Game of Life rules in 14 lines of Python

Question

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()

Answer 1

For docstrings, if you're following the Sphinx documentation format (which it looks like you are), you can specify an explicit :return: field to document what exactly it is your function is returning. PEP-0257 has various other conventions for docstrings like leaving a blank line between the summary line and the rest of the docstring, if you're really interested.

In terms of functional programming, you could use some of Python's functional programming functions, e.g the builtins filter and map and also any functions from the functools module. Also, since you are already not mutating any of the variables in your program (as you wouldn't do when programming in a functional manner), you can use frozenset()s in place of where you're currently using sets, as frozen sets are explicitly immutable.

Here is an attempt at "functionifying" the step function. Since Python 3, you can put type hints in the signature of functions, and since Python 3.5 you can also use the typing module to define types in a formal way, which can allow for better static type-checking if you're using a typing-aware IDE. Since you're wanting to program in a functional way, I'm guessing this would be of more interest than usual.

from functools import reduce
from typing import Tuple, Set

Cell = Tuple[int, int]
Universe = Set[Cell]  # or even FrozenSet[Cell]

...

def step(universe: Universe) -> Universe:
    """ Evaluate the next step in the Game of Life.

    :param universe: set of live cells in the universe. A live cell is the tuple (x,y)
    :return: the new universe after a single step in the game of life.
    """
    survivors = filter(lambda cell: is_survivor(universe, *cell), universe)
    neighbours = reduce(set.union, map(lambda cell: get_neighbours(*cell), universe))
    dead_neighbours = filter(lambda cell: cell not in universe, neighbours)
    births = filter(lambda cell: is_born(universe, *cell), dead_neighbours)
    return frozenset(survivors) | frozenset(births)

To be honest though, functional programming does not seem idiomatic in Python, even though it can be done; I would say your current code is pretty clear and idiomatic as is, using set comprehensions and such.