Recursive Z-matrix

Originally from a CMC I proposed for the last BMG event

Challenge

Given a non-negative integer $$\n\$$, create a 2D array of size $$\2^n × 2^n\$$ which is generated in the following manner:

1. Divide the matrix into four quadrants of size $$\2^{n-1} × 2^{n-1}\$$.
2. Visiting order of the four quadrants is defined to be the Z-shape (top-left, top-right, bottom-left, then bottom-right).
3. Recursively apply the ordering (steps 1-2) to each quadrant, until the ordering is defined for each cell in the matrix.
4. Visit each cell in the defined order, sequentially writing down 0, 1, 2, 3, ... to each cell.

You can output 1-based instead of 0-based (add 1 to all cells in the examples below).

Standard rules apply. The shortest code in bytes wins.

Examples

n = 0:
[[0]]

n = 1:
[[0, 1],
[2, 3]]

n = 2:
[[0,  1,  4,  5],
[2,  3,  6,  7],
[8,  9,  12, 13],
[10, 11, 14, 15]]

n = 3:
[[0,  1,  4,  5,  16, 17, 20, 21],
[2,  3,  6,  7,  18, 19, 22, 23],
[8,  9,  12, 13, 24, 25, 28, 29],
[10, 11, 14, 15, 26, 27, 30, 31],
[32, 33, 36, 37, 48, 49, 52, 53],
[34, 35, 38, 39, 50, 51, 54, 55],
[40, 41, 44, 45, 56, 57, 60, 61],
[42, 43, 46, 47, 58, 59, 62, 63]]


Brownie points for beating or tying with my 9 6 bytes in Jelly or 19 bytes in J.

• What is Biweekly Mini Golf? Commented Jul 5, 2021 at 23:44
• Commented Jul 5, 2021 at 23:52
• This could possibly help someone with a recursive solution: a=(a+171)&(341) Commented Jul 6, 2021 at 12:12
• This is just one of the bijections between ℕ² and ℕ, specifically the number at a given row and column is obtained by interleaving the bit patterns of the row and column.
– Neil
Commented Jul 6, 2021 at 13:14
• Is transposed output okay?
– lynn
Commented Jul 6, 2021 at 19:30

Jelly, 5 bytes

4ṗ>2Ġ


Try it online! Neil saved a byte. Thanks!

4ṗ       n-th Cartesian power of [1,2,3,4]
>2     Replace 1,2,3,4 with 0,0,1,1
Ġ    Group indices by values


For n=2, 4ṗ>2 generates a list of 16 pairs:

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


Then Ġ turns this into a list of lists:

• all indices where the value is 0 0: namely [ 1, 2, 5, 6],
• all indices where the value is 0 1: namely [ 3, 4, 7, 8],
• all indices where the value is 1 0: namely [ 9, 10, 13, 14],
• all indices where the value is 1 1: namely [11, 12, 15, 16].

The result is a Z-matrix.

Why does this work?

Suppose we bump the input up to $$\n=3\$$. How does our output compare to that for $$\n=2\$$?

Let's call 4ṗ>2 a function $$\f\$$. The list of 16 pairs above is the output of $$\f(2)\$$. By definition of the Cartesian power, $$\f(3) = [0,0,1,1] \times f(2)\$$ =

  [[0] + x for x in f(2)]     (indices  1..16)
+ [[0] + x for x in f(2)]     (indices 17..32)
+ [[1] + x for x in f(2)]     (indices 33..48)
+ [[1] + x for x in f(2)]     (indices 49..64)


There are now 8 values for Ġ to group the indices by, ranging from [0,0,0] to [1,1,1].

All indices in 1..32 end up in the first four groups, and because we repeated [[0] + x for x in f(2)] twice, a[i+16] is always in the same group as a[i]. Then, all indices in 33..64 end up in the last four groups, and their relative order is the same as the first half of the list (the only difference is they have 1 instead of 0 in front). Within each quadrant, the order is the same as it was in f(2). So we get:

[0, 0, 0]:  1  2  5  6 17 18 21 22
[0, 0, 1]:  3  4  7  8 19 20 23 24
[0, 1, 0]:  9 10 13 14 25 26 29 30
[0, 1, 1]: 11 12 15 16 27 28 31 32

