# 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 Pixel color off on white black 0 1 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.

## 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
```

Macs running OS X come with a built-in viewer that can display these PBM images (just double-click on the file and the `GraphicConverter` application will open -- if your Mac doesn't have it, you can download it). For Windows, you can download a free viewer (try Googling for windows pbm viewer freeware). On the Unix machines in the lab, you can use `xv` like this:

```xv rule30.pbm
```

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
>>> 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.

• Use of functions — your program must be broken down into one or more functions — it cannot be one big long script.
• Each function has a docstring that summarizes its purpose and provides a description of its inputs and outputs.
• Tests and test output provided in printed form for each function in the program.
• All functions and variables have meaningful names.
• The program produces a correctly formatted PBM file.
• The program produces an image of the correct size.
• The program produces the correct pattern (demonstrate with at least 5 different patterns, some of which are the same as the Wolfram Atlas, some of which are different (like rule 139)