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.
Programming Praxis 
[…] Praxis – Cellular Automata By Remco Niemeijer Today’s Programming Praxis problem is about cellular automata. Let’s dive […]
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 15There may be a little bit of confusion with the example rule 158 generations you provide. There are 13 lines listed there, not 12.
Nevermind, I was misreading the text :)
Anyway, here’s my crappy solution: link
[…] 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 […]
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;
}
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.
In Ruby. Could be improved…
def nextState(rule, state) rule_in_binary = ("%08b" % rule).chars.reverse rule_in_binary[state.join.to_i(2)] end def cellState(xs, i) [ (i - 1 < 0) ? "0" : xs[i - 1], xs[i], (i + 1 > (xs.size - 1)) ? "0" : xs[i + 1] ] end def nextGeneration(rule, row) row.size.times.map do |i| nextState(rule, cellState(row, i)) end end def formatState(state) state.map { |x| x == "0" ? " " : "#" }.join end def show(rule:, cols:, rows:) state = cols.times.map { "0" } state[(cols/2).floor] = "1" puts formatState(state) rows.times.map do |memo, x| state = nextGeneration(rule, state) puts formatState(state) state end end show(rule: 30, cols: 31, rows:15)outputs:
# ### ## # ## #### ## # # ## #### ### ## # # # ## #### ###### ## # ### # ## #### ## # ### ## # # #### ## # ## #### ## # # #### ## # ### ## ## # # ## #### ## ### ### ## ### ## # # ### # ### # # ## #### ## # # ##### #######