Inspirado por esta pergunta

Outra maneira de desenrolar uma imagem 2D em uma sequência 1D é usar uma Curva de Hilbert.

Há muitas versões dessa curva, dependendo do número de iterações usadas durante o cálculo. Abaixo segue o exemplo das curvas de Hilbert da primeira ordem à quinta ordem.

A maneira de calcular essa curva é a seguinte. Primeiro, definimos a Curva de Hilbert de primeira ordem como a mostrada na figura (a de n = 1), para que ela caiba em um quadrado 1x1. Nós, então, fazemos quatro cópias dessa curva, espaçando-as em um quadrado 4x4, para que todas apresentem a "concavidade" no lado esquerdo. Em seguida, invertemos as duas curvas 1 da ordem mais à esquerda, para que a concavidade superior fique voltada para o topo, enquanto a inferior fica voltada para o fundo. Finalmente, conectamos os cantos das curvas Hilbert adjacentes. Se desejar obter uma curva de ordem (n + 1), basta repetir o processo com quatro curvas de ordem n. Podemos ver uma visualização do processo aqui (também adicionarei uma imagem detalhando o processo em breve)

Sua tarefa neste desafio é desenrolar uma matriz de números inteiros ao longo da ordem mais baixa de Hilbert Curve para essa matriz.

Por uma questão de simplicidade, teremos a curva começando no canto superior esquerdo da matriz.

Você pode receber a entrada como uma lista da lista de números inteiros, onde cada sub-lista representa uma linha da matriz.

Você pode assumir que a entrada será uma matriz quadrada (n * n).

Por exemplo:

Entrada:

[[ 1, 2,]
 [ 3, 4 ]]

Resultado:

[ 1, 2, 4, 3 ]

Como estamos usando a primeira curva de Hilbert mostrada na figura

Entrada:

[[ 1, 2, 3, 4,    ]
 [ 5, 6, 7, 8,    ]
 [ 9, 10, 11, 12, ]
 [ 13, 14, 15, 16 ]]

Resultado:

[ 1, 5, 6, 2, 3, 4, 8, 7, 11, 12, 16, 15, 14, 10, 9, 13 ]

Usando a segunda ordem Hilbert Curve

Como sempre, brechas padrão não são permitidas.

Isso é código-golfe, então a resposta mais curta em byte vence.

MATL , 86 85 bytes

Esta solução é baseada na entrada File Exchange de Jonas Lundgren, que utiliza números complexos para gerar a curva de Hilbert. Esses números complexos são então convertidos em valores de índice para recuperar os elementos da matriz que caem ao longo da curva.

nZl2/1XLJQXH1J-XI0,1L:"XJJZj1j*XKKH-JI-JH+IK-,4$h2/]XJJ1L*XJJH+J1)-XHGHXjHYj3$)1$Xd1$

Experimente online!

Explicação

%--- Define some numbers to be used throughout ---%
n                   % Retrieve the number of elements in the input matrix
Zl2/                % Compute the order of the curve (log2(numel(i))/2)
1XL                 % Store the order in the 1L clipboard
JQ XH               % Store 1 + j in H clipboard
1J- XI              % Store 1 - j in I clipboard
0                   % Place 0 onto the stack

%--- Compute the hilbert curve ---%
1L:"                % For k = 1:order
    XJ                   % Store the top of the stack (z) in J clipboard
    JZj                  % Compute the conjugate of z (stored in J)
    1j*                  % Multiply by j to get conj(z) * j
    XK                   % Store result in K clipboard
    KH- JI- JH+ IK- 4$h  % Horizontal concatenation of K-H, J-I, J+H, and I-K
    2/                   % Divide entire array by 2
]                   % End for loop
XJ                  % Store z in J clipboard

%----- Convert complex decimal values to complex integer indices ----%
J1L*                % Multiply z by the order
XJ                  % Store result in clipboard J
JH+                 % Add 1 + j to H
J1)-                % Subtract the first element of z
XH                  % Store integer complex numbers in H

%--- Retrieve the elements from the input along the curve ---%  
G HXj HYj 3$)       % Index into input using real/imag components input(real, imag)
                    % This will yield an numel(real) x numel(imag) matrix where 
            % the diagonal values are the values we want
1$Xd                % Extract the diagonals using diag with one input
1$                   % Display only the top element on the stack

APL (Dyalog Unicode) , 41 bytes ^SBCS

Economizou 30 bytes (!) Consultando a sabedoria do APL Orchard, especialmente @ngn e @ Sherlock9.

{0::⍵⋄∊∇¨⌽∘⊖¨@4,⌽@1⊢∘⍉\⌽↑∘⍵¨∘.,⍨2 ¯2÷⍨≢⍵}

Experimente online!

Explicação da seguinte maneira:

{0::⍵⋄∊∇¨⌽∘⊖¨@4,⌽@1⊢∘⍉\⌽↑∘⍵¨∘.,⍨2 ¯2÷⍨≢⍵} ⍝ Recursive function - takes input as an
                                          ⍝ n*n square matrix
 0::⍵                                     ⍝ Our base case - this is an error guard
                                          ⍝ If there's any error, catch it and
                                          ⍝ return the function's input
                                      ≢⍵  ⍝ Find the number of rows in the input
                                2 ¯2÷⍨    ⍝ Divide the above by 2 and negative 2,
                                          ⍝ resulting in a 2-element vector
                            ∘.,⍨          ⍝ Outer product - take the above vector and
                                          ⍝ apply concatenation (,) with each element
                                          ⍝ against all elements in the vector. Since
                                          ⍝ we have a 2-element vector, this results in
                                          ⍝ a 2-by-2 matrix, e.g.
                                          ⍝ [[(2,2),(2,¯2)],[(¯2,2),(¯2,¯2)]]
                        ↑∘⍵¨              ⍝ For each element in the matrix, we apply
                                          ⍝ "take" against our original input matrix.
                                          ⍝ Take, given a negative number, will take
                                          ⍝ elements from the end of a particular rank.
                                          ⍝ With our argument above, this means that we end
                                          ⍝ up with our original original input matrix
                                          ⍝ split by quadrant into a 2-by-2 matrix.
                                          ⍝ It is also worth noting that take expects
                                          ⍝ an integer argument, so for matrices whose
                                          ⍝ rowcount divided by two results in a decimal
                                          ⍝ (i.e., 1-by-1 matrices), we throw an error
                                          ⍝ which is caught by the guard above, returning
                                          ⍝ the original input.
                       ⌽                  ⍝ Flip the above matrix about the vertical axis.
                   ⊢∘⍉\                   ⍝ Apply a "monadic transpose scan". More details
                                          ⍝ on how this works below, but for our purposes
                                          ⍝ this applies transpose to each of the two 
                                          ⍝ sub-matrices on the right half.
                ⌽@1                       ⍝ Swap the two upper sub-matrices. Given our
                                          ⍝ flip for the overall matrix above, this returns
                                          ⍝ the two upper quadrants to their original
                                          ⍝ positions.
               ,                          ⍝ Ravel: flatten the 2-by-2 matrix into a
                                          ⍝ 4-element vector
         ⌽∘⊖¨@4                           ⍝ Take the last element of the list (the lower
                                          ⍝ right quadrant originally) and flip it
                                          ⍝ along the vertical and horizontal axes. Given
                                          ⍝ the transposition above, this has the final
                                          ⍝ effect of transposition along the antidiagonal.
       ∇¨                                 ⍝ For each element in the above vector, recurse.
      ∊                                   ⍝ Recursively flatten the results into a single
                                          ⍝ vector.

Mais detalhes em " varredura de transposição monádica ".

Documentação Dyalog sobre proteções contra erros .

Mathcad, 302 bytes

O programa Mathcad abaixo é baseado no programa @ Sherlock9 Python. Difere curvando matrizes retangulares ignorando as partes da Curva de Hilbert que ficam fora dos limites da matriz. Observe que, como o Mathcad possui um manuseio de string relativamente ruim, mapeei os símbolos Lindenmayer para números inteiros na função Hilbert.

