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.

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 — stevec, Commented Jun 1 at 17:02
+1 but I would suggest explaining the rule rather than linking externally. — Jonathan Allan, 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. — Arnauld, Commented Jun 2 at 8:52

z.. · Accepted Answer · 2024-06-01 17:37:25Z

10

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

answered Jun 1 at 17:37

z..

1,2411 gold badge1 silver badge11 bronze badges

Add a comment |

boothby · Accepted Answer · 2024-06-02 07:56:36Z

7

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)

answered Jun 2 at 7:56

boothby

9,9262 gold badges35 silver badges60 bronze badges

1

\$\begingroup\$ This gives a horizontally-mirrored output. You'd probably want to ask the OP if this is allowed. \$\endgroup\$
– Arnauld
Commented Jun 2 at 9:09
3

\$\begingroup\$ Fixed version (width and height also adjusted) \$\endgroup\$
– Arnauld
Commented Jun 2 at 15:46
\$\begingroup\$ Replacing l='.'*32 and l+='O'+l with l=f"{'O':.^63}" saves two bytes. \$\endgroup\$
– Jonathan Allan
Commented Jun 3 at 12:19

Add a comment |

Jonathan Allan · Accepted Answer · 2024-06-01 19:39:30Z

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

akamayu · Accepted Answer · 2024-06-10 03:38:30Z

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

edited Jun 10 at 3:38

answered Jun 2 at 17:48

akamayu

1,1451 silver badge7 bronze badges

Add a comment |

Jonathan Allan · Accepted Answer · 2024-06-04 16:11:06Z

3

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.

edited Jun 4 at 16:11

answered Jun 3 at 20:12

Jonathan Allan

110k7 gold badges65 silver badges282 bronze badges

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

Add a comment |

Graham · Accepted Answer · 2024-06-01 18:20:41Z

2

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

answered Jun 1 at 18:20

Graham

6,8461 gold badge15 silver badges11 bronze badges

Add a comment |

Arnauld · Accepted Answer · 2024-06-02 23:07:01Z

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!

Neil · Accepted Answer · 2024-06-03 07:42:18Z

2

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.

edited Jun 3 at 7:42

answered Jun 2 at 8:55

Neil

177k12 gold badges74 silver badges281 bronze badges

Add a comment |

Kevin Cruijssen · Accepted Answer · 2024-06-03 08:35:54Z

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)

Jan Blumschein · Accepted Answer · 2024-06-05 21:17:02Z

2

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!

answered Jun 5 at 21:17

Jan Blumschein

2012 bronze badges

Add a comment |

Neil · Accepted Answer · 2024-06-01 21:52:40Z

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.

Xcali · Accepted Answer · 2024-06-03 17:08:35Z

1

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!

answered Jun 3 at 17:08

Xcali

16.2k2 gold badges15 silver badges39 bronze badges

Add a comment |

Greg Martin · Accepted Answer · 2024-06-03 17:35:04Z

1

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.

edited Jun 3 at 17:35

answered Jun 3 at 17:09

Greg Martin

16.2k4 gold badges21 silver badges72 bronze badges

1

\$\begingroup\$ Maybe add a non-builtin golf? (It might even beat this?!) \$\endgroup\$
– Jonathan Allan
Commented Jun 3 at 19:15
\$\begingroup\$ Someone's welcome to do that :) \$\endgroup\$
– Greg Martin
Commented Jun 3 at 22:49

Add a comment |

Stack Exchange Network

Cellular Automata Rule 30

What are cellular automata?

What is 'Rule 30'?

Challenge

13 Answers 13

Google Sheets, 171 bytes

Python, 100 byes

Jelly, 22 21 bytes

How?

K (ngn/k), 36 34 bytes

Python 3, 88 87 bytes

APL+WIN, 120 bytes

JavaScript (ES11), 84 bytes

Method

Notes

Retina 0.8.2, 100 69 bytes

05AB1E, 29 25 bytes

sed, 110 bytes

Charcoal, 32 bytes

Perl 5, 105 bytes

Wolfram Language (Mathematica), 71 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
ascii-art
kolmogorov-complexity
cellular-automata
or ask your own question.

Linked

Hot Network Questions

Cellular Automata Rule 30

What are cellular automata?

What is 'Rule 30'?

Challenge

13 Answers 13

Google Sheets, 171 bytes

Python, 100 byes

Jelly, 22 21 bytes

How?

K (ngn/k), 36 34 bytes

Python 3, 88 87 bytes

APL+WIN, 120 bytes

JavaScript (ES11), 84 bytes

Method

Notes

Retina 0.8.2, 100 69 bytes

05AB1E, 29 25 bytes

sed, 110 bytes

Charcoal, 32 bytes

Perl 5, 105 bytes

Wolfram Language (Mathematica), 71 bytes

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golfascii-artkolmogorov-complexitycellular-automata or ask your own question.

Linked

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
code-golf
ascii-art
kolmogorov-complexity
cellular-automata
or ask your own question.