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 = 110₂ => 0.11₄ = 0.3125 = 0.0101₂. 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.

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!

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

ＮθＩ⊘ＥθＥθ↨Ｅ⟦⁰λ⟧↨↨⁻｜νι＆νι²⊘⊘¹⊘¹

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 ¼ to reverse the bit pattern.

Ｎθ                            First input as a number
     θ                        Input number
    Ｅ                         Map over implicit range
       θ                      Input number
      Ｅ                       Map over implicit range
          ⟦  ⟧                List of
           ⁰                  Literal integer `0`
            λ                 Inner value
         Ｅ                    Map over list
                ⁻｜νι＆νι       Bitwise XOR with outer value
               ↨       ²      Convert to base `2`
              ↨         ⊘⊘¹   Interpret as base `¼`
        ↨                  ⊘¹ Interpret as base `½`
   ⊘                          Vectorised halved
  Ｉ                           Cast to string
                              Implicitly print

Previous 33-byte version:

⊞υ⟦⁰⟧ＦＮ«≧×⁴υ≔⁺Ｅυ⁺κ⁺²κＥυ⁺⁺³κ⊕κυ»Ｉυ

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.

⊞υ⟦⁰⟧

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

ＦＮ«

Repeat s times.

≧×⁴υ

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

≔⁺Ｅυ⁺κ⁺²κＥυ⁺⁺³κ⊕κυ

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

»Ｉυ

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!

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(i\2,j\2))/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:ᵒ{ᵈ:-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:ᵒ{ᵈ:-A2*+ç4£Ed
r                      Range from 0 to s-1
 2B                    Convert to base 2. The least significant digit comes first.
   :                   Duplicate
    ᵒ{                 Make a table with the following function
      ᵈ:-                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+,$→:→$,ᶻ,

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+,$→:→$,ᶻ,
0UU                    [[0]]
   $ᵑ{                 Apply the following function n times
      4*                 Multiply by 4
        :                Duplicate
         :               Duplicate
          3+             Add 3
            ,            Join
             $           Swap
              →          Increment
               :         Duplicate
                →        Increment
                 ,       Join
                  ᶻ,     Zip with join

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

Answer 13

TI-Basic, 68 60 bytes

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

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