Hilbert-Curvify a Matrix

Question

Inspired by this question

Another way to unroll a 2D image into a 1D string is to use an Hilbert Curve.

There are many version of this curve, depending on the number of iterations used while computing it. Below follow example of Hilbert Curves from first order to fifth order.

The way of computing this curve is the following. First we define the first order Hilbert Curve as the one shown in figure (the one for n = 1), so that it fits in a 1x1 square. We than make four copies of this curve, spacing them in a 4x4 square, so that they all present the "concavity" towards the left side. We then flip the two leftmost order 1 curves, so that the top one concavity faces toward the top, while the bottom's faces the bottom. We finally connect the the corners of the adjacent Hilbert Curves. If wanting to obtain a (n+1)-order Curve, we just need to repeat the process with four n-order Curves. We can see a visualisation of the process here (I will also add an image detailing the process soon)

Your task in this challenge is to unroll a matrix of integers along the lowest order Hilbert Curve for that matrix.

For simplicity's sake, we will have the curve starting from the top left corner of the matrix.

You can receive the input either as a list of list of integers, where each sub-list represents a row of the matrix.

You can assume that the input will be a square matrix (n*n).

For example:

Input:

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

Output:

[ 1, 2, 4, 3 ]

Since we are using the first order Hilbert Curve shown in figure

Input:

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

Output:

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

Using the second order Hilbert Curve

As usual, standard loopholes are not permitted.

This is code-golf, so the shortest answer in byte wins.

Answer 1

APL (Dyalog Unicode), 41 bytes^SBCS

Saved 30 bytes (!) by consulting the wisdom of the APL Orchard, especially @ngn and @Sherlock9.

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

Try it online!

Explanation as follows:

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

More details on "monadic transpose scan".

Dyalog documentation on error guards.

Answer 2

MATL, 86 85 bytes

This solution is based upon Jonas Lundgren's File Exchange entry which utilizes complex numbers to generate the Hilbert curve. These complex numbers are then converted to index values to retrieve the elements of the matrix that fall along the curve.

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

Try it online!

Explanation

%--- 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

Answer 3

Python 3, 327 289 275 271 239 234 bytes

This is a solution I modified from my answer for another Hilbert curve question here. Any golfing tips are appreciated.

Edit: Changed how g is incremented and decremented. Now using eval() and str.translate. No longer using 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

Answer 4

Mathcad, 302 bytes

The Mathcad program below is based on the @Sherlock9 Python program. It differs by curvifying rectangular matrices by ignoring those parts of the Hilbert Curve that lie outside of the matrix bounds. Note that as Mathcad has relatively poor string handling, I've mapped the Lindenmayer symbols to integers in the Hilbert function.

Mathcad works through a 2D interface that allows the user to place (and freely mix) mathematical expressions, plots, text, inputs and outputs. I've equated a byte to the minimum user keyboard equivalent operation to create a symbol (for example, the definition operator (:=) is entered by simply typing :.

Answer 5

Uiua, 36 bytes

⊏⍏∩♭⍥(⊂∶¯+¬×2⧻♭.⇌.≡⊂⊃⍉+∶⧻♭.)ₙ2⧻,↯1⇡1

Try it online!

Constructs the path on the matrix directly, and uses it to index into the matrix.

⊏⍏∩♭⍥(⊂∶¯+¬×2⧻♭.⇌.≡⊂⊃⍉+∶⧻♭.)ₙ2⧻,↯1⇡1    input: matrix M of size 2^n*2^n
↯1⇡1    the initial Hilbert matrix [[0]]
ₙ2⧻,    log 2 of the length of M (= n)
⍥(...)   repeatedly construct the Hilbert matrix by calling the inner function n times...
  ∶⧻♭.   put the number of elements in the current matrix under itself
  ⊃⍉+   construct the top two submatrices: 1) transpose 2) add to each element
  ≡⊂     join horizontally
  ⇌.     create a copy and reverse its rows
  ¯+¬×2⧻♭.  a bunch of arithmetic to get the bottom two submatrices
  ⊂∶      join vertically in reverse
∩♭    flatten the Hilbert matrix and M
⊏⍏    put the elements of M in the increasing order in the Hilbert matrix

Uiua, 41 bytes

⊡⍉∧(≡⊂∶⍜⊢-≡⇌,-1×2∶≡⊂∶⇌⍜⊢+,,⇌)↯2⇡1ⁿ∶2⇡ₙ2⧻.

Try it online!

Constructs the list of coordinates and indexes into the original matrix using ⊡ "pick".

Answer 6

Wolfram - 233

Based on representation as Lindenmayer system:

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}}]]

Answer 7

Ruby, 224 221 216 bytes

This answer is based on my Python answer.

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

Answer 8

CJam, 60

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

Try it online

Explanation:

I'm building the fractal as a series of movement directions: 0=right, 1=down, 2=left, 3=up.

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