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 2k+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))
      (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

You can run this code at http://codepad.org/H7akaoDD.

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: