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 23=8 states and 28=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 = 000111102 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

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

8 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

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

    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


    using namespace std;
    void binRev(int n,int arr[])
    int i=0;
    void print(int arr[],int n)
    int i=0;
    cout<<" ";
    else if(arr[i]==1)
    int main()
    int n;
    int store;
    int tri;
    int j;
    int i;
    int hash[n];
    int bin[8];

  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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: