I recently took a couple of hours to work through the Game Of Life kata trying to do it strictly TDD. I've had a couple of short goes on the kata before during a code retreat but we were never able to finish it during the 45 minute sessions.
My first implementation is shown below together with the tests developed n parallell. This is a fixed board implementation that wraps in both north<->south and east<->west direction. Originally I did it as a non-wrapping implementation but changing it to a wrapping one was only a matter of writing a couple o extra tests and updating the cell_at() implementation.
This implementation also holds a representation for all cells, both dead and live ones. The upside is that this makes it very straight forward to calculate the new state of all cells. The two large drawbacks is that the space and number of calculations needed for is proportional to the board size rather than the number of live cells. This is no problem for a board of reasonable size but may be if the size is large.
# gameoflife.py
"""
Simple Game of Life implementation for a fixed size board that
wraps at the edges. All cells, both alive and dead are part of
the representation.
"""
ALIVE = 1
DEAD = 0
class GameAnalyzer(object):
directions = ((-1,-1), (0,-1), (1,-1),
(-1, 0), (1, 0),
(-1, 1), (0, 1), (1, 1))
def __init__(self, board):
self.board = board
def cell_at(self, x, y):
y_wrapped = y % len(self.board)
x_wrapped = x % len(self.board[y_wrapped])
return self.board[y_wrapped][x_wrapped]
def neighbour_count(self, x, y):
return sum([self.cell_at(x + dx, y + dy) for dx, dy in self.directions])
def judge_cell(self, x, y):
rules = (DEAD, DEAD, self.cell_at(x, y), ALIVE, DEAD, DEAD, DEAD, DEAD, DEAD)
neighbour_count = self.neighbour_count(x, y)
return rules[neighbour_count]
def evolve(board):
a = GameAnalyzer(board)
return [[a.judge_cell(x, y) for x, _ in enumerate(row)] for y, row in enumerate(board)]
# gameoflife_test.py
from gameoflife import evolve, GameAnalyzer, ALIVE as x, DEAD as o
from nose.tools import assert_equal
def test_empty_board_remains_empty():
assert_equal(evolve([[o, o, o],
[o, o, o],
[o, o, o]]), [[o, o, o],
[o, o, o],
[o, o, o]])
def test_single_cell_dies():
assert_equal(evolve([[o, o, o],
[o, x, o],
[o, o, o]]), [[o, o, o],
[o, o, o],
[o, o, o]])
def test_stable_formation_remains():
assert_equal(evolve([[o, o, o],
[o, x, x],
[o, x, x]]), [[o, o, o],
[o, x, x],
[o, x, x]])
def test_blinker_blinks():
assert_equal(evolve([[o, o, o, o, o],
[o, o, o, o, o],
[o, x, x, x, o],
[o, o, o, o, o],
[o, o, o, o, o]]), [[o, o, o, o, o],
[o, o, x, o, o],
[o, o, x, o, o],
[o, o, x, o, o],
[o, o, o, o, o]])
assert_equal(evolve([[o, o, o, o, o],
[o, o, x, o, o],
[o, o, x, o, o],
[o, o, x, o, o],
[o, o, o, o, o]]), [[o, o, o, o, o],
[o, o, o, o, o],
[o, x, x, x, o],
[o, o, o, o, o],
[o, o, o, o, o]])
def test_board_wraps_around():
# South -> North
assert_equal(evolve([[o, o, o, o, o],
[o, o, o, o, o],
[o, o, o, o, o],
[o, o, o, o, o],
[o, x, x, x, o]]), [[o, o, x, o, o],
[o, o, o, o, o],
[o, o, o, o, o],
[o, o, x, o, o],
[o, o, x, o, o]])
# North -> South
assert_equal(evolve([[o, x, x, x, o],
[o, o, o, o, o],
[o, o, o, o, o],
[o, o, o, o, o],
[o, o, o, o, o]]), [[o, o, x, o, o],
[o, o, x, o, o],
[o, o, o, o, o],
[o, o, o, o, o],
[o, o, x, o, o]])
# East -> West
assert_equal(evolve([[o, o, o, o, o],
[o, o, o, o, x],
[o, o, o, o, x],
[o, o, o, o, x],
[o, o, o, o, o]]), [[o, o, o, o, o],
[o, o, o, o, o],
[x, o, o, x, x],
[o, o, o, o, o],
[o, o, o, o, o]])
# East -> West
assert_equal(evolve([[o, o, o, o, o],
[x, o, o, o, o],
[x, o, o, o, o],
[x, o, o, o, o],
[o, o, o, o, o]]), [[o, o, o, o, o],
[o, o, o, o, o],
[x, x, o, o, x],
[o, o, o, o, o],
[o, o, o, o, o]])
def check_neighbour_count(board, at, expected):
(x, y) = at
a = GameAnalyzer(board)
assert_equal(a.neighbour_count(x, y), expected)
def test_correct_neighbour_count_to_the_right():
check_neighbour_count([[o, o, o],
[o, o, x],
[o, o, o]], (1, 1), expected=1)
def test_correct_neighbour_count_to_the_right_and_right_down():
check_neighbour_count([[o, o, o],
[o, o, x],
[o, o, x]], (1, 1), expected=2)
def test_zero_neighbour_count_with_no_cells():
check_neighbour_count([[o, o, o],
[o, o, o],
[o, o, o]], (1, 1), expected=0)
def test_correct_neighbour_count_with_alive_cell_on_the_board_but_no_neighbours():
check_neighbour_count([[o, o, o],
[o, x, o],
[o, o, o]], (1, 1), expected=0)
def test_correct_neighbour_count_with_alive_cells_in_all_neighbour_positions():
check_neighbour_count([[x, x, x],
[x, x, x],
[x, x, x]], (1, 1), expected=8)
def test_correct_neighbour_count_for_corner_cell():
check_neighbour_count([[o, o, o],
[o, x, x],
[o, x, o]], (2, 2), expected=3)
Representing the whole board makes the tests easy to read (no additional comments needed, both the existing and expected board are all fleshed out), but input data may be on the large size.Driving the design with tests I experience as hard sometimes. The biggest problem I usually have is that I reach points in the development process were I would like to write a test that would require too much of a development effort in one step to make it pass (staying at red for too long in the red-green-refactoring cycle).
The number of tests for this implementation probably indicate some test redundancy and could probably be reduced. I have not gone over them. These are all the tests I wrote during my "design driving".
One common strategy to deal with this is to start writing tests for lower level functions that you've identified that you need. This is indeed a good way of moving forward. In the code below I took the decision to do this with the GameAnalyzer.neighbour_count() method. What I don't like about this strategy is that it locks your implementation to using certain classes and functions that shouldn't even be exposed in the API. In this example the GameAnalyzer class should probably be considered private and part of the implementation details that the user of this code shouldn't ned to know about.
Writing tests against it partly wrecks this idea I belive since it forces some of the tests in the regression suite to work against code that should not be exposed. It will also force you to keep the GameAnalyser class and the neighbour_count() function unless you want to rewrite the tests.
One solution to this may be to write tests on a low level while driving the implementation and than replace those with tests on an API level once the implementation is ready.
The not so good things with this strategy is, as I see it:
- You have to write the same test twice, but on different levels.
- The second time you write the test you do not have the same confidence that it actually tests what you intended it to test (unless you start removing the parts implementing what you want to test to simulate "test first").
The answer to all these problems may (in part) be to write small and focused classes that corresponds well to the single responsibility principle and test those individually. Then complement those with a couple of high level integration tests that act as "guiding tests" to drive a top-down design.
For testing I used Nose with Rednose to colorize the output. I also used Nosier to have the tests run directly whenever I saved a file. This was a very nice setup: The command used (standing in the source folder) was:
nosier "nosetests --rednose" .
The second implementation was influenced by the implementation by Emily Bache in this video but I wanted to take the ideas of using sets a step or two further. This implementation uses an infinite board where only live cells are represented as (x, y) tuples. It's more efficient since both the number of calculations and space used is proportional only to the number of live cells.
# gameoflife2.py
"""
Game of Life implementation for an expanding game. Live cells are
represented as x and y tuples stored in a set.
"""
class Game(object):
directions = ((-1,-1), (0,-1), (1,-1),
(-1, 0), (1, 0),
(-1, 1), (0, 1), (1, 1))
def __init__(self, live_cells):
self.live_cells = live_cells
def next_generation(self):
return set.union(self.survivors(), self.births())
def births(self):
return set([(x, y) for x, y in self.birth_candidates()
if len(self.live_neighbours(x, y)) == 3])
def birth_candidates(self):
return set.difference(self.all_neighbours(), self.live_cells)
def all_neighbours(self):
neighbours = [self.neighbours(x, y) for x, y in self.live_cells] or [set()]
return set.union(*neighbours)
def survivors(self):
return set([(x, y) for x, y in self.live_cells
if len(self.live_neighbours(x, y)) in (2, 3)])
def live_neighbours(self, x, y):
return set.intersection(self.live_cells, self.neighbours(x, y))
def neighbours(self, x, y):
return set([(x + dx, y + dy) for dx, dy in self.directions])
def game_generator(initial_state):
state = initial_state
while True:
state = Game(state).next_generation()
yield state
# gameoflife2_test.py
from gameoflife2 import game_generator, Game
def test_game_with_no_live_cells_remains_dead():
assert game_generator(set()).next() == set()
def test_a_single_live_cell_dies():
game = game_generator(set([(1, 1)]))
assert game.next() == set()
def test_stable_formation_remains():
"""
xxo xxo
xxo -> xxo
ooo ooo
"""
stable = set([(0, 0), (0, 1), (1, 0), (1, 1)])
game = game_generator(stable)
assert game.next() == stable
def test_blinker_blinks():
"""
ooo oxo ooo
xxx -> oxo -> xxx
ooo oxo ooo
"""
game = game_generator(set([(0, 1), (1, 1), (2, 1)]))
assert game.next() == set([(1, 0), (1, 1), (1, 2)])
assert game.next() == set([(0, 1), (1, 1), (2, 1)])
def test_game_plan_expands():
"""
oxo
xxx oxo
ooo -> oxo
ooo ooo
"""
game = game_generator(set([(0, 0), (1, 0), (2, 0)]))
assert game.next() == set([(1,-1), (1, 0), (1, 1)])
def test_Game_survivors_live_cell_with_two_and_three_neighbours_survive():
"""
xxo xxo
xxo -survivors-> oox
oxo oxo
"""
state = set([(0, 0), (0, 1), (1, 0), (1, 1), (1, 2)])
assert Game(state).survivors() == set([(0, 0), (1, 0), (1, 2)])
def test_Game_births_dead_cell_with_three_neighbours_come_alive():
"""
oxo ooo
oxo -births-> xox
oxo ooo
"""
state = set([(1, 0), (1, 1), (1, 2)])
assert Game(state).births() == set([(0, 1), (2, 1)])
def test_Game_birth_candidates_all_dead_cells_with_with_live_neighbour():
"""
ooo ooo
ooo -birth_candidates-> xxx
oxo xox
"""
state = set([(1, 2)])
assert Game(state).birth_candidates() == set([(0, 1), (1, 1), (2, 1), (0, 2),
(2, 2), (0, 3), (1, 3), (2, 3)])
def test_Game_live_neighbours_counts_correctly():
state = set([(0, 0), (0, 1), (1, 0)])
game = Game(state)
assert game.live_neighbours(0, 0) == set([(0, 1), (1, 0)])
assert game.live_neighbours(1, 1) == set([(0, 0), (0, 1), (1, 0)])
The tests are a bit clumsier since the input and output is not so easy to read and may require additional comments.
I switched to pytest for this implementation. Still using Nosier to run the tests the command was as follows:
nosier py.test .
In this limited scenarion Nose and Py.Test are rather similar. Writing the tests in PyTest is a bit cleaner I think since you can use the standard assert and still get a nice printout of what caused the assertion to fail. In Nose you must use a special assert_equal() to get the same functionality. No big deal really. It fells like Nose is a tiny bit faster running the tests. I haven't done any measurements though.
Overall this was a nice and teaching session. I might return to the game of life in the future.
