Make a Custom Bayer Matrix

Question

A Bayer matrix is a threshold map used for ordered dithering that gives the illusion of having more shades of color than actually present by using a crosshatch-like pattern.

Bayer matrices are square with a side length that is a power of 2. Here are some examples:

\$ \displaystyle\frac{1}{4} \times \begin{bmatrix} 0 & 2\\ 3 & 1 \end{bmatrix}\$

\$ \displaystyle\frac{1}{16} \times \begin{bmatrix} 0 & 8 & 2 & 10\\ 12 & 4 & 14 & 6\\ 3 & 11 & 1 & 9\\ 15 & 7 & 13 & 5 \end{bmatrix}\$

\$ \displaystyle\frac{1}{64} \times \begin{bmatrix} 0 & 32 & 8 & 40 & 2 & 34 & 10 & 42\\ 48 & 16 & 56 & 24 & 50 & 18 & 58 & 26\\ 12 & 44 & 4 & 36 & 14 & 46 & 6 & 38\\ 60 & 28 & 52 & 20 & 62 & 30 & 54 & 22\\ 3 & 35 & 11 & 43 & 1 & 33 & 9 & 41\\ 51 & 19 & 59 & 27 & 49 & 17 & 57 & 25\\ 15 & 47 & 7 & 39 & 13 & 45 & 5 & 37\\ 63 & 31 & 55 & 23 & 61 & 29 & 53 & 21 \end{bmatrix}\$

The numbers in the matrix are arranged in such a way so that each number is placed as distant from the previous ones as possible, taking account that the edges wrap.

For example, in the second matrix shown above, the 0 is placed in the top left first, then the 1 is placed two to the right and two below the 0, which is the maximum distance away from the 0. Note that the 1 is not placed in the bottom right, because since the edges wrap, the bottom right would be one to the left and one above the 0. Next, the 2 is placed with a distance of 2 from both 0 and 1, and the 3 is placed similarly.

Note that measuring the distances to generate the matrix is not the simplest method.

Challenge

Your task is to create a program or function, that when given an input side length \$s\$, outputs a Bayer matrix that has a side length of \$s\$.

Rules

• For a side length of \$s\$, you may take the input as \$s\$ or \$log_2(s)\$. You may assume that \2ドル\le s\le16\$ and that \$log_2(s)\$ is an integer. This means you are allowed to hardcode outputs, but in most cases this is not the shortest method.
• The numbers in the output matrix may range from (inclusive) \0ドル\$ to \$s^2-1\$, \1ドル\$ to \$s^2\$, \0ドル\$ to \$\frac{s^2-1}{s^2}\$, or \$\frac{1}{s^2}\$ to \1ドル\$. For example, for \$s=2\$, all of these are acceptable: \$ \begin{bmatrix} 0 & 2\\ 3 & 1 \end{bmatrix}\$, \$ \begin{bmatrix} 1 & 3\\ 4 & 2 \end{bmatrix}\$, \$ \begin{bmatrix} 0 & 0.5\\ 0.75 & 0.25 \end{bmatrix}\$, \$ \begin{bmatrix} 0.25 & 0.75\\ 1 & 0.5 \end{bmatrix} \$
• The output matrix may be offsetted or transposed, reflected, rotated, etc. as long as the general pattern is the same. This means that when there is a tie for maximum distance, any of the tied options may be chosen. For example, for \$s=2\$, any matrix with 0 and 1 in opposite corners and 2 and 3 in opposite corners is acceptable.
• Input and output may be in any convenient format.
• This is code-golf, so the shortest answer in bytes wins.

Answer 1

Python NumPy, 75 bytes

from numpy import*
f=lambda n:n and kron(c_[[0,3],[2,1]]-4j,1j-f(n-1)).imag

Attempt This Online!

How?

Recursively expands the pattern by "Kroneckering" it with the 2x2 template. The Kronecker product knows which of the inputs must come together in each cell of the output. Only, it takes the product where we want the sum.

In principle we could address this by exponentiating but that would be numerically unsound.

Instead we use a bit of complex number trickery. Principle:

Have a,b,times

Need a+b

Do (1+ai)x(1+bi) = 1-ab + (a+b)i and use imaginary part of result

Answer 2

Wolfram Language (Mathematica), 48 bytes

Nest[ArrayFlatten@{{4#,4#+2},{4#+3,4#+1}}&,0,#]&

Try it online!

Input is \$\log_2s\$, output is an integer matrix with entries starting from 0. Modified from the recursive formula on the Wikipedia page for ordered dithering: $$M_{2s}=\begin{bmatrix}4M_s&4M_s+2\\ 4M_s+3&4M_s+1 \end{bmatrix}$$

Answer 3

JavaScript (ES6), 87 bytes

Based on the recursive formula already pointed out by Parcly Taxel, but using a bitwise construction.

n=>[...Array(1<<n)].map((_,y,a)=>a.map(g=(k=n,x)=>k--&&4*g(k,x)|2*(x>>k)+3*(y>>k&1)&3))

Try it online!

How?

Given \$n\$, we build a square matrix of width \2ドル^n\$:

[...Array(1 << n)].map((_, y, a) =>
 a.map(
 ...
 )
)

We fill this matrix with a recursive callback function. Because the content of the array we iterate over is not initialized, \$k\$ is undefined on the first call and set to the default value \$n\$. The second argument \$x\$, on the other hand, is well defined right away.

g = (k = n, x) => // k = counter, x = horizontal position
 k-- && // decrement k; if it was not 0:
 4 * g(k, x) | // append 4 times the result of a recursive call
 2 * (x >> k) + // set bit #1 if the k-th bit of x is set
 3 * (y >> k & 1) // toggle bits #0 and #1 if the k-th bit of y is set
 & 3 // ignore the other bits

Answer 4

Python 3, 93 bytes (@alephalpha)

lambda n:[[g(x)/4+g(x^y)/2for y in range(n)]for x in range(n)]
g=lambda n:n and n%2+g(n//2)/4

Try it online! Link includes test cases. Takes the size of the matrix as input and returns binary fractions. Explanation: g takes the bits of n from LSB to MSB and interprets them as base 4 digits starting at the quaternary point e.g. 6 = 1102 => 0.114 = 0.3125 = 0.01012. One set of alternate bits depends only on the row while the other set depends on the bitwise XOR of the row and column; this is the equivalent to the 3* and 2* approach of the previous versions.

Previous 104-byte Python 3.8 answer (@xnor):

lambda n:[[2*(g:=lambda m:int(f"{m:0{n}b}"[::-1],4))(y)^3*g(x)for y in range(2**n)]for x in range(2**n)]

Try it online! Link includes test cases. Takes the power of 2 as input and outputs integers.

Previous (削除) 154 (削除ここまで) 116-byte Python 3 answer:

lambda n:[[2*g(y,n)^3*g(x,n)for y in range(2**n)]for x in range(2**n)]
g=lambda m,n:int(bin(m)[2:].zfill(n)[::-1],4)

Try it online! Link includes test cases. Takes the power of 2 as input and outputs integers. Explanation: Lots of bit twiddling.

First row of cells:

Col Bin Rev Val Binary
 0 000 000 0 000000
 1 001 100 32 100000
 2 010 010 8 001000
 3 011 110 40 101000
 4 100 001 2 000010
 5 101 101 34 100010
 6 110 011 10 001010
 7 111 111 42 101010

First column of cells:

Row Bin Rev Val Binary
 0 000 000 0 000000
 1 001 100 48 110000
 2 010 010 12 001100
 3 011 110 60 111100
 4 100 001 3 000011
 5 101 101 51 110011
 6 110 011 15 001111
 7 111 111 64 111111

Each cell is then the bitwise XOR of the first cell in its row and column.

• xnor: If you do Python 3.8+, you can save some bytes: Try it online
• alephalpha: 93 bytes taking \$s\$ and the output ranges from \0ドル\$ to \$\frac{s^2-1}{s^2}\$

Answer 5

Jelly, (削除) 20 (削除ここまで) (削除) 18 (削除ここまで) 14 bytes

ḶBUz0Zμ+Ḥ^þḤḅ4

Try it online!

-4 porting Neil's Python solution

Thought something that generates it flat then cuts the rows up at the end might be shorter, but I haven't actually gotten anything like that to work.

ḶB Binary digits of each [0 .. n).
 U Reverse each
 z0Z and right-pad with zeroes to the same length.
 μ+Ḥ Multiply each by 3,
 Ḥ multiply each by 2,
 ^þ table XOR,
 ḅ4 convert from base 4.

Answer 6

MATLAB/Octave, 72 bytes

function B=f(n),if n,S=f(n-1);B=[4*S,4*S+2;4*S+3,4*S+1];else,B=0;end,end

Try it online!

• ceilingcat: 64 bytes

Answer 7

05AB1E, 18 bytes

Ý ̈2вí0ζøxs3*δ^εε4β

Port of @Neil's previous Python answer.

Outputs the transposed result compared to the challenge description.

Try it online or verify all test cases or try it step-by-step.

Explanation:

Ý # Push a list in the range [0, (implicit) input]
 ̈ # Remove the last character to make the range [0,input)
 2в # Convert each integer to binary as lists
 í # Reverse each inner list
 0ζø # Right-pad each inner list with 0s:
 ζ # Zip/transpose; swapping rows/columns,
 0 # using 0 as filler character for unequal length rows
 ø # Then zip/transpose back
 x # Double each inner 1 (without popping the matrix)
 s # Swap so the matrix is at the top again
 3* # Multiply each 1 by 3
 δ # Apply double-vectorized using the two matrices:
 ^ # Bitwise-XOR them together
 ε # Then map over the list of matrices:
 ε # Map over each inner matrix:
 4β # Convert the current row-list from base-4 to an integer
 # (after which the resulting matrix is output implicitly)

Answer 8

Charcoal, (削除) 33 (削除ここまで) 29 bytes

NθI⊘EθEθ↨E⟦0λ⟧↨↨−|νι&νι2⊘⊘1⊘1

Try it online! Link is to verbose version of code. Takes the size of the matrix as input and outputs binary fractions. Explanation: Now uses @alephalpha's trick of converting from base 1⁄4 to reverse the bit pattern.

Nθ First input as a number
 θ Input number
 E Map over implicit range
 θ Input number
 E Map over implicit range
 ⟦ ⟧ List of
 0 Literal integer `0`
 λ Inner value
 E Map over list
 −|νι&νι Bitwise XOR with outer value
 ↨ 2 Convert to base `2`
 ↨ ⊘⊘1 Interpret as base `1⁄4`
 ↨ ⊘1 Interpret as base `1⁄2`
 ⊘ Vectorised halved
 I Cast to string
 Implicitly print

Previous 33-byte version:

×ばつ4υ≔+Eυ+κ+2κEυ++3κ⊕κυ»Iυ

Try it online! Link is to verbose version of code. Takes the power of 2 as input and outputs integers. Explanation: Another port of @ParclyTaxel's recursive formula.

⊞υ⟦0⟧

Start with a ×ばつ1 matrix for s=0.

FN«

Repeat s times.

×ばつ4υ

Multiply the matrix by 4. (Fortunately this function fully vectorises on the version of Charcoal on TIO.)

≔+Eυ+κ+2κEυ++3κ⊕κυ

Concatenate copies of the matrix with itself both horizontally and vertically, with each copy offset by a different integer from 0 to 3 appropriately.

»Iυ

Output the final matrix in Charcoal's default output format for matrices (each element on its own line and rows double-spaced from each other).

Answer 9

R, (削除) 65 (削除ここまで) 63 bytes

f=function(n)"if"(n,kronecker(matrix(4:1%%4,2),4*f(n-1),"+"),0)

Try it online!

-2 bytes thanks to pajonk.

Recursive function. Takes \$log_2(s)\$ as an input and returns the corresponding \$s\times s\$ matrix as output. 4 bytes shorter than using rbind and cbind.

R, 67 bytes

f=function(n)"if"(n,cbind(rbind(g<-4*f(n-1),g+3),rbind(g+2,g+1)),0)

Try it online!

• pajonk: Isn't c(0,3:1) same as 4:1%%4?
• Giuseppe: @pajonk yes it is! Thanks much.
• pajonk: 63 byte version of the second approach and I think this works for 62 bytes.

Answer 10

PARI/GP, 65 bytes

f(n)=matrix(2^n,,i,j,if(n,f(n-1)[-i\-2,-j\-2]+(i%2+j%2*2+1)%4))/4

Attempt This Online!

Takes \$\log_2(s)\$ and the output ranges from \0ドル\$ to \$\frac{s^2-1}{s^2}\$.

---

PARI/GP, 68 bytes

n->matrix(n,,i,j,g(i--,j--))
g(i,j)=if(k=i+j,i%2+k%2*2+g(i2,円j2円))/4

Attempt This Online!

Takes \$s\$ and the output ranges from \0ドル\$ to \$\frac{s^2-1}{s^2}\$.

---

PARI/GP, 69 bytes

f(n)=if(n,matconcat([m=4*f(n--),m+2*o=matrix(2^n,,i,j,1);m+3*o,m+o]))

Attempt This Online!

Takes \$\log_2(s)\$ and the output ranges from \0ドル\$ to \$s^2-1\$.

Answer 11

Nekomata, 18 bytes

r2B:o{d:-A2*+ç4£Ed

Attempt This Online!

Port of @Neil's Python answer. Takes \$s\$ and the output ranges from \0ドル\$ to \$\frac{s^2-1}{s^2}\$.

r2B:o{d:-A2*+ç4£Ed
r Range from 0 to s-1
 2B Convert to base 2. The least significant digit comes first.
 : Duplicate
 o{ Make a table with the following function
 d:- Take the difference between the two arguments
 A Absolute value
 2* Multiply by 2
 + Add the second argument
 ç Prepend 0
 4£Ed Convert from base 1/4

---

Nekomata, 21 bytes

0UU$ŋ{4*::3+,$→:→,ドルz,

Attempt This Online!

Port of @Parcly Taxel's Mathematica answer. Takes \$\log_2(s)\$ and the output ranges from \0ドル\$ to \$s^2-1\$.

0UU$ŋ{4*::3+,$→:→,ドルz,
0UU [[0]]
 $ŋ{ Apply the following function n times
 4* Multiply by 4
 : Duplicate
 : Duplicate
 3+ Add 3
 , Join
 $ Swap
 → Increment
 : Duplicate
 → Increment
 , Join
 z, Zip with join

• Neil: Oh, base ¼, very nice!

Answer 12

Java, (削除) 131 (削除ここまで) 129 bytes

n->{int d=1<<n,m[][]=new int[d][d],i=d*d,g,k;for(;i-->0;m[i/d][i%d]=g)for(g=k=0;k<n;)g=4*g|2*(i%d>>k)+3*(i/d>>k++&1)&3;return m;}

Port of @Arnauld's JavaScript answer, so will also output a \2ドル^n\$ by \2ドル^n\$ sized matrix based on the given \$n\$.
-2 bytes thanks to @ceilingcat.

Try it online.

Explanation:

n->{ // Method with integer parameter and int-matrix return-type
 int d=1<<n, // Integer `d`, set to 2 to the power `n`
 m[][]=new int[d][d], // Result-matrix, of size `d` by `d`
 i=d*d, // Index-integer, starting at `d` squared
 g,k; // Temp-integers, uninitialized
 for(;i-->0 // Loop `i` in the range (d*d,0], over all cells:
 ; // After every iteration:
 m[i/d][i%d]= // Set the [y,x]'th matrix-value to:
 g) // Value `g`
 for(g=k=0; // Reset both `g` and `k` to 0
 k<n;) // Inner loop `k` in the range [0,n):
 g= // Set `g` to:
 4*g| // Append 4 times the previous `g`;
 2*(i%d>>k)+ // Set bit #1 if the k'th bit of `x` is set
 3*(i/d>>k++&1) // Toggle bits #0 and #1 if the k'th bit of `y` is set
 // (and increase `k` by 1 afterwards with `k++`)
 &3; // Ignore the other bits
 return m;} // Return the resulting matrix after the loops

• Kevin Cruijssen: @ceilingcat Not sure why I even had those. :/ Probably when I was trying some shorter alternatives before. Thanks for noticing.

Answer 13

TI-Basic, (削除) 68 (削除ここまで) 60 bytes

Input N
identity(1→[A]
0Ans
For(I,1,N
4Ans
augment(augment(Ans,Ans+3[A])T,augment(Ans+2[A],Ans+[A])T→[A]
Fill(1,[A]
End
Ans

Takes input as \$log_2(s)\$.
-8 bytes thanks to MarcMush.

• Yousername: @MarcMush You're right; it is always stored in Ans after the third line, so it does not need to be stored in a separate variable.