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 2³=8 states and 2⁸=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 = 00011110₂ 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 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.

Posted by programmingpraxis

Filed in Exercises

9 Comments »

9 Responses to “Cellular Automata”

Programming Praxis – Cellular Automata « Bonsai Code said
May 15, 2009 at 5:56 PM
[…] Praxis – Cellular Automata By Remco Niemeijer Today’s Programming Praxis problem is about cellular automata. Let’s dive […]

Remco Niemeijer said

May 15, 2009 at 5:56 PM

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

ardnew said
June 8, 2010 at 9:44 PM
There may be a little bit of confusion with the example rule 158 generations you provide. There are 13 lines listed there, not 12.
ardnew said
June 8, 2010 at 9:50 PM
Nevermind, I was misreading the text :)
ardnew said
June 8, 2010 at 10:53 PM
Anyway, here’s my crappy solution: link
Rule 30 RNG « Programming Praxis said
April 29, 2011 at 9:04 AM
[…] 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 […]
Devdhar said
April 29, 2012 at 10:07 PM
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;
}
JP said
October 4, 2012 at 3:52 AM
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.

V said

December 20, 2016 at 10:35 AM

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:


               #               
              ###              
             ##  #             
            ## ####            
           ##  #   #           
          ## #### ###          
         ##  #    #  #         
        ## ####  ######        
       ##  #   ###     #       
      ## #### ##  #   ###      
     ##  #    # #### ##  #     
    ## ####  ## #    # ####    
   ##  #   ###  ##  ## #   #   
  ## #### ##  ### ###  ## ###  
 ##  #    # ###   #  ###  #  # 
## ####  ## #  # #####  #######

Programming Praxis