13
\$\begingroup\$

Background

Page 219 of A New Kind of Science (a book by Stephen Wolfram, the creator of Mathematica) shows an interesting 2D pattern generated by constraints. The relevant section in the book starts at page 210; you can browse other pages for more context.

In short, the large binary image is the result generated by 12 constraints at the bottom, along with an extra condition that two black cells stacked vertically must appear somewhere on the grid. The constraints describe that, for every cell in the (infinite) pattern, the cell itself combined with its four neighbors must match one of the constraints given. The book describes this pattern as "the simplest system based on constraints that is forced to exhibit a non-repetitive pattern". An interesting fact is that the sequence of antidiagonals describes the binary pattern of all integers (including positive and negative).

Task

The task is to replicate a finite region at the center of this infinite pattern. For this task, the center of this pattern is defined to be the endpoint of the semi-infinite antidiagonal of black cells (which does not include the part of the upper-right stripes).

The input is a positive odd number \$n\$. You may choose to take the value of \$\left\lfloor \frac{n}{2}\right\rfloor\$ (0-based integers) or \$\left\lceil \frac{n}{2}\right\rceil\$ (1-based) instead.

The output is the square region of \$n \times n\$ cells centered at the center cell defined above. See test cases below for exact output. The output format is flexible; you may choose any two distinct values (numbers or chars) for black and white cells respectively, and any structure that exhibits the 2D grid is acceptable (e.g. nested arrays or strings delimited by newlines).

Standard rules apply. The shortest code in bytes wins.

Test cases

Uses X for black and . for white cells. Note that your program should (at least theoretically) give the correct pattern for arbitrarily large \$n\$.

n = 1
X

n = 3
.XX
.X.
X..

n = 7
.XXXXXX
.X.....
...XXXX
.X.X...
..X..XX
.X...X.
X......

n = 15
.XXXXXXXXXXXXXX
.X.............
...XXXXXXXXXXXX
.X.X...........
..X..XXXXXXXXXX
.X...X.........
.......XXXXXXXX
.X...X.X.......
..X...X..XXXXXX
...X.X...X.....
X...X......XXXX
.X.X.....X.X...
..X.......X..XX
.X.......X...X.
X..............

n = 25
X........................
..XXXXXXXXXXXXXXXXXXXXXXX
..X......................
....XXXXXXXXXXXXXXXXXXXXX
..X.X....................
...X..XXXXXXXXXXXXXXXXXXX
X.X...X..................
.X......XXXXXXXXXXXXXXXXX
X.....X.X................
.......X..XXXXXXXXXXXXXXX
X.....X...X..............
.X..........XXXXXXXXXXXXX
..X...X...X.X............
...X...X...X..XXXXXXXXXXX
X...X...X.X...X..........
.X...X...X......XXXXXXXXX
..X...X.X.....X.X........
...X...X.......X..XXXXXXX
X...X.X.......X...X......
.X...X..............XXXXX
..X.X.........X...X.X....
...X...........X...X..XXX
X.X.............X.X...X..
.X...............X......X
X...............X.....X.X
\$\endgroup\$

2 Answers 2

14
\$\begingroup\$

Python 3 with numpy, 90 87 86 84 bytes

from numpy import*
lambda n:2*((4<<(a:=(y:=c_[1-n:n])-y.T)//4)+a%4-2&a-2*y)-1<<a<y%2

Takes \$\left\lceil \frac{n}{2}\right\rceil\$.

-3 by removing x. -1 with a shorter expression for \$-x - y\$. -2 with a shorter combining method.

How it works

Broadcasting is used in several places to produce the table.

The bottom-left section

Change coordinates to \$a = -x + y\$ and \$b = -x - y\$, as shown here (\$a\$ blue, \$b\$ yellow):

Part of the pattern, with a,b coordinates

This part is handled by the subexpression (4<<(a:=(y:=c_[1-n:n])-y.T)//4)+a%4-2&a-2*y. (y.T produces \$x\$.)

Looking at the lines of constant nonnegative even \$a\$, their squares are black when certain bits of \$b\$ are zero, specifically (1x, 10x, 11x, 100x, 111x, 1000x, 1111x, ...) -- the low bit does not matter as it is always 0 in \$b\$ here. These values are produced by taking a power of 2 and adding 0 or -2; then bitwise-ANDing with \$b\$ yields 0 for black squares and nonzero values for white squares.

The lines of constant nonnegative odd \$a\$ are all white. To get this to work, since the low bit of \$b\$ is 1 here, we just need to make sure the low bit of the value ANDed with \$b\$ is 1.

The top-right section

Here, a square is black iff \$y\$ is odd, thus black iff y%2 is 1.

Combining the sections

Doubling the first part and subtracting 1 from it makes it negative for black squares and positive for white squares in the bottom-left section. In numpy arrays, shifting by a negative number produces zero, so <<a makes it zero in the top-right section while preserving its sign in the bottom-left section. Finally, it is less than y%2 iff it is negative (for a black square in the bottom-left section) or it is 0 and y%2 is 1 (for a black square in the top-right section).

\$\endgroup\$
3
\$\begingroup\$

Charcoal, 44 bytes

NθG↖→→↓↓θ¶XFθ«P↖⭆…⊕⁻ιθ⁻θι§ X¬&κ⁻X²⊕÷鲬﹪ι²←←

Try it online! Link is to verbose version of code. Takes input as the 1-indexed distance from the centre. Explanation: Diagonal bit-twiddling shamelessly stolen from @m90's answer, because I can't work out what @Bubbler means regarding the antidiagonals.

Nθ

Input ⌈n/2⌉.

G↖→→↓↓θ¶X

Draw alternate rows of Xs in the upper right triangle, leaving the cursor at the bottom right of the final diagram.

Fθ«

Loop through each diagonal of the lower right triangle.

P↖⭆…⊕⁻ιθ⁻θι§ X¬&κ⁻X²⊕÷鲬﹪ι²

Output Xs where the distance from the centre antidiagonal does not have the given bits.

←←

Move to the next diagonal.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.