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
|
input=6
|
input=5
|
input=4
|
input=3
|
input=2
|
input=1
|
input=0
|
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 |
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 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%
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)