Cellular Automata Rule 30

Question

What are cellular automata?

Cellular automata describes a broad category of computational models that covers various cellular automations, some of the most intriguing of which involve 'simple' rules in a 'simple' space (often 1 dimensional or 2 dimensional grid), but from which intricate complexity occasionally arises.

enter image description here

What is 'Rule 30'?

Rule 30 is a particularly special automation because it demonstrates complexity arising from simple rules, chaos and randomness, and is computationally irreducible (i.e. the fastest way to find out what any cell or line will look like after many generations is simply to run the automaton).

It's also Stephen Wolfram's favourite discovery:

Today my all-time favorite science discovery is 40 yrs old! My June 1, 1984 diary told me to "take pict." of "R30" on a 9 pm flight to London ... which is when I finally realized (2 yrs after first generating it) what a big deal rule 30 is...

Further explanation of rule 30.

Challenge

The goal is to generate the first 32 lines of cellular automata rule 30 as represented in ASCII (well, O's and .'s) as per this slightly modified example found on its wikipedia page:

...............................O...............................
..............................OOO..............................
.............................OO..O.............................
............................OO.OOOO............................
...........................OO..O...O...........................
..........................OO.OOOO.OOO..........................
.........................OO..O....O..O.........................
........................OO.OOOO..OOOOOO........................
.......................OO..O...OOO.....O.......................
......................OO.OOOO.OO..O...OOO......................
.....................OO..O....O.OOOO.OO..O.....................
....................OO.OOOO..OO.O....O.OOOO....................
...................OO..O...OOO..OO..OO.O...O...................
..................OO.OOOO.OO..OOO.OOO..OO.OOO..................
.................OO..O....O.OOO...O..OOO..O..O.................
................OO.OOOO..OO.O..O.OOOOO..OOOOOOO................
...............OO..O...OOO..OOOO.O....OOO......O...............
..............OO.OOOO.OO..OOO....OO..OO..O....OOO..............
.............OO..O....O.OOO..O..OO.OOO.OOOO..OO..O.............
............OO.OOOO..OO.O..OOOOOO..O...O...OOO.OOOO............
...........OO..O...OOO..OOOO.....OOOO.OOO.OO...O...O...........
..........OO.OOOO.OO..OOO...O...OO....O...O.O.OOO.OOO..........
.........OO..O....O.OOO..O.OOO.OO.O..OOO.OO.O.O...O..O.........
........OO.OOOO..OO.O..OOO.O...O..OOOO...O..O.OO.OOOOOO........
.......OO..O...OOO..OOOO...OO.OOOOO...O.OOOOO.O..O.....O.......
......OO.OOOO.OO..OOO...O.OO..O....O.OO.O.....OOOOO...OOO......
.....OO..O....O.OOO..O.OO.O.OOOO..OO.O..OO...OO....O.OO..O.....
....OO.OOOO..OO.O..OOO.O..O.O...OOO..OOOO.O.OO.O..OO.O.OOOO....
...OO..O...OOO..OOOO...OOOO.OO.OO..OOO....O.O..OOOO..O.O...O...
..OO.OOOO.OO..OOO...O.OO....O..O.OOO..O..OO.OOOO...OOO.OO.OOO..
.OO..O....O.OOO..O.OO.O.O..OOOOO.O..OOOOOO..O...O.OO...O..O..O.
OO.OOOO..OO.O..OOO.O..O.OOOO.....OOOO.....OOOO.OO.O.O.OOOOOOOOO

Note: this may be a duplicate (or subset of) this previous challenge.

• stevec: @Arnauld great catch (I hadn't noticed it). I think it's conventional not to include any empty column(s) (I suspect Wikipedia added it for visual clarity). I will remove it in the question. I think that's best
• Jonathan Allan: +1 but I would suggest explaining the rule rather than linking externally.
• Arnauld: Sorry, I didn't notice you added a link to my (now deleted) comment in the challenge. Generally speaking, we require challenges to be self-contained. So you should avoid links to external and/or temporary content.

Answer 1

Google Sheets, 171 bytes

=LET(o,"O",r,REPT(".",31),a,r&o&r,{a;SCAN(a,Z1:Z31,LAMBDA(a,_,JOIN(,MAP(SEQUENCE(63),LAMBDA(i,IF(XOR(IFERROR(MID(a,i-1,1))=o,OR(MID(a,i,1)=o,MID(a,i+1,1)=o)),o,"."))))))})

enter image description here

Answer 2

Python, 100 byes

l='.'*32
l+='O'+l
exec("print(l);l=''.join('.O'[f'.{l}.'[i:i+3]in'OO..O.']for i in range(65));"*33)

• Arnauld: This gives a horizontally-mirrored output. You'd probably want to ask the OP if this is allowed.
• Arnauld: Fixed version (width and height also adjusted)
• Jonathan Allan: Replacing l='.'*32 and l+='O'+l with l=f"{'O':.^63}" saves two bytes.

Answer 3

Jelly, (削除) 22 (削除ここまで) 21 bytes

32ṬŒḄØ0jḢ−ṀƊ3ƤƊƬḣị)O.

