Conway's Game of Life is a cellular automaton operating on a grid of rectangles, infinite in both directions.

*Gosper Glider Gun Game of Life Excerpt*

* courtesy of Wikipedia -- hope they don't mind*

This project involves designing and implementing a collection of cellular automatons with birth-and-death rules identical to those of Conway's game, but on finite grids with various topologies.

** Cylinder**: Like a finite rectangle, but with the left and right
borders identified so that the column of cells on the left side of the rectangle
act as if they were bordered on the left by the column of cells on the right
side of the rectangle. And, vice versa, the column of cells on the right side of
the rectangle act as if they were bordered on the right by the column of cells
on the left side of the rectangle. Furthermore, the row of cells on the top of
the rectangle act as if they were bordered above by a row of cells whose states
are unaffected by the states of neighboring cells: they are always dead. In like
fashion, the row of cells on the bottom act as if they were bordered below by a
row of always-dead cells. The number of rows and columns stays fixed throughout
the game and is determined by the initial state of the game

** Moebius strip**. Like a cylinder, but with the left column
identified with the reverse of the right column. That is, the top left square is
the neighbor to the "right" of the bottom right square. The square
below the top left square is neighbor to the right of the square above the
bottom right square. And so on to bottom left square, which is the neighbor to
the right of the top right square. Note that these conventions also determine
diagonal neighbors of border squares.

** Torus**. Like a cylinder, but instead of having the top and
bottom rows bordered by always-dead cells, the top and bottom rows are identified in the same
fashion as the left and right columns in the cylinder. The left and right
columns in the torus are also identified, as in the cylinder

** Klein bottle**. Like a torus, but with the left column identified
with the reverse of the right column (as in a moebius strip) and with the top
row identified with the reverse of the bottom row.

** Infinite hex grid**. A honeycomb-like, two-dimensional grid of infinite extent in which
each cell is a regular hexagon with six neighboring hexagons of the same size
and shape. Birth, death, and survival rules follow a 34/2 pattern: In each
generation, a living cell survives if and only if it has 3 or 4 living
neighbors, and a dead cell comes to life if and only if it has exactly two
living neighbors.

Design and implement an interface to your software that facilitates setting up the initial state of the game-of-life automaton and helps visualize what is going on as the game progresses through the generations. You will probably want to use the graphics and reactive software facilities of DrACuLa, as described in the competitive pachinko project.

You will probably need to use some cleverness to avoid performance problems. One problem is quick access to the state of a cell. It may help to store cell states in an AVL tree (or red-black tree, or some other data structure with similar insertion, deletion, and look up properties) with nodes named by coordinate pairs. It may also help to store the names of a neighboring cells along with the state of a given cell, so you can quickly look at the states of its neighbors. To keep memory from getting out of hand, you will probably want store only live cells in the structure.

You will need to design a data structure to represent the state of the game, and numerous other data structures for other aspects of your software. Your functions will accept and/or generate these structures. As a minimum, every function must be accompanied by a theorem that states that if the function is supplied with arguments with the expected kind, it will deliver values of the expected kind.

In other words, as a minimum, you must prove that your code meets the type constraints that your design expects. Additional theorems bearing on aspects of correctness in the implementation are welcome and will improve its quality.