[1, 0, 0]: 33 34 37 38 49 50 53 54
[1, 0, 1]: 35 36 39 40 51 52 55 56
[1, 1, 0]: 41 42 45 46 57 58 61 62
[1, 1, 1]: 43 44 47 48 59 60 63 64

• I don't think you need the Ḅ.
– Neil
Commented Jul 6, 2021 at 20:02

Charcoal, 2723 18 bytes

≔ＥＸ²Ｎ↨⁴↨ι²υＩＥ⊗υ⁺ιυ


Try it online! Link is to verbose version of code. Explanation: Now a port of @tsh's Python answer.

≔ＥＸ²Ｎ↨⁴↨ι²υ


Map the numbers up to 2ⁿ by converting them to base 2 and then interpreting the result as base 4.

ＩＥ⊗υ⁺ιυ


Vectorised add the doubled array to itself as a matrix.

Previous 27 23 byte answer uses a different approach that is interesting in its own right because some golfing languages have built-ins for things like group index by value or sort array by key.

≔ＥＸ⁴Ｎ↨²÷↨ι⁴¦²υＩＥ⊕⌈υ⌕Ａυι


Try it online! Link is to verbose version of code. Explanation:

≔ＥＸ⁴Ｎ↨²÷↨ι⁴¦²υ


For each element in the final diagram, convert it to base 4, halve the digits, then convert from base 2. This gives the row number for that element.

ＩＥ⊕⌈υ⌕Ａυι


For each row list the elements assigned to that row.

J, 21 19 bytes

Found Bubbler's solution. :-)

2(*+/])4#.2#:@i.@^]


Try it online!

The first row is A000695, the first column is the same but times two. In the comments Marc LeBrun notes that this is rebasing n from base 2 into base 4. So that's helpful with J:

2(*+/])4#.2#:@i.@^]
2   i.@^]  0 1 … 2^n
#:        digits in base 2
0 0 0
0 0 1
…
1 1 0
1 1 1
4#.           interpret as digits in base 4
0 1 4 5 16 17 20 21
2(*+/])              addition table of list*2 with list

• Nice. Weird, both of our answers got a random downvote.... Commented Jul 7, 2021 at 0:50

R, 65635957 55 bytes

for(i in seq(l=scan()))T=T^4%x%2^rbind(0:1,2:3);log2(T)


Try it online!

Relies on the observation that each next iteration N relates to the previous iteration P by Kronecker product-like operation with the matrix M for n=1, but using summation instead of multiplication:

N = kronecker(4*P, M, FUN = "+")


Here, we transform the values with powers and logarithms in order to make use of the actual Kronecker product function, which is conveniently abbreviated as %x% operator.

Python 2, 81 bytes

R=[int(bin(x)[2:],4)for x in range(2**input())]
for y in R:print[x+y*2for x in R]


Try it online!

R, 5752 49 bytes

Edit: -8 bytes by changing to iterative approach with scan() for input (instead of recursive function)

for(i in seq(l=2*scan())-1)F=t(cbind(F,F+2^i));+F


Try it online!

Explanation

Recursive function that Each loop icreates two side-by-side copies of the columns of a matrix, adding the maximum value of the first +1 2^i to the second copy, and then transposes it all.

This creates the top left & top right copies of the last matrix (F), transposed: so, every second loop creates a full 'Z' of four copies of the last matrix, untransposed.

So we need to loop twice the value of n times.

Jelly, 9 bytes

4*Ḷb4:2ḄĠ


Try it online!

Pretty much a port of Neil's Charcoal answer, so go upvote them too.

4*Ḷb4:2ḄĠ    Main Link; take x
4*           4 ** x
Ḷ          [0, 1, 2, ..., 4 ** x - 1]
b4        Convert to base 4
:2      Floor-divide by 2
Ḅ     Convert from binary
Ġ    Group the indices by their corresponding values


This answer can be ported directly into yuno.

yuno, 9 bytes

4*ʀb4:2ɮG


Try it online!

This approach is probably what Bubbler's 6-byter is going for, but a) I need to find how to get 0,0,1,1 in 3 bytes, and b) I need to figure out how to make the format valid without the s2*$ being that long: Jelly, 11 bytes Ø.x2¤ṗỤs2*$


Try it online!

Jelly, 16 bytes

