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.

`....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 = row;    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();}  }}`