Hilbert-Curvificar una matriz

19

Inspirado por esta pregunta

Otra forma de desenrollar una imagen 2D en una cadena 1D es usar una curva de Hilbert.

Hay muchas versiones de esta curva, dependiendo del número de iteraciones utilizadas al calcularla. A continuación, siga el ejemplo de las curvas de Hilbert de primer orden a quinto orden.

ingrese la descripción de la imagen aquí

La forma de calcular esta curva es la siguiente. Primero definimos la curva de Hilbert de primer orden como la que se muestra en la figura (la de n = 1), para que quepa en un cuadrado de 1x1. Entonces hacemos cuatro copias de esta curva, espaciándolas en un cuadrado de 4x4, de modo que todas presenten la "concavidad" hacia el lado izquierdo. Luego volteamos las dos curvas de orden 1 más a la izquierda, de modo que la concavidad superior se enfrenta hacia la parte superior, mientras que la inferior se enfrenta a la parte inferior. Finalmente conectamos las esquinas de las curvas adyacentes de Hilbert. Si queremos obtener una curva de orden (n + 1), solo necesitamos repetir el proceso con cuatro curvas de orden n. Podemos ver una visualización del proceso aquí (también agregaré una imagen que detalla el proceso pronto)

Su tarea en este desafío es desenrollar una matriz de enteros a lo largo de la curva de Hilbert de orden más bajo para esa matriz.

En aras de la simplicidad, tendremos la curva comenzando desde la esquina superior izquierda de la matriz.

Puede recibir la entrada como una lista de enteros, donde cada sublista representa una fila de la matriz.

Puede suponer que la entrada será una matriz cuadrada (n * n).

Por ejemplo:

Entrada:

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

Salida:

[ 1, 2, 4, 3 ]

Como estamos usando la curva de Hilbert de primer orden que se muestra en la figura

Entrada:

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

Salida:

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

Usando la curva de Hilbert de segundo orden

Como de costumbre, las lagunas estándar no están permitidas.

Este es el código de golf, por lo que gana la respuesta más corta en bytes.

WizardOfMenlo
fuente
1
Relacionado.
ETHproductions
@StewieGriffin seguro, estoy en ello
WizardOfMenlo
1
@StewieGriffin He agregado un breve resumen, haré un trabajo más completo en la próxima hora más o menos, después de terminar las lecciones
WizardOfMenlo
La matriz no solo debe ser cuadrada, también necesita n para ser una potencia de 2.
mbomb007

Respuestas:

5

MATL , 86 85 bytes

Esta solución se basa en la entrada de Intercambio de archivos de Jonas Lundgren que utiliza números complejos para generar la curva de Hilbert. Estos números complejos se convierten luego en valores de índice para recuperar los elementos de la matriz que se encuentran a lo largo de la curva.

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

Pruébalo en línea!

Explicación

%--- 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
Suever
fuente
@DonMuesli Estoy trabajando en una mejor manera de manejar esto. ¡Definitivamente está lejos de ser elegante! Gracias por los consejos. ¡Actualizado!
Suever
No he investigado este desafío específico. A veces no se pueden evitar los portapapeles
Luis Mendo
5

APL (Dyalog Unicode) , SBCS de 41 bytes

Ahorró 30 bytes (!) Al consultar la sabiduría de APL Orchard, especialmente @ngn y @ Sherlock9.

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

Pruébalo en línea!

Explicación como sigue:

{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),(22)],[(¯2,2),(¯22)]]
                        ↑∘⍵¨               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.

Más detalles sobre " escaneo de transposición monádica ".

Documentación de Dyalog sobre protectores de errores .

halcón vacío
fuente
3

Mathcad, 302 bytes

El siguiente programa Mathcad se basa en el programa Python @ Sherlock9. Se diferencia al curvar matrices rectangulares al ignorar aquellas partes de la curva de Hilbert que se encuentran fuera de los límites de la matriz. Tenga en cuenta que como Mathcad tiene un manejo de cadenas relativamente pobre, he asignado los símbolos de Lindenmayer a enteros en la función de Hilbert.

ingrese la descripción de la imagen aquí

Mathcad funciona a través de una interfaz 2D que permite al usuario colocar (y mezclar libremente) expresiones matemáticas, diagramas, texto, entradas y salidas. He igualado un byte a la operación mínima equivalente del teclado del usuario para crear un símbolo (por ejemplo, el operador de definición (: =) se ingresa simplemente escribiendo:.

Stuart Bruff
fuente
3

Pitón 3, 327 289 275 271 239 234 bytes

Esta es una solución que modifiqué de mi respuesta para otra pregunta de la curva de Hilbert aquí . Cualquier consejo de golf es apreciado.

Editar: se modificó cómo gse incrementa y disminuye. Ahora usando eval()y str.translate. Ya no lo uso 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

Sin golf:

# 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
Sherlock9
fuente
2

Wolfram - 233

Basado en la representación 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}}]]
silbido
fuente
¿Podrías publicar algunas capturas de pantalla para los usuarios que no tienen Mathematica?
WizardOfMenlo
2
¿Es "Wolfram" diferente de Mathematica? Si no, debería llamarse Mathematica.
mbomb007
@WizardOfMenlo Aquí está trabajando en línea
swish
@swish Creo que necesitas cambiar el permiso de la aplicación web, parece estar bloqueada
WizardOfMenlo
@ mbomb007 Wolfram es el nombre del lenguaje , Mathematica es como un IDE.
swish
1

Rubí, 224 221 216 bytes

Esta respuesta se basa en mi respuesta de 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}

No golfista:

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
Sherlock9
fuente
1

CJam, 60

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

Pruébalo en línea

Explicación:

Estoy construyendo el fractal como una serie de direcciones de movimiento: 0 = derecha, 1 = abajo, 2 = izquierda, 3 = arriba.

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
aditsu
fuente