Python track: lab 4: fun with cellular automata

This lab, you're going to be implementing a general-purpose program for computing one-dimensional cellular automata in python. We will use this program next week to generate interesting graphical patterns.

One-dimensional cellular automata

Most programmers have either written or at least played with programs that simulate the game of "Life". Life is a particular kind of two-dimensional cellular automaton. In this assignment we'll be looking at one-dimensional cellular automata (1dCA). (Note that "automata" is the plural of the word "automaton".) You'll see that 1dCAs can also generate lots of interesting patterns, including both periodic and "chaotic" patterns. In fact, some 1dCAs are actually universal models of computation all by themselves, but we won't go into that here.

A 1dCA is composed of the following elements:

1. An array of cells, each of which has a state (represented by a number between 0 and the maximum number of states minus 1).
2. A neighborhood radius, which states how many cells in either direction affect the next state of any given cell. The cell's next state depends only on the states of these cells as well as its own current state.
3. A state transition table that determines which state to set a given cell to, given the previous state of the cell and the states of the cells in its neighborhood.

Some implications of this are:

1. The 1dCA is entirely deterministic.
2. The next state of the cells in the 1dCA depends only on the current states of the cells.

We will add one extra rule to simplify our program: the next state of a given cell depends only on the sum of the states of the cells in its neighborhood and its own state.

There is always the question of what to do for the edges of the automaton, where not all the cells in the neighborhood may be available. Two obvious choices are:

1. assume that the unavailable (missing) cells have states = 0, or
2. apply a "wraparound" rule whereby   cell[-1] = cell[nstates-1] and cell[nstates] = cell[0]. Make sure you wrap around on both sides if you do this.

You are free to use either rule in your program, or to implement both (user-selectable, of course ;-)).

Description of the program

You are to write a python module called automaton.py which implements a 1dCA with the following characteristics:

1. The above updating rules are implemented.
2. An arbitrary sized cell array can be specified.
3. An arbitrary number of states can be specified.
4. An arbitrary number of nearest neighbors can be specified.
5. An arbitrary update rule (state transition table) can be specified.

Note that the size of the state transition table is a function of the number of states and the number of neighbors.

Your module should include a class called cellular_automaton_1d. You should implement (at least!) these methods for your class (you may choose different names if you like):

1. __init__, of course.

   Use this to specify values (including default values) for the number of states, number of nearest neighbors, and the state transition table (which should default to None, meaning it will be generated randomly). You should also specify the size of the cell array, though you don't need to specify a default size.

   The format of the state transition table is an array of integers where:

   • the index (position) in the array represents the sum of the state of a cell and the states of its nearest neighbors
   • the contents of the array at that index represent the next state of the cell

   Note that the states are represented as positive integers starting from 0.

   NOTE: Check for errors! You should raise an exception if any of the arguments to the constructor are invalid (e.g. some arguments that should be integers aren't integers, some arguments are out of range (e.g. a negative number of nearest neighbors) the state transition table is too small for the number of states and the number of neighbors, the contents of the table are invalid, etc.). Check for every possible error, not just for the ones that come to you off the top of your head.

2. generate_random_table, which will generate a valid random state transition table for the given number of neighbors and states.

3. random_initialize, which will randomly initialize each cell in the cell array to a valid state.

4. update, which will use the current values of the cell array in order to generate the next set of values. You will need a temporary array for this. Make sure you don't change the original array until the new array is completely computed.

5. get_states, which will return the cell array (ideally, a copy of the cell array).

6. dump, which will print the cell array to stdout. If there are no more than 10 states, each cell should print as a single digit in the range [0-9] (with no spaces between the digits); otherwise, just print the array directly using python's "print" statement. To print a single digit without a newline or a space after it, you can use the sys.stdout.write() function.

Testing your class

At the end of your module (outside of the class) put this code:

    if __name__ == "__main__":
        try:
            # Arguments here to the constructor are:
            # size of cell array, number of states, number of neighbors (on each
            # side), the state transition table.
            a = cellular_automaton_1d(70, 2, 1, [0, 1, 1, 0])
            a.random_initialize()
            a.dump()
    
            for i in range(100):
                a.update()
                a.dump()
        except ...  # whatever can be thrown in the try block

Since your constructor can throw exceptions, you should put it in a try/except block as shown, catch all exceptions it raises, and print out a usage message where appropriate. Do not use a catch-all exception handler.

Test your class by typing

    % python automaton.py

(where % is the prompt). This should generate an interesting pattern of 1s and 0s. (If the pattern isn't interesting, you probably have a bug.) If you want to see the pattern more clearly, do this:

    % python automaton.py | tr "01" ".*"

This will show a nice fractal-like pattern. Try other arguments to the constructor and see what kinds of patterns you generate.

NOTE: If the pattern displayed by the program doesn't look cool, then you've absolutely certainly made a mistake. Fix it before submitting it! It's surprising how many students have trivial mistakes in their lab 4 code.

Next week, we'll use this class to generate graphical patterns in color.