O Mathcad funciona através de uma interface 2D que permite ao usuário inserir (e misturar livremente) expressões matemáticas, gráficos, texto, entradas e saídas. Equacionei um byte à operação equivalente no teclado mínimo do usuário para criar um símbolo (por exemplo, o operador de definição (: =) é inserido digitando simplesmente:.

Python 3, 327 289 275 271 239 234 bytes

Esta é uma solução que modifiquei da minha resposta para outra pergunta da curva de Hilbert aqui . Todas as dicas de golfe são apreciadas.

Editar: Alterado como gé incrementado e decrementado. Agora usando eval()e str.translate. Não está mais usando l=len(s).

def h(s):
 t=[s[0][0]];x=y=g=0;b="A"
 for j in range(len(bin(len(s)))-3):b=b.translate({65:"-BF+AFA+FB-",66:"+AF-BFB-FA+"})
 for c in b:g+=(c<"-")-(c=="-");a=c>"B";x,y=[[x,y],[[x+1-g%4,y],[x,y+g%4-2]][g%2]][a];t+=[s[x][y]]*a
 return t

Ungolfed:

# the following function is implemented in the code with b=b.translate

def hilbert(it):
    s="A"
    n=""
    for i in range(it):
        for c in s:
            if c == "A":
                n += "-BF+AFA+FB-"
            elif c == "B":
                n += "+AF-BFB-FA+"
            else:
                n += c
        s=n;n=""
    return s

def matrix_to_hilbert(mat):
    length = len(mat)       # this returns the number of rows in the matrix
    if length < 2:
        return mat
    it = len(bin(length)) - 3
    hil = hilbert(it)
    output = [mat[0][0]]    # a list that starts with the first element of the matrix
    x = 0
    y = 0
    heading = 0
    for char in hil:        # navigating the Hilbert curve
        if char == "-": heading += -1
        elif char == "+": heading += 1
        elif char == "F":
            if heading % 4 == 3: y += 1
            elif heading % 4 == 2: x -= 1
            elif heading % 4 == 1: y -= 1
            else: x += 1
            output.append(mat[x][y])
    return output

Wolfram - 233

Com base na representação como sistema Lindenmayer :

f[m_]:=m[[Sequence@@Reverse[#+1]]]&/@DeleteDuplicates@AnglePath[Pi/2,List@@StringReplace[Last@SubstitutionSystem[{"A"->"-BF+AFA+FB-","B"->"+AF-BFB-FA+"},"A",Round@Sqrt@Length@m],{"A"|"B"->"","-"->{0,-Pi/2},"+"->{0,Pi/2},"F"->{1,0}}]]

Ruby, 224 221 216 bytes

Esta resposta é baseada em minha resposta Python .

->s{t=[s[0][0]];x=y=g=0;b=?A;(s.size.bit_length-1).times{b=b.split("").map{|c|c==?A?"-BF+AFA+FB-":c==?B?"+AF-BFB-FA+":c}.join("")};b.each_char{|c|g+=c==?-?-1:c==?+?1:0;(g%2>0?y+=g%4-2:x+=1-g%4;t<<s[x][y])if c==?F};t}

Ungolfing:

def hilbert(mat)
  result = mat[0][0]
  x = 0
  y = 0
  heading = 0
  b = "A"
  (mat.size.bit_length-1).times do each |j| # Hilbert curve using a Lindenmayer system
    a = b.split("").map do |char|
      if char == "A"
        "-BF+AFA+FB-"
      else if char == "B"
        "+AF-BFB-FA+"
      else
        char
      end
    end
    b = a.join("")
  end
  b.each_char do |char| # navigating the matrix
    if char == "-"
      heading += -1
    else if char == "+"
      heading += 1
    else if char == "F"
      if heading % 2 == 0
        y += heading % 4 - 2
      else
        x += 1 - heading % 4
      end
      result << s[x][y]
    end
  return result
  end

CJam, 60

Lq~:A,2mL{:B1f^0B1B2B3f^]:+}*1+{AT=U=\2md'U^_~)@2*-':@+~;}%p

Experimente online

Explicação:

Estou construindo o fractal como uma série de direções de movimento: 0 = direita, 1 = abaixo, 2 = esquerda, 3 = acima.

L          push an empty array (level 0 fractal)
q~:A       read the input, evaluate and store in A
,2mL       get the length (number of rows) and calculate the logarithm in base 2
            (to get the desired level)
{…}*       repeat <level> times
  :B       store the previous-level fractal in B
  1f^      XOR it with 1 (top-left part)
  0        (move right)
  B        copy the fractal (top right part)
  1        (move down)
  B        copy the fractal (bottom right part)
  2        (move left)
  B3f^     copy the fractal and XOR it with 3 (bottom left part)
  ]:+      put everything in an array and concatenate the parts
1+         add a dummy move (needed for the last step)
{…}%       apply to each direction in the array
  AT=U=    push A[T][U] (T and U are initially 0)
  \2md     bring the direction to the top and get the quotient and remainder mod 2
  'U^      XOR the 'U' character with the remainder,
            to get the variable we want to modify
  _~)      make a copy of it, then evaluate it and increment
  @2*-     bring the quotient to the top, multiply by 2 and subtract
  ':@+     concatenate ':' with the variable name
  ~;       evaluate (this updates the variable) and pop the result
p          pretty-print the resulting array