## 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 2*k*+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

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

My Haskell solution (see http://bonsaicode.wordpress.com/2009/05/15/programming-praxis-cellular-automata/ for a version with comments):

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

Nevermind, I was misreading the text :)

Anyway, here’s my crappy solution: link

[…] 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 […]

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[8];

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[0];

for(i=1;i>n;

}

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.