Conway's Game of Life in Python

Question

Here's my Python implementation of Conway's Game of Life:

class Game(object):

    def __init__(self, state, infinite_board = True):

        self.state = state
        self.width = state.width
        self.height = state.height
        self.infinite_board = infinite_board

    def step(self, count = 1):

        for generation in range(count):

            new_board = [[False] * self.width for row in range(self.height)]

            for y, row in enumerate(self.state.board):
                for x, cell in enumerate(row):
                    neighbours = self.neighbours(x, y)
                    previous_state = self.state.board[y][x]
                    should_live = neighbours == 3 or (neighbours == 2 and previous_state == True)
                    new_board[y][x] = should_live

            self.state.board = new_board

    def neighbours(self, x, y):

        count = 0

        for hor in [-1, 0, 1]:
            for ver in [-1, 0, 1]:
                if not hor == ver == 0 and (self.infinite_board == True or (0 <= x + hor < self.width and 0 <= y + ver < self.height)):
                    count += self.state.board[(y + ver) % self.height][(x + hor) % self.width]

        return count

    def display(self):
        return self.state.display()

class State(object):

    def __init__(self, positions, x, y, width, height):

        active_cells = []

        for y, row in enumerate(positions.splitlines()):
            for x, cell in enumerate(row.strip()):
                if cell == 'o':
                    active_cells.append((x,y))

        board = [[False] * width for row in range(height)]

        for cell in active_cells:
            board[cell[1] + y][cell[0] + x] = True

        self.board = board
        self.width = width
        self.height = height

    def display(self):

        output = ''

        for y, row in enumerate(self.board):
            for x, cell in enumerate(row):
                if self.board[y][x]:
                    output += ' o'
                else:
                    output += ' .'
            output += '\n'

        return output

glider = """ oo.
             o.o
             o.. """

my_game = Game(State(glider, x = 2, y = 3, width = 10, height = 10))
print my_game.display()
my_game.step(27)
print my_game.display()

Output:

 . . . . . . . . . .
 . . . . . . . . . .
 . . o o . . . . . .
 . . o . o . . . . .
 . . o . . . . . . .
 . . . . . . . . . .
 . . . . . . . . . .
 . . . . . . . . . .
 . . . . . . . . . .
 . . . . . . . . . .

 . . . . . . . . . .
 . . . . . . . . . .
 . . . . . . . . . .
 . . . . . . . . . .
 . . . . . . . . . .
 . . . . . . o . . .
 . . . . . o o . . .
 . . . . . o . o . .
 . . . . . . . . . .
 . . . . . . . . . .

I have several concerns:

1. It feels a bit unnatural to write self.state.board[y][x], instead of [x][y]. However, I thought it would make sense to let the board be an array of rows rather than columns.

2. I'm not sure how to divide the tasks between the two classes. For instance, I could have implemented the neighbours() function in the State class, rather than in the Game class.

3. I know it's good practice to write a lot of comments, but I found most of this code self-explanatory (though that could be because I've just written it).

4. I used several nested for-loops, but maybe I could replace some with list comprehensions.

5. I could have left out the display() function of the Game class and just write print my_game.state.display() on the last line. Does this simplify things, or does it only make it more complicated?

Answer 1

This is excellent code for a Python novice.

To address your questions:

1. Rather than x and y, try naming your variables row and col. Then it wouldn't feel unnatural to write self.state.board[row][col].
2. In my opinion, the .neighbour() function would be better in the State class, since you're counting neighbours of a cell within that state.
3. Your code is easy to understand, partly because the rules of the game are well known. However, you should still write docstrings for your functions. It's not obvious, for example, what to pass for the state parameter to the Game constructor unless you read the code. (Should I pass a 2D array of booleans?)
4. You could use list comprehensions, but the current code is not bad either.

5. I would rename both of your display(self) functions to __str__(self). In Game, that function would become

   def __str__(self):
       return str(self.state)
   

   Then you can just print my_game.

Answer 2

To address all your questions in one go, you could consider a very simple implementation using only a couple of functions and the set data structure:

def neighbors(cell):
    x, y = cell
    yield x - 1, y - 1
    yield x    , y - 1
    yield x + 1, y - 1
    yield x - 1, y
    yield x + 1, y
    yield x - 1, y + 1
    yield x    , y + 1
    yield x + 1, y + 1

def apply_iteration(board):
    new_board = set([])
    candidates = board.union(set(n for cell in board for n in neighbors(cell)))
    for cell in candidates:
        count = sum((n in board) for n in neighbors(cell))
        if count == 3 or (count == 2 and cell in board):
            new_board.add(cell)
    return new_board

if __name__ == "__main__":
    board = {(0,1), (1,2), (2,0), (2,1), (2,2)}
    number_of_iterations = 10
    for _ in xrange(number_of_iterations):
        board = apply_iteration(board)
    print board

The main idea behind this solution is to keep track of only live cells. This way we don't have to scan the whole board each time we want to compute an iteration of the game. Another advantage also is we get to model infinite boards this way.

Thus a board is modeled as a set of cells using the set data type in python. Each cell is represented by a tuple (x, y) denoting the coordinates of the cell. The function neighbors simply takes in a cell and uses list distructering to extract the individual cell coordinates. The yield statement is used to return the eight neighboring cells in the order specified.

The function apply_iteration takes a board as input, applies an iteration and then and returns a new board. The idea is to compute a set of candidate cells (called candidates in the function) and then determine the new set of live cells for the next iteration. Notice how we can pass a generator expression as input to the set function. The candidate cells can simply be seen to be the union of the board with the set of neighbors of all cells in that board. The inner loop in the function applies the game's rules and adds any new living cells to the new_board variable which is returned as the result after the loop finishes execution.

The entry point of the program contains the initialization part as well as the loop which simulates the game for a specified number of iterations.

The main advantage of this solution over the one proposed by the OP is its simplicity. It also showcases some of Python's most powerful constructs such as parameter destructuring, the set data type and last but not least the yield statement.