Introduction to Computer Programming

Program 4: Conway's Game of Life

Due date: Tuesday, November 6 at 5pm



Conway's Game of Life

Your goal for this assignment is to implement Conway's Game of Life. You are encouraged to familiarize yourself with the game and its history. In particular, you should read "The fantastic combinations of John Conway's new solitaire game 'life'" by Martin Gardner from the October 1970 issue of Scientific American. (The final set of diagrams is not included in this version of the article, but that should not prevent you from understanding how the "game" works.) You are strongly encouraged to experiment with an existing implementation of the game such as this JavaScript version runnable in your Web browser or Golly (a very powerful downloadable version of the game).

grids v. boards

For purposes of this assignment, we need to distinguish between two related ideas: A grid is a list of lists of the same kinds of items (so a list of lists of Booleans, or of numbers, or really anything) where each interior list (row) is the same length (has the number of columns). If we refer to the dimensions of a grid as being "m by n" we mean it consists of n lists each of which consist of m values (i.e., the grid is m columns by n rows).

On the other hand, for this project, we define a board as a grid of numbers where the numbers are all either 1 or 0 and where the borders (the top and bottom rows and the leftmost and rightmost columns) are all 0. Because the border is not designed to change, we describe the dimensions of the board as ignoring the borders. So if the underlying grid is 7x5 (inclusive of the borders) then that is describing a 5x3 board. The overall grid might be:


but conceptually the inside of the board is just this


and the user would think there are active cells at these (column, row) coordinates:

(0, 0), (2, 0), (3, 0), (4, 0)
(0, 1), (1, 1), (4, 1)
(1, 2), (3, 2)

The choice to use 1 and 0 instead of True and False and use the extra border of 0 values is motivated by the simplicity it offers for counting how many active neighbors a cell has (see the count_neighbors function described below).

columns v. rows

It is important to remember that when specifying the total number of columns and rows in a board, each is just an integer, but the order matters. Likewise, when specifying the coordinate - the specific column and row of a cell in the board - both are integers and order matters. (3, 4) is not the same as (4, 3).

When using the paint method, the coordinates are specified as an ordered pair (a tuple of length two) where the first item in the pair is the horizontal (x) coordinate (the column number) and the second item is the vertical (y) coordinate (the row number).

However, the standard convention for representing a two-dimensional array is as a list of lists and thinking of that as a list of rows. This means we specify the row number first when accessing the elements directly in an array. So if we have a grid g, and wanted to refer to what is at position (3, 4) - i.e., column 3 (counting from 0) and row 4 (counting from 0), we would write:


This can lead to hard to find bugs where a value intended to specify a column number is instead used as a row index and vice versa. To combat that problem: 1) be aware of the potential problem; 2) test as you go; and 3) use non-square grids (usually we use more columns than rows because most computer screens are wider than they are tall) so that you either receive an index error (for instance if accidentally referring to an out-of-bounds row number when you intended it to be a column number), or the visual display of the grid seems rotated by 90 degrees.

ordered pairs

Ordered pairs in Python are tuples (immutable lists) of length two. In this assignment, the only ordered pairs we use will consist of two integers.

When passing dimensions into a function (how wide, how high), the arguments will be separate integers. For example, to create an empty grid, gol_repl calls:

gol_aux.make_empty_grid(columns + 2, rows + 2)

When referring to a coordinate pair, we use a tuple. For example, to fill the cell at column 7, row 4 with the color blue, we would write:

gol_graphics.paint((7, 4), 'blue')

Occasionally, it will be convenient to use tuples for the overall dimensions - most notably in functions that returns the dimensions of a board (since we can only return one value; but one tuple can contain two values). For example

(columns, rows) = gol_aux.get_dimensions(board)

graphics in Spyder