A niladic Link that yields a list of lines.

Try it online!

How?

32ṬŒḄØ0jḢ−ṀƊ3ƤƊƬḣị)O. - Link: no arguments
32 - set the left argument to 32
 Ṭ - untruth -> [0,0,...,0,1] (31 zeros and a one)
 ŒḄ - bounce -> [0,0,...,0,1,0,...,0,0] (the top line)
 Ƭ - collect while distinct, applying:
 Ɗ - last three links as a monad - f(Line):
 Ø0 - literal [0,0]
 j - join with {Line} (wrap the Line with zeros)
 3Ƥ - for overlapping infixes of length three:
 Ɗ - last three links as a monad - f([a,b,c]):
 Ḣ - head and yield {[a,b,c]} -> a
 Ṁ - max {[b,c]} -> M
 − - {a} not equal? {M}
 ḣ - head to index {32} -> first 32 lines
 ị)O. - index into "O."

Possible triples and their new state:

a	b	c	max(b,c) -> M	a != M -> New State
0	0	0	0	0
0	0	1	1	1
0	1	0	1	1
0	1	1	1	1
1	0	0	0	1
1	0	1	1	0
1	1	0	1	0
1	1	1	1	0

Answer 4

K (ngn/k), (削除) 36 (削除ここまで) 34 bytes

-2 bytes thanks to @Jonathan Allan's bit table

