Conway's Game of Life + Topology

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. 

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

User interface

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.

Speed

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.

Tests and Theorems

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.