4,494
edits
Rule 110: Difference between revisions
Jump to navigation
Jump to search
m
Text replacement - "<source" to "<syntaxhighlight"
(An implementation and explanation of rule 110) |
m (Text replacement - "<source" to "<syntaxhighlight") |
||
| (4 intermediate revisions by 3 users not shown) | |||
| Line 18: | Line 18: | ||
111: 0 | 111: 0 | ||
Rule 110 is so-called because the binary number 01101110 is 110 in | Rule 110 is so-called because the binary number 01101110 is 110 in decimal. | ||
== 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. | ||
< | <syntaxhighlight lang="apl"> | ||
⎕IO←0 | ⎕IO←0 | ||
</ | </syntaxhighlight> | ||
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. | ||
< | <syntaxhighlight lang="apl"> | ||
⌽110⊤⍨8⍴2 | ⌽110⊤⍨8⍴2 | ||
</ | </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. | ||
< | <syntaxhighlight lang="apl"> | ||
{(2⊥⍵)⌷⌽110⊤⍨8⍴2} | {(2⊥⍵)⌷⌽110⊤⍨8⍴2} | ||
</ | </syntaxhighlight> | ||
< | <syntaxhighlight lang="apl"> | ||
{(2⊥⍵)⌷⌽110⊤⍨8⍴2}0 0 0 | {(2⊥⍵)⌷⌽110⊤⍨8⍴2}0 0 0 | ||
0 | 0 | ||
| Line 49: | Line 49: | ||
0 | 0 | ||
etc... | etc... | ||
</ | </syntaxhighlight> | ||
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. | ||
< | <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> | ||
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. | ||
< | <syntaxhighlight lang="apl"> | ||
3 , /⍳10 | 3 , /⍳10 | ||
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐ | ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐ | ||
| Line 63: | Line 63: | ||
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘ | └─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘ | ||
</ | </syntaxhighlight> | ||
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! | ||
< | <syntaxhighlight lang="apl"> | ||
solve←{{(2⊥⍵)⌷⌽110⊤⍨8⍴2}¨3,/0,⍵,0} | solve←{{(2⊥⍵)⌷⌽110⊤⍨8⍴2}¨3,/0,⍵,0} | ||
</ | </syntaxhighlight> | ||
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. | 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 | 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. | ||
<syntaxhighlight lang="apl"> | |||
< | |||
gen←{(solve⍣⍵)⍺} | gen←{(solve⍣⍵)⍺} | ||
</ | </syntaxhighlight> | ||
And the grand finale... | And the grand finale... | ||
< | <syntaxhighlight lang="apl"> | ||
(board 10)∘gen¨⍳10 | (board 10)∘gen¨⍳10 | ||
┌─────────────────────┬─────────────────────┬─────────────────────┬─────────────────────┬─────────────────────┬─────────────────────┬─────────────────────┬─────────────────────┬─────────────────────┬─────────────────────┐ | ┌─────────────────────┬─────────────────────┬─────────────────────┬─────────────────────┬─────────────────────┬─────────────────────┬─────────────────────┬─────────────────────┬─────────────────────┬─────────────────────┐ | ||
| Line 86: | Line 84: | ||
└─────────────────────┴─────────────────────┴─────────────────────┴─────────────────────┴─────────────────────┴─────────────────────┴─────────────────────┴─────────────────────┴─────────────────────┴─────────────────────┘ | └─────────────────────┴─────────────────────┴─────────────────────┴─────────────────────┴─────────────────────┴─────────────────────┴─────────────────────┴─────────────────────┴─────────────────────┴─────────────────────┘ | ||
</ | </syntaxhighlight> | ||
It worked! kinda... | 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. | 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. | ||
< | <syntaxhighlight lang="apl"> | ||
10 1⍴(board 10)∘gen¨⍳10 | 10 1⍴(board 10)∘gen¨⍳10 | ||
┌─────────────────────┐ | ┌─────────────────────┐ | ||
| Line 113: | Line 111: | ||
│0 1 1 0 0 0 0 0 1 1 1│ | │0 1 1 0 0 0 0 0 1 1 1│ | ||
└─────────────────────┘ | └─────────────────────┘ | ||
</ | </syntaxhighlight> | ||
Let's put this all into one function... | Let's put this all into one function... | ||
< | <syntaxhighlight lang="apl"> | ||
rule110←{⍵ 1⍴(board ⍵)∘gen¨⍳⍵} | rule110←{⍵ 1⍴(board ⍵)∘gen¨⍳⍵} | ||
</ | </syntaxhighlight> | ||
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 | ||
< | <syntaxhighlight lang="apl"> | ||
↑{⍵⌷' *'}¨¨rule110 25 ⍝ "{⍵⌷' *'}" will only work with 0 index. | ↑{⍵⌷' *'}¨¨rule110 25 ⍝ "{⍵⌷' *'}" will only work with 0 index. | ||
* | * | ||
| Line 173: | Line 171: | ||
******* * *** ** * | ******* * *** ** * | ||
</ | </syntaxhighlight> | ||
Beautiful. | Beautiful. | ||
| Line 182: | Line 180: | ||
== Full solution == | == Full solution == | ||
< | <syntaxhighlight lang="apl"> | ||
⎕IO←0 | ⎕IO←0 | ||
solve←{{(2⊥⍵)⌷⌽110⊤⍨8⍴2}¨3,/0,⍵,0} | solve←{{(2⊥⍵)⌷⌽110⊤⍨8⍴2}¨3,/0,⍵,0} | ||
| Line 189: | Line 187: | ||
rule110←{⍵ 1⍴(board ⍵)∘gen¨⍳⍵} | rule110←{⍵ 1⍴(board ⍵)∘gen¨⍳⍵} | ||
↑{⍵⌷' *'}¨¨rule110 25 | ↑{⍵⌷' *'}¨¨rule110 25 | ||
</ | </syntaxhighlight> | ||
[[Category:Examples]] | |||