".O"@31{~{x=y|z}.+3':0,x,0}31円=!63

Try it online!

 31=!63 /0 0 0 ... 0 1 0 ... 0 0 0 
 { 3':0,x,0} /3-wise windowed bits
 {~{x=y|z}.+ } /the next iteration in Rule 30
 31{ }\ /apply function repeatedly for 31 times
 / and collect intermediate results
".O"@ /index into ".O"

36 bytes

Answer 5

Python 3, (削除) 88 (削除ここまで) 87 bytes

-1 thanks to Jitse! (Reverse the order, strip leading character at each step to avoid some slice offsets.)

I started with boothby,'s answer and tweaked quite a bit...

s=f"..{'O':.^63}"
i=2048
while i:i%64or print(s[2:]);s=s[1:]+'.O'[s[:3]in'.O..OO'];i-=1

A full program that takes no arguments and prints the first thirty-two states as prescribed.

Try it online! Or check it.

• Jitse: 87 bytes
• Jonathan Allan: Thanks @Jitse that's great! I had tried striping chars but never got to less, I'm not sure what mistake I made there.

Answer 6

APL+WIN, 120 bytes

m←32 63⍴0
m[0;62]←1
:for i :in 1+⍳31
n←m[i-1;]
:for j :in ⍳63
m[i;j]←(↑v)≠(↑1↓v)∨ ̄1↑v←3↑n
n←1↓n
:end
:end
'.o'[(⌽⍳32)⌽m]

Try it online! Thanks to Dyalog Classic

Answer 7

JavaScript (ES11), 84 bytes

f=(r=1n<<32n,k,q=r>>62n&7n)=>k^63?"._O"[q&2n]+f(r+r|30n>>q&1n,-~k):q>1?"":`
`+f(r+r)

Try it online!

Method

At each iteration:

• the bit at position 63 in the bitmask r is read to figure out the next output character
• the bits at positions 62, 63 and 64 are turned into a new bit according to rule 30
• the bitmask is left-shifted and the new bit is inserted at position 0

We stop when we reach the end of a row and bit #63 is set.

Notes

Because we shift to the left and the bitmask is never cleared, it keeps growing up and eventually reaches a size of 2080 bits.

Another way to get the same result is to use rule 86 (a horizontally-mirrored version of rule 30) and shift the bitmask to the right:

85 bytes

f=(r=1n<<32n,k)=>k^63?"._O"[r&2n]+f(r/2n|(86n>>r%8n&1n)<<64n,-~k):r&1n?"":`
`+f(r/2n)

Try it online!

Answer 8

Retina 0.8.2, (削除) 100 (削除ここまで) 69 bytes

2080$*.
M!`.{65}
33=`.
0
+s`.(?<=(0\.\.|\.0.|\..0).{65})
0
.(.+).
1ドル

Try it online! Explanation:

2080$*.

Insert 2080 .s.

M!`.{65}

Split it into 32 lines of 65 ..

33=`.
0

Change the middle . on the first line to a 0.

+`

Repeat the following change until no more .s can be changed into 0s.

s`.(?<=(0\.\.|\.0.|\..0).{65})
0

Change all .s to 0s if there is either 0.., .00, .0. or ..0 on the line above.

.(.+).
1ドル

Remove the left and right columns.

Answer 9

05AB1E, (削除) 29 (削除ここまで) 25 bytes

31°ÂûsvJDT„O.‡,0.øü3εćsàÊ

-4 bytes porting @JonathanAllan's Jelly answer.

Try it online.

Explanation:

31° # Push 10 to the power 31
 Â # Bifurcate it; short for Duplicate & Reverse copy
 û # Palindromize this reversed copy
sv # Swap and foreach-loop; aka loop 32 times:
 J # Join the current list (from 2nd iteration onward) to a string
 D # Duplicate this string of 0s/1s
 T„O.‡ # Transliterate "10" to "O." in this copy
 , # Pop and output it with trailing newline
 0.ø # Surround the current line with trailing/leading 0
 ü3 # Pop and convert it into overlapping triplets
 ε # Map over each triplet:
 ć # Head extracted (abc → bc,a)
 s # Swap so the remainder (bc) is at the top
 à # Pop and get the maximum digit of this pair
 Ê # Check that it's NOT equal to the head: a != max(b,c)

Answer 10

sed, 110 bytes

:0
p
/^O/b
y/.O/_x/
s/.*/_&_/
:1
s/[_x]/&:/
/:__/s/:/_:/
//!s/:/x:/
s/(.)1円:/./
s/..:/O/
/[_x]../b1
s/..$//
b0

Try it online!

Answer 11

Charcoal, 32 bytes

×ばつ31ψ0F31«⸿F63c/o↔−c/o§KM0c/o⌈✂KM1¦3

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

UB.

Set the "background", which is anywhere where the null character or no character all is printed, to ..

×ばつ31ψ0

Write a 0 in the 32nd column in the canvas.

F31«

Repeat for each of the remaining 31 rows.

⸿

Start at the beginning of the next line.

F63

Repeat for each of the 63 columns.

c/o↔−c/o§KM0c/o⌈✂KM1¦3

Peek the cells adjacent to the current cell. Using @JonathanAllan's formula, take the absolute difference of the ordinal of the cell above and to the left (a in his formula) with the ordinal of the maximum of the cells above (b) and above and to the right (c), and output the character with that ordinal.

When the two values are equal, i.e. either all three cells are empty or a has a 0 and at least one of b and c have a 0, then the result is zero, and a null character is written, which is then considered to be part of the background, while if the two values are different then one will be a 0 and the other will not, and the absolute difference of the ordinals will be the ordinal of 0 and that will be output.

33 bytes using the actual definition of the rule:

×ばつ31ψ0F31«⸿F63§+ψ0÷30X2⍘...KM3+ψ0

Attempt This Online! Link is to verbose version of code. Needs to use ATO instead of TIO because AtIndex is broken on TIO. Explanation: As above but decodes the presence of the cells in the row above using a custom base, right-shifts 30 by that amount, then outputs the presence according to the LSB.

Answer 12

Perl 5, 105 bytes

@a=(0)x63;$a[31]=1;for$z(1..32){say map$_?O:".",@a;@a=map{($b=join'',@a[$_-1..$_+1])<101&&$b>0||0}0..$#a}

Try it online!

Answer 13

Wolfram Language (Mathematica), 71 bytes

StringRiffle[CellularAutomaton[30,{{1},0},31]/.{1->"1",0->"."},"\n",""]

Try it online! A code snippet that produces a string.

Gotta have the OG in the house. Note the 30 in this code is precisely why this cellular automaton is called Rule 30! See the CellularAutomaton documentation for how it encodes the rule of evolution.

• Jonathan Allan: Maybe add a non-builtin golf? (It might even beat this?!)
• Greg Martin: Someone's welcome to do that :)