## 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 2^{3}=8 states and 2^{8}=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 = 00011110_{2} 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

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

In Ruby. Could be improved…

outputs: