Inspiré par cette question

Une autre façon de dérouler une image 2D dans une chaîne 1D consiste à utiliser une courbe de Hilbert.

Il existe de nombreuses versions de cette courbe, selon le nombre d'itérations utilisées lors du calcul. Ci-dessous, un exemple de courbes de Hilbert du premier au cinquième ordre.

La façon de calculer cette courbe est la suivante. D'abord, nous définissons la courbe de Hilbert de premier ordre comme celle représentée sur la figure (celle pour n = 1), de sorte qu'elle s'insère dans un carré 1x1. Nous faisons ensuite quatre copies de cette courbe, en les espaçant dans un carré 4x4, afin qu'elles présentent toutes la "concavité" vers le côté gauche. Nous inversons ensuite les deux courbes d'ordre 1 les plus à gauche, de sorte que la concavité du haut soit tournée vers le haut, tandis que celle du bas fait face au bas. Nous connectons enfin les coins des courbes de Hilbert adjacentes. Si vous voulez obtenir une courbe d'ordre (n + 1), il suffit de répéter le processus avec quatre courbes d'ordre n. Nous pouvons voir une visualisation du processus ici (j'ajouterai également une image détaillant le processus bientôt)

Votre tâche dans ce défi est de dérouler une matrice d'entiers le long de la courbe de Hilbert d'ordre le plus bas pour cette matrice.

Par souci de simplicité, nous aurons la courbe en partant du coin supérieur gauche de la matrice.

Vous pouvez recevoir l'entrée soit sous la forme d'une liste de liste d'entiers, où chaque sous-liste représente une ligne de la matrice.

Vous pouvez supposer que l'entrée sera une matrice carrée (n * n).

Par exemple:

Contribution:

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

Production:

[ 1, 2, 4, 3 ]

Puisque nous utilisons la courbe de Hilbert de premier ordre illustrée sur la figure

Contribution:

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

Production:

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

Utilisation de la courbe de Hilbert de second ordre

Comme d'habitude, les échappatoires standard ne sont pas autorisées.

C'est le code-golf, donc la réponse la plus courte en octets l'emporte.

MATL , 86 85 octets

Cette solution est basée sur l' entrée d'échange de fichiers de Jonas Lundgren qui utilise des nombres complexes pour générer la courbe de Hilbert. Ces nombres complexes sont ensuite convertis en valeurs d'index pour récupérer les éléments de la matrice qui tombent le long de la courbe.

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

Essayez-le en ligne!

Explication

%--- 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 octets ^SBCS

Économisez 30 octets (!) En consultant la sagesse de l'APL Orchard, en particulier @ngn et @ Sherlock9.

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

Essayez-le en ligne!

Explication comme suit:

{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.

Plus de détails sur le " scan de transposition monadique ".

Documentation Dyalog sur les protections d'erreur .

Mathcad, 302 octets

Le programme Mathcad ci-dessous est basé sur le programme @ Sherlock9 Python. Il diffère en courbant les matrices rectangulaires en ignorant les parties de la courbe de Hilbert qui se trouvent en dehors des limites de la matrice. Notez que comme Mathcad a une gestion des chaînes relativement médiocre, j'ai mappé les symboles Lindenmayer à des entiers dans la fonction Hilbert.

Mathcad fonctionne via une interface 2D qui permet à l'utilisateur de placer (et de mélanger librement) des expressions mathématiques, des tracés, du texte, des entrées et des sorties. J'ai assimilé un octet à l'opération équivalente minimale du clavier utilisateur pour créer un symbole (par exemple, l'opérateur de définition (: =) est entré en tapant simplement:.

Python 3, 327 289 275 271 239 234 octets

C'est une solution que j'ai modifiée de ma réponse pour une autre question de courbe de Hilbert ici . Tous les conseils de golf sont appréciés.

Edit: changé la façon dont gest incrémentée et décrémentée. Maintenant en utilisant eval()et str.translate. Ne plus utiliser 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

Non 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

Wolfram - 233

Basé sur la représentation en tant que système 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}}]]

Rubis, 224 221 216 octets

Cette réponse est basée sur ma réponse 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

Essayez-le en ligne

Explication:

Je construis la fractale comme une série de directions de mouvement: 0 = droite, 1 = bas, 2 = gauche, 3 = haut.

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