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))
          next)
      (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   X

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

About these ads

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

    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;
    }

  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

Follow

Get every new post delivered to your Inbox.

Join 576 other followers

%d bloggers like this: