## Cellular Automata

### May 15, 2009

A cellular automaton is a collection of cells arranged in an infinite grid, controlled by a clock, with each cell coloring itself at each tick of the clock based on the state of its neighboring cells. A linear cellular automaton has all the cells of the grid arranged in a single line. A time-lapse picture of a linear cellular automaton shows a two-dimensional grid with the automaton as a horizontal line, the state of the automaton at each clock tick flowing down the page.

For the elementary cellular automata that we will study, each cell may be either of two colors, black or white, and a cell’s neighborhood consists of itself and the two cells on either side. With two colors and three neighbors, there are 23=8 states and 28=256 possible rules for advancing from one state to the next.

Rules are specified using a kind of binary notation; for each of the eight states 111, 110, 101, 100, 011, 010, 001, and 000, where 1 is black and 0 is white and the neighbors are arranged left-to-right on the line. Then the rule is specified by the binary number corresponding to the eight successor states of each of the eight neighbors, so for instance rule 30 = 000111102 maps 111 to 0, 110 to 0, 101 to 0, 100 to 1, 011 to 1, 010 to 1, 001 to 1, and 000 to 0.

For example, the first 12 rows of the rule 158 automaton applied to a row containing a single black cell are shown below:

```                        X                       X X X                     X X X   X                   X X X     X X                 X X X   X X X   X               X X X     X X     X X             X X X   X X X   X X X   X           X X X     X X     X X     X X         X X X   X X X   X X X   X X X   X       X X X     X X     X X     X X     X X     X X X   X X X   X X X   X X X   X X X   X   X X X     X X     X X     X X     X X     X X X X X   X X X   X X X   X X X   X X X   X X X   X```

You can see more examples at http://mathworld.wolfram.com/ElementaryCellularAutomaton.html.

Your task is to write a function that draws the result of applying a given rule to a given number of rows, starting from a row with a single black cell. When you are finished, you are welcome to read or run a suggested solution, or post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 9 Responses to “Cellular Automata”

1. […] Praxis – Cellular Automata By Remco Niemeijer Today’s Programming Praxis problem is about cellular automata. Let’s dive […]

2. Remco Niemeijer said

```import Data.Bits
import Data.List

successor :: Int -> [Bool] -> Bool
successor r bs = testBit r . sum \$
zipWith (shiftL . fromEnum) (reverse bs) [0..]

nextRow :: Int -> [Bool] -> [Bool]
nextRow r cs = map (successor r) . take (length cs) . transpose .
take 3 . iterate (drop 1) \$ [head cs] ++ cs ++ [last cs]

displayRow :: [Bool] -> String
displayRow = intersperse ' ' . map (\b -> if b then 'X' else ' ')

cells :: Int -> Int -> [String]
cells r h = map displayRow . take (h + 1) . iterate (nextRow r) \$
replicate h False ++ [True] ++ replicate h False

main :: IO ()
main = mapM_ putStrLn \$ cells 82 15
```
3. ardnew said

There may be a little bit of confusion with the example rule 158 generations you provide. There are 13 lines listed there, not 12.

4. ardnew said

Nevermind, I was misreading the text :)

5. ardnew said

Anyway, here’s my crappy solution: link

6. […] generator that is used in the Standard Prelude. We also looked at cellular automata in a previous exercise. In today’s exercise we combine random number generators and cellular automata by looking at […]

7. Devdhar said

MY SOLUTION :(U CAN SET NO OF GENERATIONS AND RULE NO.):

#include
using namespace std;
void binRev(int n,int arr[])
{
int i=0;
while(n>0)
{
arr[i++]=(n%2);
n=n/2;
}
}
void print(int arr[],int n)
{
int i=0;
for(;i<=n;i++)
{
if(arr[i]==0)
cout<<" ";
else if(arr[i]==1)
cout<<"#";
}
cout<<endl;
}
int main()
{
int n;
int store;
int tri;
int j;
int i;
cout<>n;
n=n*2-1;
int hash[n];
for(j=0;j<n;j++)
hash[j]=0;
hash[n/2]=1;
int bin;
for(j=0;j<8;j++)
bin[j]=0;
cout<>store;
binRev(store,bin);
print(hash,n);
for(j=0;j<n/2-1;j++)
{
store=hash;
for(i=1;i>n;
}

8. JP said

A bit late, by I coded up a Javascript version here that uses an HTML5 canvas to draw the automata. Then there’s a bigger, re-sizable version here.

9. V said

In Ruby. Could be improved…

```
def nextState(rule, state)
rule_in_binary = ("%08b" % rule).chars.reverse
rule_in_binary[state.join.to_i(2)]
end

def cellState(xs, i)
[
(i - 1 < 0)             ? "0" : xs[i - 1],
xs[i],
(i + 1 > (xs.size - 1)) ? "0" : xs[i + 1]
]
end

def nextGeneration(rule, row)
row.size.times.map do |i|
nextState(rule, cellState(row, i))
end
end

def formatState(state)
state.map { |x| x == "0" ? " " : "#" }.join
end

def show(rule:, cols:, rows:)
state = cols.times.map { "0" }
state[(cols/2).floor] = "1"

puts formatState(state)

rows.times.map do |memo, x|
state = nextGeneration(rule, state)
puts formatState(state)
state
end
end

show(rule: 30, cols: 31, rows:15)

```

outputs:

```
#
###
##  #
## ####
##  #   #
## #### ###
##  #    #  #
## ####  ######
##  #   ###     #
## #### ##  #   ###
##  #    # #### ##  #
## ####  ## #    # ####
##  #   ###  ##  ## #   #
## #### ##  ### ###  ## ###
##  #    # ###   #  ###  #  #
## ####  ## #  # #####  #######

```