This is an archived copy of a previous semester's site.
Please see the current semester's site.
Many descriptions of Conway’s Game of Life (hereinafter called simply GoL
) are presented in a way that does not mesh well with practical implementation. This page attempts to describe the simplest Python implementation of which I am aware. It may not be the most efficient or most extensible, but it is short and functional.
GoL imagines a grid where each cell is either live
or dead
.
It hinges around an update
step which generates a new next
grid from a provided current
grid. This update can be done in several ways, but the simplest (and in many cases the most efficient too) is a two-step process.
Make a counts
grid containing integers between 0 and 8. The integer in a given cell of the counts grid is the number of live cells adjacent to the corresponding cell in the current grid. Here adjacent
means one of the cell’s 8 neighbors: one cell away above or below, and/or one cell away to the left or right.
A cell in the next grid depends only on the corresponding cell in the current and counts grids.
If the cell was live in the current grid and either 2 or 3 in the counts grid, it is live in the new grid.
If the cell was dead in the current grid and 3 in the counts grid, it is live in the new grid.
Otherwise, it is dead in the new grid.
There are many choices for how the grid is represented. It could be a list of lists, a single list with computation in indices, or even a big integer with each bit corresponding to one cell of the grid.
In Python, the shortest1 Not necessarily the most efficient or most extensible. code comes from a set of coordinates of live cells.
set of live cells is {(1,1), (2,2), (2,3), (3,1), (3,2)}
The corresponding counts grid is a dict with coordinates as keys and counts as values.
dict of counts is {(0,0):1, (0,1):1, (0,2):1, (1,0):1, (1,1):1, (1,2):3, (1,4):2, (1,5):1, (2,0):2, (2,1):4, (2,2):4, (2,3):2, (2,4):1, (3,0):1, (3,1):2, (3,2):3, (3,3):3, (3,4):1, (4,0):1, (4,1):2, (4,2):2, (4,3):1}
The standard library type collections.Counter is optimized for this particular kind of dict, and in particular will create such a dict from a sequence with repeated values. Assuming we have a collection defining what the neighborhood is, such as
deltas = ((-1,-1), (0,-1), (1,-1),
(-1, 0), (1, 0),
(-1, 1), (0, 1), (1, 1))we can make the counts from the current grid with a 1-liner:
counts = Counter((x+i,y+j) for (x,y) in current
for (i,j) in deltas)and make the next grid from the counts and current grid with another 1-liner:
next = {c for c,n in counts.items()
if n==3 or (n==2 and c in current)}That’s it. Two expressions (counts = ... and next = ... above) are the entirety of the update routine for the set-of-cells representation of GoL grids.
To create an animation, we