I've attempted a functional solution to Conway's Game of Life in Python.
The example code allows you to see the next generation of the universe by calling the step()
function, passing the current generation of the universe. The universe is represented as a set of live cells. Live cells are represented as a tuple of x, y coordinates.
All suggestions for improvement are welcome. I'd especially like feedback on the following:
- Approach - is it functional? If not, why not?
- Test cases - are there any test case I've missed that highlight a bug? Can it be done with less test cases while maintaining the same code coverage?
- Python idioms and conventions
- Making use of built-in functions and datatypes
import unittest
def get_neighbours(x, y):
'''
Returns the set of the given cell's (x,y) 8 eight neighbours.
:param x: x coordinate of cell
:param y: y coordinate of cell
'''
return {(x + dx, y + dy) for dx, dy in [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]}
def is_survivor(universe, x, y):
'''
Returns True if given cell will survive to the next generation, False otherwise.
:param universe: set of live cells in the universe. A live cell is the tuple (x,y)
:param x: x coordinate of cell
:param y: y coordinate of cell
'''
num_live_neighbours = len(get_neighbours(x, y) & universe)
return num_live_neighbours == 2 or num_live_neighbours == 3
def is_born(universe, x, y):
'''
Returns True if given cell will be born in the next generation, False otherwise.
:param universe: set of live cells in the universe. A live cell is the tuple (x,y)
:param x: x coordinate of cell
:param y: y coordinate of cell
'''
return len(get_neighbours(x, y) & universe) == 3
def step(universe):
'''
Returns the new universe after a single step in the game of life.
:param universe: set of live cells in the universe. A live cell is the tuple (x,y)
'''
survivors = { (x, y) for x, y in universe if is_survivor(universe, x, y) }
list_of_neighbour_sets = [get_neighbours(x, y) for x, y in universe]
flattened_neighbour_set = {item for subset in list_of_neighbour_sets for item in subset}
dead_neighbours = flattened_neighbour_set - universe
births = { (x, y) for x, y in dead_neighbours if is_born(universe, x, y) }
return survivors | births
class Test(unittest.TestCase):
def test_get_neigbours(self):
self.assertEqual({(-1, -1), (0, -1), (1, -1), (-1, 0), (1, 0), (-1, 1), (0, 1), (1, 1)}, get_neighbours(0, 0))
self.assertEqual({(4, 5), (4, 6), (4, 7), (5, 5), (5, 7), (6, 5), (6, 6), (6, 7)}, get_neighbours(5, 6))
def test_is_survivour_should_return_true_if_cell_has_2_live_neighbours(self):
self.assertTrue(is_survivor({(0, 0), (1, 0), (2, 0)}, 1, 0))
def test_is_survivour_should_return_true_if_cell_has_3_live_neighbours(self):
self.assertTrue(is_survivor({(0, 0), (1, 0), (0, 1), (1, 1)}, 0, 0))
self.assertTrue(is_survivor({(0, 0), (1, 0), (0, 1), (1, 1)}, 1, 0))
self.assertTrue(is_survivor({(0, 0), (1, 0), (0, 1), (1, 1)}, 0, 1))
self.assertTrue(is_survivor({(0, 0), (1, 0), (0, 1), (1, 1)}, 1, 1))
def test_is_survivour_should_return_false_if_cell_is_underpopulated(self):
self.assertFalse(is_survivor({(0, 0)}, 0, 0))
def test_is_survivour_should_return_false_if_cell_is_overpopulated(self):
self.assertFalse(is_survivor({(-1, -1), (0, -1), (1, -1), (-1, 0), (1, 0), (-1, 1), (0, 1), (1, 1)}, 0, 0))
def test_is_born_should_return_false_if_dead_cell_doesnt_have_exactly_3_live_neighbours(self):
self.assertFalse(is_born({(0, 0)}, 0, 0))
def test_is_born_should_return_true_if_dead_cell_has_exactly_3_live_neighbours(self):
self.assertTrue(is_born({(0, 0), (1, 0), (0, 1)}, 1, 1))
def test_L_becomes_block_after_step(self):
self.assertEqual({(0, 0), (1, 0), (0, 1), (1, 1)}, step({(0, 0), (0, 1), (1, 1)}))
if __name__ == "__main__":
unittest.main()