Rule 110
Basic summary
Rule 110 is one of the Wolfram cellular automaton. It is a 1 dimensional automata and has rules on whether a cell stays alive or not, based on its surroundings (similar to Conway's Game of Life). A cell has 2 states, alive or dead which can be represented in binary. The way it calculates the next generation is it goes through each cell and looks at the neighbor to the left of it, the cell itself, and the neighbor to the right of it. This forms a binary number which can be looked at in a binary table. The rules are as follows:
000: 0
001: 1
010: 1
011: 1
100: 0
101: 1
110: 1
111: 0
Rule 110 is so-called because the binary number 01101110 is 110 in decimal.
Implementation
Since we will be using binary numbers to index arrays, it is more convenient for us to have arrays start at 0.
⎕IO←0
The lookup table can be created by simply converting the decimal number 110 into binary and flipping it.
⌽110⊤⍨8⍴2
A function that takes the three cells as an argument can then easily be implemented by converting it into a decimal number and indexing that number in the table.
{(2⊥⍵)⌷⌽110⊤⍨8⍴2}
{(2⊥⍵)⌷⌽110⊤⍨8⍴2}0 0 0
0
{(2⊥⍵)⌷⌽110⊤⍨8⍴2}0 0 1
1
{(2⊥⍵)⌷⌽110⊤⍨8⍴2}0 1 0
1
{(2⊥⍵)⌷⌽110⊤⍨8⍴2}0 1 1
1
{(2⊥⍵)⌷⌽110⊤⍨8⍴2}1 0 0
0
etc...
But how are we going to iterate over an entire board? Well, it would be useful to have a function that would generate us a board first.
board←{1,⍨⍵⍴0} ⍝ this function creates an array full of 0s with a 1 at the end.
APL has an interesting function that lets you operate over a small window of your choice.
3 , /⍳10 ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐ │0 1 2│1 2 3│2 3 4│3 4 5│4 5 6│5 6 7│6 7 8│7 8 9│ └─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
Wait! Eureka! That is exactly what we want! A 3 cell sized window!
solve←{{(2⊥⍵)⌷⌽110⊤⍨8⍴2}¨3,/0,⍵,0}
I did gloss over an important step, which is to pad the array with a 0 on both sides. This is because any cell that exceeds the bounds is considered dead no matter what, so we need to tell this explicitly to APL.
Anyway, now we have a solve function that can calculate the next generation given an array of any size. Now all we need to do is implement a function that can give you a specific generation.
gen←{(solve⍣⍵)⍺}
And the grand finale...
(board 10)∘gen¨⍳10 ┌─────────────────────┬─────────────────────┬─────────────────────┬─────────────────────┬─────────────────────┬─────────────────────┬─────────────────────┬─────────────────────┬─────────────────────┬─────────────────────┐ │0 0 0 0 0 0 0 0 0 0 1│0 0 0 0 0 0 0 0 0 1 1│0 0 0 0 0 0 0 0 1 1 1│0 0 0 0 0 0 0 1 1 0 1│0 0 0 0 0 0 1 1 1 1 1│0 0 0 0 0 1 1 0 0 0 1│0 0 0 0 1 1 1 0 0 1 1│0 0 0 1 1 0 1 0 1 1 1│0 0 1 1 1 1 1 1 1 0 1│0 1 1 0 0 0 0 0 1 1 1│ └─────────────────────┴─────────────────────┴─────────────────────┴─────────────────────┴─────────────────────┴─────────────────────┴─────────────────────┴─────────────────────┴─────────────────────┴─────────────────────┘
It worked! kinda...
It printed all of the generations on one line, which is still a solution but not at all pretty. Luckily, we can reshape the array to go down not across.
10 1⍴(board 10)∘gen¨⍳10 ┌─────────────────────┐ │0 0 0 0 0 0 0 0 0 0 1│ ├─────────────────────┤ │0 0 0 0 0 0 0 0 0 1 1│ ├─────────────────────┤ │0 0 0 0 0 0 0 0 1 1 1│ ├─────────────────────┤ │0 0 0 0 0 0 0 1 1 0 1│ ├─────────────────────┤ │0 0 0 0 0 0 1 1 1 1 1│ ├─────────────────────┤ │0 0 0 0 0 1 1 0 0 0 1│ ├─────────────────────┤ │0 0 0 0 1 1 1 0 0 1 1│ ├─────────────────────┤ │0 0 0 1 1 0 1 0 1 1 1│ ├─────────────────────┤ │0 0 1 1 1 1 1 1 1 0 1│ ├─────────────────────┤ │0 1 1 0 0 0 0 0 1 1 1│ └─────────────────────┘
Let's put this all into one function...
rule110←{⍵ 1⍴(board ⍵)∘gen¨⍳⍵}
And just for fun, let's use * for a 1 and a space for a 0
↑{⍵⌷' *'}¨¨rule110 25 ⍝ "{⍵⌷' *'}" will only work with 0 index.
*
**
***
** *
*****
** *
*** **
** * ***
******* *
** ***
*** ** *
** * *****
***** ** *
** * *** **
*** **** * ***
** * ** ***** *
******** ** ***
** **** ** *
*** ** * *****
** * *** **** *
***** ** *** * **
** * ***** * ** ***
*** ** ** ******** *
** * ****** ** ***
******* * *** ** *
Beautiful.
Closing notes
This is another demonstration of the power of APL, as we have done in 6 lines what normal languages do in 20. It is also a proof that APL is Turing complete, since programs which are not fail to simulate this automata. To be honest, I was surprised that this article hadn't already been made.
Full solution
⎕IO←0
solve←{{(2⊥⍵)⌷⌽110⊤⍨8⍴2}¨3,/0,⍵,0}
board←{1,⍨⍵⍴0}
gen←{(solve⍣⍵)⍺}
rule110←{⍵ 1⍴(board ⍵)∘gen¨⍳⍵}
↑{⍵⌷' *'}¨¨rule110 25