conway's game of life
Conway's game of life is a simple simulation. The simulation universe is a grid of cells where each cell can either be dead or alive. As time moves on cells can flip from one state to the other with the following rules:
- A perviously alive cell will continue to be alive if it has 2 or 3 adjacent cells that are currently alive (ie neighbors).
- A dead cell can become alive if it has 3 alive neighbors
- Any other scenario leads to the cell dying
Here is a simple example of the first two steps of a 3x3 game of life:
0 | 0 | 0 |
1 | 1 | 1 |
0 | 0 | 0 |
\(\rightarrow\)
0 | 1 | 0 |
0 | 1 | 0 |
0 | 1 | 0 |
You can see the middle cell, which has two adjacent alive cells does not change. But, the cells on each side which only have one alive neighbor turns off. Then, on the top and bottom row each middle cell with three neighbors below/above it turn on.
We can start by defining the universe. In this case, we can define the universe as a mapping from coodinates that describe a cells location to binary values (1 for alive, 0 for dead):
Universe = dict Coord = tuple def alive(universe, coord): return universe[coord]
In order to test our code, we will create a test universe identical to the one in the example above and a couple of helper functions to make that easier:
def array_to_universe(arr): universe = Universe() for x, row in enumerate(arr): for y, cell in enumerate(row): universe[(x, y)] = cell return universe def universe_to_array(universe, width, height): arr = [] for x in range(width): arr += [], for y in range(height): arr[-1] += universe[(x, y)], return arr # The intial state of our universe arr = [ [0, 0, 0], [1, 1, 1], [0, 0, 0] ] universe = array_to_universe(arr)
assert arr == universe_to_array(array_to_universe(arr), 3, 3)
In each iteration of the game, the universe is updated to a new state using simple rules:
- A perviously alive cell will continue to be alive if it has 2 or 3 alive cells adjacent to it (ie neighbors).
- A dead cell can become alive if it has 3 alive neighbors
- Any other scenario leads to the cell dying
We can code up the rules as the simple expression:
def should_live(is_alive, alive_neighbors): return int(is_alive and alive_neighbors == 2 or alive_neighbors == 3)
assert should_live(0, 0) == 0, "Line 1" assert should_live(0, 3) == 1, "Line 2" assert should_live(1, 1) == 0, "Line 3" assert should_live(1, 2) == 1, "Line 4" assert should_live(1, 3) == 1, "Line 5" assert should_live(1, 4) == 0, "Line 6"
Next, we need an update function. This function will take our universe and a specific coordinat as an input. It will apply our rules and produce the value that the cell should take in the next step of the simulation:
def update(universe, coord): alive_neighbors = sum([ alive(universe, neighbor) for neighbor in neighbors(universe, coord) ]) return should_live(alive(universe, coord), alive_neighbors)
assert update(universe, (0, 0)) == 0 assert update(universe, (0, 1)) == 1 assert update(universe, (1, 0)) == 0 assert update(universe, (1, 1)) == 1
The implementation is a little more involved. In order to apply should_live
we need the state of the cell at that coordinate and the number of neighbors surrounding that cell that are alive. The first piece of information is easy to find. The second is a little trickier and requires us to write a function to find all the neighbor of a point:
from itertools import product increments = (-1, 0, 1) directions = product(increments, increments) def neighbors(universe, coord): # Create a set of potential neighbors x, y = coord potential_neighbors = { (x + dx, y + dy) for dx, dy in directions if not (dx == 0 and dy == 0) } # Return all potential neighbors in the universe return potential_neighbors & universe.keys()
assert neighbors(universe, (0, 0)) == {(0, 1), (1, 0), (1, 1)} assert neighbors(universe, (-2, -2)) == set()
Finding our neighbors isn't too challenging but there is a neat trick to it. Notice that if we want the coordinate to the left of a point we subtract 1 from the x value and do nothing with the y value. If we want the point diagionally top-left, we subtract one from the x value and add one to the y. The pattern here is that a neighbors coordinate of a point is any combination of -1, 0, or 1 more/less from the x or y value of that point. In python, we use itertools.product
to create all of these combinations. (Notice: there is one combination that isn't a neighbor, (0, 0) because adding 0 to the x and y values of a point is that same point).
Finally, we need a driver to step through the simulation. It will be fairly simple: for every coordinate in the cell, run the update function:
def cgl(universe): return { coord: update(universe, coord) for coord in universe }
Now, let's see if it works:
result = cgl(universe) universe_to_array(result, 3, 3)
0 | 1 | 0 |
0 | 1 | 0 |
0 | 1 | 0 |