# Cellular Automata Rule 30

### 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.

### 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.

• @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 Commented Jun 1 at 17:02
• +1 but I would suggest explaining the rule rather than linking externally. Commented Jun 1 at 18:56
• 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. Commented Jun 2 at 8:52

=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,"."))))))})


# 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)

• This gives a horizontally-mirrored output. You'd probably want to ask the OP if this is allowed. Commented Jun 2 at 9:09
• Fixed version (width and height also adjusted) Commented Jun 2 at 15:46
• Replacing l='.'*32 and l+='O'+l with l=f"{'O':.^63}" saves two bytes. Commented Jun 3 at 12:19

# Jelly,  22  21 bytes

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


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:
Ø0               -     literal [0,0]
j              -     join with {Line} (wrap the Line with zeros)
3Ƥ        -     for overlapping infixes of length three:
Ḣ             -         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

# 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

# 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.

• 87 bytes Commented Jun 4 at 11:55
• Thanks @Jitse that's great! I had tried striping chars but never got to less, I'm not sure what mistake I made there. Commented Jun 4 at 16:15

# 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

# 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!

# 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.

# 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)


# 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! # Charcoal, 32 bytes ＵＢ.×³¹ψ0Ｆ³¹«⸿Ｆ⁶³℅↔⁻℅§ＫＭ⁰℅⌈✂ＫＭ¹¦³  Try it online! Link is to verbose version of code. Explanation: ＵＢ.  Set the "background", which is anywhere where the null character or no character all is printed, to .. ×³¹ψ0  Write a 0 in the 32nd column in the canvas. Ｆ³¹«  Repeat for each of the remaining 31 rows. ⸿  Start at the beginning of the next line. Ｆ⁶³  Repeat for each of the 63 columns. ℅↔⁻℅§ＫＭ⁰℅⌈✂ＫＭ¹¦³  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: ＵＢ.×³¹ψ0Ｆ³¹«⸿Ｆ⁶³§⁺ψ0÷³⁰Ｘ²⍘…ＫＭ³⁺ψ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. # 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!

# 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.

• Maybe add a non-builtin golf? (It might even beat this?!) Commented Jun 3 at 19:15
• Someone's welcome to do that :) Commented Jun 3 at 22:49