Project 1: Cellular Automaton

Ka-Ping Yee & Dan Garcia, 2005-11-30 (updated 2006-01-29)
A cellular automaton is an array of cells that switch on or off depending on whether other cells are on or off. Even simple rules for deciding when cells turn on or off can lead to complex and beautiful patterns.

Let's consider a particular kind of automaton in which the array contains a single row of cells. At each timestep, all of the cells update their state depending on the states of their neighbours. The state of a particular cell at time T = 1 is determined by the states of the cell itself at T = 0, its left neighbour at T = 0, and its right neighbour at T = 0. Then the state of the cell at T = 2 is determined by the states of the cell and its two neighbours at T = 1, and so on.

The decision whether to turn on or off is governed by a rule. For example, a rule might say, "if the left neighbour is on, then turn on". You can think of a rule as a function with three binary inputs (the state of the left neighbour, the cell itself, and the right neighbour in the previous timestep) and one binary output (the new state of the cell in the next timestep).

A rule can be described by a single number from 0 to 255 in the following manner: convert the rule number into a binary number with 8 bits, which we'll call bit 7, bit 6, and so on down to bit 0, where bit 7 is the most significant bit and bit 0 is the least significant bit. If you take the three inputs as three bits of a binary number, you get a number k from 0 to 7, and bit k of the rule number gives you the output.

In the following examples, we will use multiple equivalent representations for off and on states:

State off on
Pixel color white black
Value 0 1
Graphic empty filled

Boundary Conditions : off-the board should be considered off!

Cellular automaton specifications always need to be clear what to do about the edges of the simulation. Here, when you place your rule mask on the rightmost or leftmost cells, it will hang off the edge, and have undefined values for the cells off the board.

For this assignment, we want you to consider the cells that are off the board to be permanently off.

An Example: Rule 30

For example, the number 30 is 00011110 in binary.

27=128 26=64 25=32 24=16 23=8 22=4 21=2 20=1
16 + 8 + 4 + 2 = 30
0 0 0 1 1 1 1 0

So, this is how you would interpret rule 30:

input=7
1 1 1
0
input=6
1 1 0
0
input=5
1 0 1
0
input=4
1 0 0
1
input=3
0 1 1
1
input=2
0 1 0
1
input=1
0 0 1
1
input=0
0 0 0
0
Figure 1. To translate the number 30 into a rule, convert it to the 8-bit binary number 00011110. These 8 bits give the output for each of the 8 possible input conditions. These diagrams show 1 as a filled cell and 0 as an empty cell.

Suppose we start out with a row with a single filled cell and all the rest empty. Here's what happens in the first two timesteps of rule 30. You can work it out on paper yourself by referring to Figure 1.

1
1 1 1
1 1 1
Figure 2. The first two steps of rule 30.

If we run rule 30 for a couple hundred timesteps, an irregular pattern emerges. This can be verified with an archival site of rule 30 at the Wolfram Atlas.

Figure 3. The first 200 steps of rule 30.

The Challenge

For this project, you'll write a Python program to generate these patterns. Your program should accept two arguments on the command line: the rule number and the number of steps. For help with handling command line arguments: read up on argv (part of the sys module). The program should print out an image in Portable Bitmap Format (described below). The first row of the image should be all white (all zeroes) except for a single black pixel in the center, and this should be followed by a row for each timestep. If there are n timesteps, there should be n columns in the image on both sides of the center column. So, for example, the command:

python project1.py 30 200

should produce the image in Figure 3, which has 401 columns and 201 rows.

Assignment Correctness

The assumption that all cells off-the-grid are always considered off causes will cause discrepancies in your results for certain rules when comparing your results to what you see at the Wolfram Atlas. For example, your solution may generate this for rule 139:
  P1 35 18
  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0
  1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1
  1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0
  1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0
  1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1
  1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 0
  1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 0 0
  1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 0 0 1
  1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 0 0 1 0
  1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 0 0 1 0 0
  1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 0 0 1 0 0 1
  1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 0 0 1 0 0 1 0
  1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0
  1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1
  1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0

