In this example, we will bring together everything we learned about debugging to fix a script that runs Conway's game of life. Before we do that, however, let's answer the most obvious question here...
Basically, it's a discrete two-dimensional grid where every cell can be "alive" or "dead". Starting with a set of cells marked "alive", we can "evolve" the cells to the next generation by following these simple rules:
There are a lot of cool things you can do with this, and, for that, I defer to the wiki. Let's get on with debugging.
The code below is intended to be an implementation of Conway's game of life, but it's pretty terrible.
In [1]:
from math import sqrt
def conway(population,
generations = 100):
for i in range(genrations): population = evolve(population)
return popluation
def evolve(population):
activeCells = population[:]
for cell in population:
for neighbor in neighbors(cell):
if neighbor not in activeCells: activeCells.append(neighbor)
newPopulation = []
for cell in activeCells:
count = sum(neighbor in population for neighbor in neighbors(cell))
if count == 3 or (count == 2 and cell in population):
if cell not in newPopulation: newPopluation.add(cell)
return newPopulation
def neighbors(cell):
x, y = cell
return [(x, y), (x+1, y), (x-1, y), (x, y+1), (x, y-1), (x+1, y+1), (x+1, y-1), (x-1, y+1), (x-1, y-1)]
glider = [(0, 0), (1, 0), (2, 0), (0, 1), (1, 2)]
print conway(glider)
It caught an unused import and some typos. In this little example, pyflakes saved us from having to run the script multiple times to find each error; imagine how useful that is in larger code! If we fix the code, it should now run.
In [4]:
def conway(population,
generations = 100):
for i in range(generations): population = evolve(population)
return population
def evolve(population):
activeCells = population[:]
for cell in population:
for neighbor in neighbors(cell):
if neighbor not in activeCells: activeCells.append(neighbor)
newPopulation = []
for cell in activeCells:
count = sum(neighbor in population for neighbor in neighbors(cell))
if count == 3 or (count == 2 and cell in population):
if cell not in newPopulation: newPopulation.append(cell)
return newPopulation
def neighbors(cell):
x, y = cell
return [(x, y), (x+1, y), (x-1, y), (x, y+1), (x, y-1), (x+1, y+1), (x+1, y-1), (x-1, y+1), (x-1, y-1)]
glider = [(0, 0), (1, 0), (2, 0), (0, 1), (1, 2)]
print conway(glider)
Wow, that's a lot of issues! I recommend going through each one and figuring out why it deviates from the PEP8 standard. It's obnoxious, but it'll help you write better code the first time around.
Even with all of these issues, there are still some things that pep8 isn't telling us.
camelCase. That's bad. Rewrite as snake_case.if statements to one line. Don't be afraid of whitespace.Fixing all of these issues results in much more readable code.
In [ ]:
def conway(population, generations=100):
"""Runs Conway's game of life on an initial population."""
for i in range(generations):
population = evolve(population)
return population
def evolve(population):
"""Evolves the population by one generation."""
# Get a unique set of discrete cells that need to be checked
active_cells = population[:]
for cell in population:
for neighbor in neighbors(cell):
if neighbor not in active_cells:
active_cells.append(neighbor)
# For each cell in the set, test if it lives or dies
new_population = []
for cell in active_cells:
count = sum(neighbor in population for neighbor in neighbors(cell))
if count == 3 or (count == 2 and cell in population):
if cell not in new_population:
new_population.append(cell)
# Return the new surviving population
return new_population
def neighbors(cell):
x, y = cell
return [(x, y), (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1),
(x + 1, y + 1), (x + 1, y - 1), (x - 1, y + 1), (x - 1, y - 1)]
glider = [(0, 0), (1, 0), (2, 0), (0, 1), (1, 2)]
print conway(glider)
According to successful implementations of Conway's game of life, our given initial population should cause the living cells to "glide" across the grid over many generations. However, it's not doing that. What's going on?
Using pdb, we can follow the state of every variable as the code runs. This is difficult to show through IPython, so I'll leave it up to you. Set some traces in "3_conway_pre_debugged.py" and see if you can find the bug. Once you find it (or give up), keep reading.
(x, y) as a neighbor. Removing that fixes the code, and the glider glides.This code is now functional and follows PEP8 standards, but maybe it could be faster. For a baseline, let's time the current script over 1,000,000 generations. Running "time python 4_conway_pre_profiled.py" results in
To break down the locations of the speed constraints, we can run "python -m cProfile -s time 4_conway_pre_profiled.py"
Going through everything here is waay beyond the scope of the tutorial. However, I want to introduce one speed boost that will not only improve performance, but will also simplify our code and improve its readability. This involves the use of sets, which are collections that only store unique elements. They are much better than lists when you need to check for the existence of an element, which we do a lot in this script. Refactoring to use sets results in:
In [ ]:
def conway(population, generations=100):
"""Runs Conway's game of life on an initial population."""
population = set(population)
for i in range(generations):
population = evolve(population)
return list(population)
def evolve(population):
"""Evolves the population by one generation."""
# Get a unique set of discrete cells that need to be checked
active_cells = population | set(neighbor for p in population
for neighbor in neighbors(p))
# For each cell in the set, test if it lives or dies
new_population = set()
for cell in active_cells:
count = sum(neighbor in population for neighbor in neighbors(cell))
if count == 3 or (count == 2 and cell in population):
new_population.add(cell)
# Return the new surviving population
return new_population
def neighbors(cell):
"""Returns the neighbors of a given cell."""
x, y = cell
return [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1), (x + 1, y + 1),
(x + 1, y - 1), (x - 1, y + 1), (x - 1, y - 1)]
glider = [(0, 0), (1, 0), (2, 0), (0, 1), (1, 2)]
print conway(glider)
The code now clocks in at 50.3 seconds, which is 38% increase in speed. That's nice.
This notebook just showcased linting, coding styles, finding bugs, and improving code speed. I know this all seems like a lot of work, but it will make you produce much better code (and, as you get better, your debugging time will decrease rapidly). Stick with it!