,Uz0$FU 2*ḶBçþḄ  Try it online! Wolfram Language (Mathematica), 49 32 bytes PositionIndex@Tuples[0|0|1|1,#]&  Try it online! Returns an Association where the values correspond with rows of the matrix (associations are ordered). For a traditional list-of-lists output, prepend List@@ (+6 bytes). Port of Lynn's Jelly solution. Older solution: Outer[#+##&,t=#~FromDigits~4&/@{0,1}~Tuples~#,t]&  Try it online! • Is {0,1}~Tuples~# a way to save 1 byte over Tuples[{0,1},#]? Commented Jul 6, 2021 at 4:49 • @Jonah Right, the infix form can save one byte for two-argument functions, just as prefix saves one for single-argument functions. – att Commented Jul 6, 2021 at 5:04 ARM A32 machine code, 48 bytes e3a0c000 e1a0215c e1b03152 112fff1e e02c3112 ec432b10 f2800e00 f2810590 f2211110 f480180d e28cc001 eafffff4  Following the AAPCS, this takes in r0 the address of an array of arrays of 32-bit integers to be filled with the result, and takes n in r1. Assembly: .section .text .code 32 .global zm zm: mov r12, #0 @ Initialise counter to 0 loop: asr r2, r12, r1 @ Shift counter right by n, to obtain the top half asrs r3, r2, r1 @ Shift that right by n again, to check for ending (2^2n) bxne lr @ If so, return eor r3, r12, r2, lsl r1 @ Exclusive-or cancels out the top half, to obtain the bottom half vmov d0, r2, r3 @ Place the two halves into a 64-bit SIMD&FP register vmull.p8 q0, d0, d0 @ Multiply by itself as polynomials over GF(2); @ because this is a ring of characteristic 2, (a+b)^2 = a^2 + b^2 holds, @ thus squaring doubles each exponent in the polynomial, spreading out the bits. @ Results go into Q0, which is also D0 and D1. vshl.i64 d0, #1 @ Shift the squared top half left by 1 ... vorr d1, d0 @ ... and combine by OR with the bottom half vst1.32 {d1[0]}, [r0]! @ Place the result into memory, advancing the pointer add r12, #1 @ Increment the counter b loop @ Repeat  (This should work on v7 or later from what I can tell, but in the testing setup I'm using (similar to here), it gives 'instruction not supported' errors on versions lower than v8.4, which doesn't seem right.) Jelly, 14 12 9 bytes 9 byter Ø.ṗḅ4+þḤ$


Try it online!

How?

Makes a table under $$\x+2y\$$ where both $$\x\$$ and $$\y\$$ are a prefix of the Moser–De Bruijn sequence.

Ø.ṗḅ4+þḤ$- Link: n Ø. - bits -> [0,1] ṗ - Cartesian power (n) -> binary representations of [0..2^n-1] ḅ4 - convert from base four -> first 2^n terms of the Moser–De Bruijn sequence$ - last two links as a monad, f(S):
Ḥ  -   double -> D=[2x for x in S]
þ   -   (s in S) table with (d in D):
+    -     (s) add (d)


(Still no clue for the 6 byte code though!)

12 Byter

-1 thanks to caird coinheringaahing (we can use 1-based values)

Ġ;"FL+ƊZƊ⁸¡⁺


A monadic Link that accepts a non-negative integer and yields the matrix (using the 1-based values option).

Try it online! (Footer formats as a Python list for clarity.)

How?

Starts with [[1]] and repeatedly applies a function that creates the required new entries to the right (and then below, via the transposed matrix) by adding the number of current elements to each element.

Ġ;"FL+ƊZƊ⁸¡⁺ - Link: non-negative integer, n
Ġ            - group indices (of implicit [n]) by value -> [[1]] (our initial M)
¡  - repeat...
⁸   - ...number of times: chain's left argument -> n
Ɗ    - ...what: last three links as a monad, f(M):
Ɗ      -   last three links as a monad, g(M):
F         -     flatten
L        -     length
+       -     add to elements of M
"          -   zip (rows of M) with (rows of that) and apply:
;           -     concatenation
Z     -   transpose
⁺ - repeat last link (i.e. repeat f() n more times)

• The trick with Ġ’ is brilliant! Plus, you can remove the ’ as the challenge allows 1 indexing Commented Jul 6, 2021 at 1:04
• Thanks, I was wracking my brain for a while for that. Commented Jul 6, 2021 at 1:07

Python 3 with numpy, 9187747069 67 bytes

lambda n:c_[s:=(c_[:1<<n]&(b:=1<<r_[:n]))@b]*2+s
from numpy import*

Attempt This Online!

c_[:1<<n] produces an array of the numbers 0 (inclusive) to 2n (exclusive), vertically. r_[:n] produces 0 (inc.) to n (exc.), horizontally, and the left shift makes the corresponding powers of 2, saved in b. The bitwise AND, with broadcasting, produces a table of values, splitting the numbers into their constituent bits. The matrix product (@) is equivalent to taking the dot product of each broken-down number with b; this squares each nonzero bit, changing powers of 2 into powers of 4, and adds them back up, producing a horizontal sequence 0, 1, 4, 5, 16, 17, 20, 21, ..., which is saved in s. c_ makes a vertical version of that sequence, which is doubled and added to the original sequence, which (by broadcasting) produces a table of sums, which is the required result.

Previously:

from numpy import*
lambda n:(s:=vander([4],8)@unpackbits(mat(r_[:1<<n],uint8),0))+s.T*2


r_[:1<<n] produces 0 (inc.) to 2n (exc.). It is passed to mat ("Interpret the input as a matrix"), which in particular makes it 2-dimensional, while also changing its type to uint8, which is necessary for the next function unpackbits, which breaks the numbers down into their binary representations, across the added dimension. vander([4],8) produces an array of powers of 4, which in the @ (matrix multiplication) gets dot-producted with each binary vector, producing a similar s (transposed differently), and the rest is similar.

• Think I three-upped you with a more pedestrian approach; still, quite like the elegance of this! Commented Nov 14, 2021 at 0:42

f n|r<-iterate(>>= \x->[4*x,4*x+1])[0]!!n=[[x+2*y|x<-r]|y<-r]


Try it online!

Same idea as tsh's Python, but the list r (e.g. [0,1,4,5,16,17,20,21]) is created in a Haskell-y way.

Julia 1.0, 42 bytes

!x=(x-=1)<0||(~n=n*2^2x.+!x;[~0 ~1;~2 ~3])


Try it online! (one-indexed)

JavaScript (ES6),  89 86  79 bytes

Saved 7 bytes thanks to @tsh

n=>[...Array(1<<n)].map((_,y,a)=>a.map(g=(k=1,x)=>k>>n?0:x&k|(y&k|g(k*2,x))*2))


Try it online!

• n=>[...Array(1<<n)].map((_,y,a)=>a.map(g=(k=1,x)=>k>>n?0:x&k|(y&k|g(k<<1,x))*2))
– tsh
Commented Jul 6, 2021 at 2:41
• @tsh Nice. Initializing the leading argument of a map callback when iterating on an array of undefined values is not a very common golfing pattern -- at least for me. I'll try to remember that. Commented Jul 6, 2021 at 9:23

Octave/MATLAB, 67 bytes

function x=f(n);x=1;for i=1:n;k=4^i/4;x=[x,k+x;2*k+x,3*k+x];end;end


Try it online!

f 0=[[1]]
f n=let(#)=zipWith(++);m=n-1;a=f m;[b,c,d]=map(map(+4^m))<$>[a,b,c]in a#b++c#d  Try it online! Ruby, 90... 64 bytes ->n{(k=0...2**n).map{|y|k.map{|x|k.sum{|z|[x,y][z%2][z/2]<<z}}}}  Try it online! Quick explanation: Every number can be expressed by interleaving the binary digits of the number of row and column. Pip, 19 bytes $+{TBg}FB4*^21MC Ea


Try it here! Or, here's a 20-byte equivalent in Pip Classic: Try it online!

Explanation

Inspired by Neil's comment about interleaving bit patterns, we can simply map the x and y coordinates to the right value (example x = 5, y = 9):

5    101    0 1 0 1
9   1001   1 0 0 1    10010011   147


We're not going to use Pip's WV operator to do the interleaving, since it works left-to-right and doesn't fill in with zeros; instead, observe that an equivalent formula is to convert to base 4, multiply the y value by 2, and sum:

5    101      1 0 1      10001 (2) =  101 (4) =  17 (10)
9   1001   1 0 0 1    10000010 (2) = 2002 (4) = 130 (10)   147


So:

$+{TBg}FB4*^21MC Ea Ea 2^input MC Map this function to a grid of coordinate pairs of that size: {TBg} Convert each coordinate to binary FB4 Treat as base 4 and convert back to decimal * Multiply by ^21 list containing 2 and 1 (multiplying the row by 2 and the column by 1)$+                     Sum


Python 3 + numpy, 66 bytes

from numpy import*
f=lambda m:c_[m and(f(m-.5),4**m//2+f(m-.5))].T


Try it online!

Mostly straight-forward recursion. Splits the 2x2 update into 2 1x2 updates with intermittent transpose.

Python 3 + numpy, 68 bytes

from numpy import*
f=lambda m:m and log2(kron(4**f(m-.5),c_[1:3])).T


Try it online!

Just noticed that @Kirill L.'s R answer uses the exact same idea.

By componentwise exponentiating adding in the original problem becomes multiplying so friend Kronecker can do the heavy lifting for us.

Downside: will get numerically inaccurate pretty fast.

BQN, 18 bytes

{(⍉∾⍉+·≠⥊)⍟2⍟𝕩≍≍0}


Try it here.

How it works:

{(⍉∾⍉+·≠⥊)⍟2⍟𝕩≍≍0}
≍≍0  # Starting from a rank 2 array containing 0
⍟𝕩     # apply the preceding function 𝕩 times where 𝕩 is the input
⍉∾               # The transposed array joined to
⍉+·≠⥊          # the transposed array plus the number of elements
(       )⍟2       # applied twice


flax, 5 bytes

G>1ṗ4


Port of @lynn's Jelly answer.

Since the lastest version isn't on ATO, here is an image of the program running (in the REPL).

Explanation

It is same as the jelly answer.

G>1ṗ4
G      " group by values
>1    "   greater than 1
ṗ4  "   nth cartesian power of [0,1,2,3]


APL(Dyalog Unicode), 10 9 bytes SBCS

⊢⌸2<,⍳⎕⍴4


Try it on APLgolf!

⊢⌸2<,⍳⎕⍴4­⁡​‎‎⁪⁡⁪⁠⁪⁢⁣⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁤⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁡⁪‏‏​⁡⁠⁡‌⁢​‎‎⁪⁡⁪⁠⁪⁢⁢⁪‏‏​⁡⁠⁡‌⁣​‎⁪⁪⁠‎⁪⁡⁪⁠⁪⁢⁡⁪‏‏​⁡⁠⁡‌⁤​‎‎⁪⁡⁪⁠⁪⁣⁪‏⁠‎⁪⁡⁪⁠⁪⁤⁪‏‏​⁡⁠⁡‌⁢⁡​‎‎⁪⁡⁪⁠⁪⁡⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁪‏‏​⁡⁠⁡‌­
⎕⍴4  # ‎⁡4 repeated n times
⍳     # ‎⁢create a n-dimensional array with shape [4, 4, ..., 4] where value equals index
,      # ‎⁣flatten
2<       # ‎⁤greater than 2 (vectorized)
⊢⌸         # ‎⁢⁡‎⁢⁡group by value and return indices for each group
💎


Created with the help of Luminespire.

Python 3 + numpy, 113 bytes

A very literal (and long) implementation of the spec.

lambda n:sum(tile(R(R(c_[:2,2:4].T,1<<i,0),1<<i,1)<<2*i,(1<<n+~i,)*2)for i in r_[:n])
from numpy import*
R=repeat


Try it online!

JavaScript (ES6), 72 bytes

f=(n,a=[0])=>n?f(n-1,a.flatMap(x=>[x*=4,x+1])):a.map(y=>a.map(x=>x+2*y))


Try it online!

Use the idea from Lynn's Haskell answer which saves many bytes on generating the list for iterate. Using base conversion as what my Python answer do will make it much longer (79 bytes).

Python 3.8 + numpy, 85 84 bytes

import numpy;z=lambda n:n and numpy.block([[m:=z(n-1),m+(k:=4**~-n)],[m+2*k,m+3*k]])


Not as clever as some of the other python ones, but shorter than the other python 3 ones. Also 0 returns a scalar instead of a list, not sure if that's allowed.

• k:=4**~-n and remove n:= for -1 byte
– att
Commented Jul 8, 2021 at 4:32

Japt, 14 bytes

Port of tsh's Python solution.

2pU Ç¤n4
£Ë+XÑ


Try it

Pari/GP, 62 bytes

n->matrix(2^n,,i,j,(g=k->fromdigits(binary(k-1),4))(i)*2+g(j))
`

Try it online!