However, the image of Rule 139 in the Wolfram Atlas suggests that it should be like this:

  P1 35 18 
  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Can you spot the difference? Our solution has several diagonals of zeros creeping in from the right-hand side of the image while the Wolfram solution does not. This is due to their assumption that the grid is an infinite grid (versus a finite grid in this assignment). Therefore, for the sake of simplicity, the CS9H solution at in the upper region is considered the correct solution for this assignment. This means, you do not need to write additional code to produce their solution. For those of you who want to have a more "correct" solution, see the Extra for Experts Section.

Portable Bitmap Format

An image in Portable Bitmap Format is a text file where each line (after the first line) is a row of the image as a string of "0"s and "1"s. The first line indicates the format and size of the image in the form "P1 width height". So, for example, the 7-pixel-by-3-pixel image in Figure 2 would be represented by a text file like this:

P1 7 3
0001000
0011100
0110010

Your program should print the PBM image on its standard output (that is, using print statements). The output can be saved to a file by putting a ">" after the command, like this:

python project1.py 30 200 > rule30.pbm

To verify that your file has been written correctly, you should open the .pbm file in your favorite graphic / image file editor (e.g., Photoshop, Graphic Converter, etc.). If you don't have one, you can use something free like GIMP: "GNU Image Manipulation Program."

Some other interesting rules you can try are rule 18, rule 45, rule 73, rule 105, rule 150, and rule 225. The Wolfram Atlas has pictures of all 256 rules, so you can use it to check your results.

Hints

Python has a few handy operators to help you manipulate binary numbers. The << and >> operators shift a number to the left or right respectively. Shifting left has the same effect as multiplying by 2; shifting right has the same effect as dividing by 2 and ignoring the remainder.

The & operator performs a binary AND, which you can use to test bits in a number. For example, x & 8 tests bit 3 in the binary value of x, yielding 8 if bit 3 is on, or yielding 0 if bit 3 is off. (8 is 23, the value of bit 3.)

Your program can store the current row as a string, and construct the next row from that. You don't need to store all the rows of the image. After printing out a row, use it to figure out the next row.

Docstrings

Python documentation strings (docstrings) are a specific way to comment your code. Each module, class, function, and method should have an associated docstring. In these, you should explain how you use them, the format of inputs and outputs, and maybe an example. A Python docstring is indicated by 3 double quotation marks at the begining and end.

Testing

Test each function in your program with enough different inputs to show that it works. When testing a function, print out the input, the expected result, and the actual result. A really great way to automate this process is to use Python's built-in doctest module.

Test your program using rule 30 and at least three other rules. For testing the whole program, use only a small number of rows (say, 5 or 6) so that the test output is reasonably short.

On a Mac or Unix computer, you can use the script command to record a log of your tests. For example (you type the text shown in bold):

computer% script project1.log
Script started, output file is project1.log
computer% python
Python 2.4.1 (#2, Mar 31 2005, 00:05:10) 
[GCC 3.3 20030304 (Apple Computer, Inc. build 1666)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> 2 + 3
5
>>>
computer% python project1.py 30 5
P1 11 6
00000100000
00001110000
00011001000
00110111100
01100100010
11011110111
computer% exit
Script done, output file is project1.log
computer% lpr project1.log
computer%
Figure 4. Use the script command to log your testing session so you can print it out on paper.

Type script followed by a filename to start a log of your shell session. Then you can start the Python interpreter to execute tests or you can run your program from the Unix prompt, and everything in the terminal will be recorded to the file. Type exit when you are finished testing.

Extra for Experts

If you want a "Wolfram Atlas correct" solution, add a new optional parameter named Wolfram to generate the correct result. For example:

  computer% python project1.py 139 17
  ;; would produce the CS9H solution above

  computer% python project1.py 139 17 Wolfram
  ;; would produce the image that matches the Wolfram Atlas website

If you really enjoy this project, you might want to consider implementing a Totalistic Cellular Automaton. Enjoy!

Checklist

These are the requirements to meet for project completion.