## Cellular Automata

### May 15, 2009

A rule is stored as an eight-element vector of 1’s and 0’s with the least-significant element in slot 0. The code to translate a rule to its bit representation is similar to the digits function of the Standard Prelude, extended to include all the leading zeroes:

```(define (rule->bits rule)   (let loop ((rule rule) (k 8) (bits '()))     (cond ((zero? k) (list->vector (reverse bits)))           ((odd? rule) (loop (quotient rule 2) (- k 1) (cons 1 bits)))           (else (loop (quotient rule 2) (- k 1) (cons 0 bits))))))```

The primary difficulty of this exercise is representing the left and right edges of the automaton, which are infinite. To represent a cellular automaton for k ticks, we use a vector of 2k+3 elements: 1 for the center element, k for each of the left and right body elements, and 1 for each of the left and right edges. The `display-row` function takes a single row as its argument and displays the central k+1 elements, omitting the two edge elements; it adds an extra space between each cell to make the output look right given the size of the character cells and the aspect ratio of the screen:

```(define (display-row row)   (let ((len (- (vector-length row) 2)))     (do ((i 1 (+ i 1))) ((> i len) (newline))       (if (zero? (vector-ref row i))           (display #\space)           (display #\X))       (if (< i len) (display #\space)))))```

The `next-row` function takes a row and the bits representation of a rule and calculates the next row. The infinitude of the edges is preserved by copying the new end-of-row cells to the corresponding edge cells:

```(define (next-row row bits)   (let* ((len (- (vector-length row) 2))          (next (make-vector (+ len 2) 0)))     (do ((i 1 (+ i 1)))         ((> i len)           (vector-set! next 0 (vector-ref next 1))           (vector-set! next (+ len 1) (vector-ref next len))           next)       (let ((neighbors (+ (* (vector-ref row (- i 1)) 4)                           (* (vector-ref row i) 2)                           (vector-ref row (+ i 1)))))         (vector-set! next i (vector-ref bits neighbors))))))```

The main function builds an initial row consisting of a single black cell, then executes `next-row` for each tick, displaying each result:

```(define (cells rule ticks)   (let* ((row (make-vector (+ ticks ticks 3) 0))          (bits (rule->bits rule)))     (vector-set! row (+ ticks 1) 1)     (do ((tick 0 (+ tick 1))          (row row (next-row row bits)))         ((> tick ticks))       (display-row row))))```

Here’s an example:

```> (cells 79 12)                         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   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 run this code at http://codepad.org/H7akaoDD.

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:

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

```