Friday, April 11, 2008

Cellular Automata

A one-dimensional cellular automata is an array where each position is either off (.) or on (X). At each time step the contents of each cell are updated using a simple rule such as the following:

* If a cell is off then next time it will be in the same state that the cell to its right is currently at.
* If a cell is on then next time it will be off if both of its neighbors are currently on, otherwise it will stay on.

For example, if you start with

....X


then next time you will have

...XX


and the next two steps will be

..XXX
.XX.X


Write a problem that implements and displays this one dimensional cellular automata rule. You can assume that the first and last positions never change their state.


This problem might be a bit too long to solve on a whiteboard (at least in Java) but you should be able to write it down in one sheet of paper. All we do is create a new row from the old one.

public class OneDCell {
private char[] row;

public OneDCell(int length){
row = new char[length];
for (int i = 0; i < row.length; i++){
row[i] = '.';}
row[row.length-1] = 'X';
}

/** Implement Wolfram's rule 110.
* Did you know: Stephen Wolfram believes
* the universe is best
* understood using cellular automata */

public void step(){
char[] newRow = new char[row.length];

//To Do: Generalize this to encode anyone of the 2^8 rules.
for (int x=1; x < row.length -1; x++){
if (row[x] == '.'){
newRow[x] = row[x+1];
}
else {
if (row[x-1] == 'X' && row[x+1] == 'X'){
newRow[x] = '.';}
else {
newRow[x] = 'X';}
}
}
//Set the first and last
newRow[0] = row[0];
newRow[row.length-1] = row[row.length-1];
row = newRow;
}

/**The Obvious visualization */
public String toString(){
String result = "";
for (int i=0; i< row.length; i++){
result += row[i];}
return result;}

//Unit testing
public static void main(String[] argc){
OneDCell ca = new OneDCell(80);

//Behold! complexity arises out of simplicity!
while (true) {
System.out.println(ca);
ca.step();}
}
}



No comments:

ShareThis