Introduction to Computer Programming

Program 4: Conway's Game of Life

Due date: Tuesday, November 7 at 5pm


Instructions


Background

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. (Note the final set of diagrams is not included in this version of the article, but it should not detract too much from communicating the main points.) You are also 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).

For purposes of this assignment, we need to distinguish between two related ideas: As we have been doing in class, we will say that 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 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 m lists each of which consist of n values (i.e., the grid is m rows by n columns).

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 5x7 (inclusive of the borders) then that is describing a 3x5 board. The overall grid might be:

0000000
0101110
0110010
0010100
0000000

but conceptually the inside of the board is just this

10111
11001
01010

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

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

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


Not all of the functions you write will be fruitful, but they will all be independent of the details of using turtle graphics in Python. The only two functions you should ever need from the supplied graphics module (gol_graphics.py) are paint (which is just like what we used in lab to "stamp" a colored square at a given row-column location) and update (which can be used to force the underlying graphics system to update the graphics on the screen - a quirk of the underlying turtle system, but a quirk that allows us to control how fast our graphics are painted).

In a normal GUI-version of Conway's Game of Life, the user can interact with the canvas directly to activate or deactivate cells. Later this semester we will learn how to do that, but it is a bit beyond our capabilities just now. Instead, we will implement a simple way to use text-based input in a REPL to load patterns of cells into and out of the Game of Life board.

This text file is an example file showing a "glider" that can be loaded as a GOL board. 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).


The 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 (hw4x.py) that is included in the starter archive. If you import that file in your working file (hw4.py) 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 gol_repl.py file so that instead of having

import hw4 as gol
    

you use:

import hw4x as hw4

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 hw4.py. Other than the first two problems, to test your work, run the gol_repl.py 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(5, 9)
    >>> 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. (Hint: this should be very similar to the paint_grid function from Lab 6. The distinction is that board's "border" cells should not be drawn.) It 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, rcp, active=True) so that it sets the cell at row-column pair rcp 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[6][8] be 1. You can test this function by using the activate and deactivate options of the REPL.

  6. Complete toggle_cell(board, rcp) so that it inverts the cell at row-column pair rcp 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.


  10. 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.

    Complete count_neighbors(board, rcp) 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

    then

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

    but count_neighbors(board, (5, 3)) 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)
    ([(0, 1), (1, 2), (2, 2), (3, 1)], [(0, 2), (2, 1), (3, 0), (3, 2)])

    (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 some optional exercises you may eventually revisit this function.) Test using the go option in the REPL.


  14. Complete read_gridfile(filename) so that it reads filename (which can be assumed to be the valid name of readable text file) and returns a 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 three semicolon-separated values: the number of rows in the board, the number of columns, and the symbol used in the remainder of the file to signify active cells in the grid. For example, see ... and ... 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 any 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 determined in their usual way (using len). The written grid should exclude the 0-border of the underlying grid.


Extra credit

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