Not all of the functions you write for this assignment will be fruitful (meaning they do not all require a return statement), but they will all be independent of the details of using graphics in Python. The only two functions you should ever need from the supplied graphics module ( are paint and update (which forces the underlying graphics system to update the graphics on the screen - a quirk of the underlying system, but a quirk that allows us to control how fast our graphics are painted).

In many implementations of Conway's Game of Life, the user can interact with the board directly to activate or deactivate cells (for example, by clicking on cells). Later this semester we will learn how to do that, but it is a bit beyond our capabilities just now. Instead, a text-based REPL allows us to load patterns of cells into and out of the Game of Life board, to randomly configure the board, and more.

In Spyder, graphics windows open as a separate window from the main Spyder IDE window. In particular, the displayed grid for this assignment runs in a separate window from the iPython console. This means that if you have limited screen real estate (like on a normal sized laptop display), you may have to bring one or or the other of the windows (the graphics window or the main IDE window) into focus in order to interact with an executing Python graphics program. For instance, in the console there will be our usual style of text-based REPL, while in the graphics window you can see the evolution of an instance of Conway's Game of life. Examples:

Spyder: iPython console in front of graphics window

Spyder: iPython console in front of graphics window

Spyder: graphics window in front of iPython console

Spyder: graphics window in front of iPython console

Depending on your computer's Spyder configuration, when you quit running an instance of the assignment (gol_repl), the graphics window may not close. If that happens, simply restart the console from within Spyder.

loading and saving Game-of-Life patterns

The supplied Game of Life REPL (gol_repl) allows the user to load and save text files that represent game-board configurations. There are two different styles that can be used:

full boards: This text file is an example file showing a "glider" that can be loaded as a GOL board. When loading a full board (the load option), the current board is replaced entirely with the configuration represented in the file. Entire boards can be saved in this format using the save option.

active-cell patterns: This text file is an example showing another way a glider can be represented (as a list of active cells on a board, rather than as an entire board). When loading a pattern (the pattern option), only the specified coordinate pairs are turned "on". All other parts of the board remain as they were prior to loading the pattern. Likewise, saving the current configuration (the xtract option) creates a files consisting only of the coordinate pairs of cells that are "on".

starter archive

The starter archive is a zip file that represents a folder (hw4) which contains a collection of Python files and text files. The Python files are:

The text files are:

runnable solution

You are welcome (and encouraged) to experiment with the runnable solution module ( that is included in the starter archive. If you import that file in your working file ( as in:

import hw4x

then you can use it to (temporarily!) use my solutions if you get stuck on a problem so that you can proceed. For example, to make randomize_board work you could use:

def randomize_board(board, density):
    hw4x.randomize_board(board, density)

You can also run my full solution by temporarily modifying your file so that instead of having

import hw4 as gol

you use:

import hw4x as gol

The assignment itself

  1. Unpack the starter archive. That should create a folder called hw4 within the folder where you performed the extraction. Work entirely within the file Other than the first two problems, to test your work, run the module.

  2. Complete fill_grid(grid, fill_item) so that it sets every cell of grid to be fill_item. You can test this in the shell using the supplied grid_to_string as in this example:

    >>> import gol_aux
    >>> g = gol_aux.make_empty_grid(9, 5)
    >>> print(gol_aux.grid_to_string(g))
    >>> fill_grid(g, 1)
    >>> print(gol_aux.grid_to_string(g))
  3. Complete set_grid_border(grid, border_item) so that it sets the all the border cells of grid to be border_item. Keep your code simple, but also try to avoid redundant work (i.e., setting the same cell more than once). You should be able to test set_grid_border in the shell like this (continuing from previous example):

    >>> fill_grid(g, 1)
    >>> set_grid_border(g, 0)
    >>> print(gol_aux.grid_to_string(g))

  4. Complete paint_board(board) so that it draws the cells from within board onto the canvas via the supplied paint function. The board's "border" cells should not be drawn. Use nested loops. Completing this function should have an immediate impact when running the game REPL because we are using three distinct colors for the window's background color (BG_COLOR), the color of active cells (ACTIVE_COLOR) and inactive cells (INACTIVE_COLOR). Furthermore, the clear and fill options work by using fill_grid and set_grid_border so you can now visually test your solutions to the previous two problems by using the REPL.

  5. Complete set_cell(board, crp, active=True) so that it sets the cell at row-column pair crp in board to be "on" if active is True and "off" if not. You can assume column and row are integers. However, your code should check that they are within the range of the board. This is a side-effecting function that returns nothing. When successful it modifies board; when not (if the position is out of range), it indicates the invalid coordinates using print. Remember to take into effect the invisible "borders" of the board. In other words, calling set_cell(b, (5, 7)) should make the value of b[8][6] be 1. You can test this function by using the activate and deactivate options of the REPL.

  6. Complete toggle_cell(board, crp) so that it inverts the cell at row-column pair crp in board. This should be the same as activate_cell (i.e, its side effecting, it should check that the coordinates are within the range of the board, and, if not, should print a warning). Again, remember to take into effect the invisible "borders" of the board. Remember that the board consists of 1's and 0's, not Boolean values. Test this using the toggle action in the REPL.

  7. Complete randomize_board(board, density) so that it sets every non-border cell of the board to be a 1 with the probability indicated by density (which should be an integer between 0 and 100 - indicating the percent chance that any cell is to be filled). randomize_board(board, 0) is equivalent to clearing the board; randomize_board(board, 100) is equivalent to filling the board. randomize(board, 50) sets each cell as active or inactive with equal likelihood. Test using the randomize action in the REPL.

  8. Complete set_cells(board, pairs, active=True) so that it sets all the cells in board indicated by pairs which should be a list of row-column pairs to be active or inactive. Complete paint_list(color, pairs) so that it paints a color-colored square at each valid row-column pair in pairs. (Hint: These are meant to be simple exercises in looping over lists; call set_cell and paint.) When these are complete you can test them by using the pattern option in the REPL which will load a pattern from a text file consisting of a list of row-column pairs of active cells. For instance, if you start with a clear board and then load the glider.list.txt (included in the starter archive) you should see a glider pattern appear on the board. (Note: I have already supplied the code to read this sort of file and parse a string that represents a list of pairs.)

  9. Complete extract_cells(board) so that it returns a list of row-column coordinate pairs of the active cells in board. The coordinates should reflect their apparent positions (not their literal coordinates within the bordered grid); so, for example: if board[5][7] is 1 then the corresponding pair returned in the list should be (4, 6). Once completed that will make the xtract option of the REPL work correctly.

    These next three problems combine together to play Conway's Game of Life's for one generation. Namely, for every non-border cell in board: if a cell is currently active and has 2 or 3 active neighbors than it remains active; otherwise it becomes inactive. If a cell is currently inactive and has exactly 3 active neighbors it becomes active.

  10. Complete count_neighbors(board, crp) so that it returns the number of active cells that "touch" the specified location in board. For example, if board looks like:

    0 0 0 0 0
    0 0 0 1 0
    0 1 1 0 0
    0 0 1 0 0
    0 1 0 1 0
    0 0 0 0 0


    >>> count_neighbors(board, (0, 0))
    >>> count_neighbors(board, (2, 1))

    but count_neighbors(board, (3, 5)) should result in an error. (Since the coordinates are apparent, not actual.)

  11. Complete compute_changes(board) so that it returns a pair of lists: the first is a list of the apparent row-column coordinates of newly active cells (those that are "born"), the second is a list of apparent row-column coordinates of newly inactive cells (those they have just "died"). For the example above, the result might look like:

    >>> compute_changes(board)
    ([(1, 0), (2, 1), (2, 2), (1, 3)], [(2, 0), (1, 2), (0, 3), (2, 3)])

    (It might be different in exact form because the order of the the newly active cells within the first list - and likewise the order of the newly deactivated cells in the second list - depends on the exact order determined by your algorithm.)

  12. Complete evolve_once(board) so that it plays Conway's Game of Life for one generation. (Hint: use compute_changes, set_cells, and paint_list.) Test using the evolve once option in the REPL.

  13. Complete evolve_n(board, n) so the game is played for n generations. (This is meant to be almost trivial once the previous problems are complete. However, if you choose to do the challenge exercises you may eventually revisit this function.) Test using the go option in the REPL.

  14. Complete read_gridfile(columns, rows, filename) so that it reads filename (which can be assumed to be the valid name of readable text file) and returns a columns x rows board that corresponds to the contents of the file. The format of the file is: a description of the file (so it can be ignored, or printed out to the shell); the second line consists of the single-character symbol used in the remainder of the file to signify active cells in the grid. For example, see blinker.grid.txt and glider.grid.txt from the archive. You can assume that each row is specified on its own line; any character (including spaces) other than the active character represent inactive cells; each line is up to specified column width then everything else ignored on that line; if the line ends before the column width is reached, the row is padded to that width using 0s. Only the specified number of rows are read (anything after is ignored); if fewer than the specified number of lines are included, remaining rows are padded with 0s. Test the function by reading either of the example grid files using the load gridfile option in the REPL.

  15. Complete write_gridfile(filename, desc, board) so it writes the board as a gridfile using the same conventions outlined in the previous problem where the first line of the desc string is the used in the description line, and the dimensions of the board are determined in their usual way (using len). The written grid should exclude the 0-border of the underlying grid.

Challenge problems

Consider these problems only after completing all of the numbered problems above.