Rule 110: Difference between revisions

From APL Wiki
Jump to navigation Jump to search
m (Text replacement - "</source>" to "</syntaxhighlight>")
m (Text replacement - "<source" to "<syntaxhighlight")
 
Line 22: Line 22:
== Implementation ==
== Implementation ==
Since we will be using binary numbers to index arrays, it is more convenient for us to have arrays start at 0.
Since we will be using binary numbers to index arrays, it is more convenient for us to have arrays start at 0.
<source lang="apl">
<syntaxhighlight lang="apl">
⎕IO←0
⎕IO←0
</syntaxhighlight>
</syntaxhighlight>
Line 28: Line 28:
The lookup table can be created by simply converting the decimal number 110 into binary and flipping it.
The lookup table can be created by simply converting the decimal number 110 into binary and flipping it.


<source lang="apl">
<syntaxhighlight lang="apl">
⌽110⊤⍨8⍴2
⌽110⊤⍨8⍴2
</syntaxhighlight>
</syntaxhighlight>


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.
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.
<source lang="apl">
<syntaxhighlight lang="apl">
{(2⊥⍵)⌷⌽110⊤⍨8⍴2}
{(2⊥⍵)⌷⌽110⊤⍨8⍴2}
</syntaxhighlight>
</syntaxhighlight>


<source lang="apl">
<syntaxhighlight lang="apl">
       {(2⊥⍵)⌷⌽110⊤⍨8⍴2}0 0 0
       {(2⊥⍵)⌷⌽110⊤⍨8⍴2}0 0 0
0
0
Line 52: Line 52:


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.
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.
<source lang="apl">
<syntaxhighlight lang="apl">
board←{1,⍨⍵⍴0} ⍝ this function creates an array full of 0s with a 1 at the end.
board←{1,⍨⍵⍴0} ⍝ this function creates an array full of 0s with a 1 at the end.
</syntaxhighlight>
</syntaxhighlight>


APL has an interesting function that lets you operate over a small window of your choice.
APL has an interesting function that lets you operate over a small window of your choice.
<source lang="apl">
<syntaxhighlight lang="apl">
       3 , /⍳10
       3 , /⍳10
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
Line 67: Line 67:
Wait! Eureka! That is exactly what we want! A 3 cell sized window!
Wait! Eureka! That is exactly what we want! A 3 cell sized window!


<source lang="apl">
<syntaxhighlight lang="apl">
solve←{{(2⊥⍵)⌷⌽110⊤⍨8⍴2}¨3,/0,⍵,0}
solve←{{(2⊥⍵)⌷⌽110⊤⍨8⍴2}¨3,/0,⍵,0}
</syntaxhighlight>
</syntaxhighlight>
Line 73: Line 73:


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.
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.
<source lang="apl">
<syntaxhighlight lang="apl">
gen←{(solve⍣⍵)⍺}
gen←{(solve⍣⍵)⍺}
</syntaxhighlight>
</syntaxhighlight>
And the grand finale...
And the grand finale...


<source lang="apl">
<syntaxhighlight lang="apl">
(board 10)∘gen¨⍳10
(board 10)∘gen¨⍳10
┌─────────────────────┬─────────────────────┬─────────────────────┬─────────────────────┬─────────────────────┬─────────────────────┬─────────────────────┬─────────────────────┬─────────────────────┬─────────────────────┐
┌─────────────────────┬─────────────────────┬─────────────────────┬─────────────────────┬─────────────────────┬─────────────────────┬─────────────────────┬─────────────────────┬─────────────────────┬─────────────────────┐
Line 88: Line 88:


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.
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.
<source lang="apl">
<syntaxhighlight lang="apl">
       10 1⍴(board 10)∘gen¨⍳10
       10 1⍴(board 10)∘gen¨⍳10
┌─────────────────────┐
┌─────────────────────┐
Line 114: Line 114:


Let's put this all into one function...
Let's put this all into one function...
<source lang="apl">
<syntaxhighlight lang="apl">
rule110←{⍵ 1⍴(board ⍵)∘gen¨⍳⍵}
rule110←{⍵ 1⍴(board ⍵)∘gen¨⍳⍵}
</syntaxhighlight>
</syntaxhighlight>
Line 120: Line 120:
And just for fun, let's use * for a 1 and a space for a 0
And just for fun, let's use * for a 1 and a space for a 0


<source lang="apl">
<syntaxhighlight lang="apl">
       ↑{⍵⌷' *'}¨¨rule110 25 ⍝ "{⍵⌷' *'}" will only work with 0 index.
       ↑{⍵⌷' *'}¨¨rule110 25 ⍝ "{⍵⌷' *'}" will only work with 0 index.
                         *
                         *
Line 180: Line 180:


== Full solution ==
== Full solution ==
<source lang="apl">
<syntaxhighlight lang="apl">
⎕IO←0
⎕IO←0
solve←{{(2⊥⍵)⌷⌽110⊤⍨8⍴2}¨3,/0,⍵,0}
solve←{{(2⊥⍵)⌷⌽110⊤⍨8⍴2}¨3,/0,⍵,0}

Latest revision as of 22:09, 10 September 2022

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