Introduction to (Web) Programming

Program 6: Conway’s Game of Life

Due date: Thursday, May 2 at 1:30pm

Instructions


Details

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

matrices v. and “the universe”

For purposes of this assignment, a matrix is an array of arrays (a.k.a. a two-dimensional array) where each of the internal arrays are of the same length and consist of the same kinds of items. You can assume that the matrices relevant this assignment consist solely of the numbers 0 and 1. The choice to use them instead of True and False is motivated by the simplicity it offers for counting how many active neighbors a cell has (see the countNneighbors function described below).

The main exercises for this assignment ask you to complete a pure JavaScript function - that is one that does not rely on the existence of the DOM. Many of the functions take an argument that is intended to be a two-dimensional array - those functions (e.g., toggleMatrix) are intended to work on any matrix you pass to the function. However, in gol-dom.js, we define a global variable gUniverse that is the matrix that represents the particular two-dimensional array representing the game-of-life board (the “universe”) which we are painting on an HTML canvas. In that file, many of the functions (e.g., drawUniverse) do not take a two-dimensional array as an argument but access or modify the global variable gUniverse.

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 coordinates - the specific column and row of a cell - both are integers and order matters. (3, 4) is not the same as (4, 3).

The standard convention for representing a two-dimensional array means 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 matrix m, 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:

 m[4][3]

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 and 2) test your code thoroughly as you proceed through the assignment.

loading and saving Game-of-Life patterns

The supplied archive includes a few text files (of the form glider.list.txt) that represent game of life patterns. The idea is that you can load such patterns onto the board by pasting the contents of the text file into the input area and then clicking the activate button. A completed assignment will also effectively give you the ability to save patterns by clicking the export button which will produce the list of coordinate pairs of active cells in the text input area. (To save, paste that list into a text file of your choosing.)

Here is a pattern representing a horizontal blinker:

3,4; 4,4; 5,4

starter archive

The starter archive is a zip file that represents a folder (hw6) which contains a collection of files:


The assignment itself

  1. Unpack the starter archive. That should create a folder called hw6 within the folder where you performed the extraction. You only need work in gol.js. You can test your work by opening gol.html in your browser and using the supplied interface (e.g., the buttons). In some cases, it may be helpful to test individual pure JavaScript functions using the console.


  2. Complete toggleMatrix(matrix) so that every cell of matrix is replaced by its complement: zeros becomes ones and vice versa. You can test this first by clicking the toggle button: it should alternate between a completely empty board and a completely full board with each click. You can further test your code after you complete the next problem (randomizeMatrix).

  3. Complete randomizeMatrix(matrix, density) so that it sets every element of matrix to be a 1 with the probability indicated by density (which should be a number between 0.0 and 1.0 indicating the percent chance that any cell is to be filled). Modifies matrix, but also returns the number of activated cells. randomizeMatrix(board, 0.0) is equivalent to clearing the board; randomizeMatrix(board, 1.0) is equivalent to filling the board. randomizeMatrix(board, 0.5) sets each cell as active or inactive with equal likelihood. Test by clicking on the randomize button and using the associated slider to select a density.


    This next series of problems (3-7) enables us to import a string representation of coordinates of active cells into a matrix and onto the corresponding canvas. You can implement the set of problems that follows (10-12) first to get the game going and then come back to these. However, it is harder to tell if a randomized matrix is evolving correctly than for a specialized set of cells (such as the glider pattern).

  4. Complete removeSpaces(s) so that it returns a string identical to s except with all spaces and newline symbols removed. This is a purely fruitful function and you can test it in the console. For example:

     > removeSpaces(' John Conway\n\n and his\nGame of Life! ')
     "JohnConwayandhisGameofLife!"
  5. Complete parsePair(pairString) so that if pairString is a string containing a comma-separated pair of numbers and such that those two numbers are integers then it returns a pair (a two-element array) of the numbers. If not, it returns null. You can assume that pairString has no spaces (nor newlines) in it. This is also a purely fruitful function and can be tested independently of the rest of the assignment. Use .split. Examples:

     > parsePair('37,41')
     [37, 41] 
     > parsePair('(37,41)')
     null
     > parsePair('37.1,41')
     null
     > parsePair('37,   41')
     null
     > parsePair('37,y')
     null
  6. Complete parsePairs(pairsString) so that it returns an array of pairs of integers that correspond to all the validly parsed pairs of integers contained within pairsString, each pair separated by a semicolon. You can assume that pairsString has no spaces (nor newlines) in it. Use .split and call parsePair. This should not quite be a purely fruitful function: for each pair that cannot be parsed successfully a warning message should be displayed in the console indicating that fact. After you complete the next two problems (setCell and setCells), this function can be tested by typing (or pasting) a semicolon-separated list of integer pairs (themselves comma separated) into the input textarea and clicking on activate (or deactivate). You can also test your function in the console like so:

     > parsePairs('3,4;9,22;15,6')
     [[3, 4], [9, 22], [15, 6]]

    An example of something that will work partially is:

     > parsePairs('3,4;9,22;THIS_IS_NOT_A_COORDINATE_PAIR!;15,6')
     [[3, 4], [9,22], [15, 6]]

    but should produce this warning message in the console:

     unable to parse coordinate pair: THIS_IS_NOT_A_COORDINATE_PAIR!
  7. Complete setCell(matrix, x, y, it) so that it sets the cell in matrix at position column x, row y to be it. You can assume x and y are integers. However, your code should check that they are within the range of the matrix. This is a side-effecting function that returns nothing. When successful it modifies matrix; when not (if the position is out of range), it indicates the invalid coordinate by displaying a warning in the console. (This problem is intended to be easy!)

  8. Complete setCells(matrix, pairs, isOn) so that assuming pairs is an array of pairs of integers (i.e., an array of arrays of integers where the inner arrays are all of length two), it attempts to turn on (if isOn is true) or off (if isOn is false) all the cells at the locations indicated by those pairs. This is a side-effecting function that implicitly modifies matrix (by calling setCell with its last argument as either 1 or 0); it returns nothing. It may indirectly (via setCell) display warning message in the console if any of the pairs are out of range.

    The previous five functions combined should make it easy to paste lists of cells to turn on and off. For example, if the universe is empty and the following is pasted in the input area and activate is clicked, the universe should now contain a horizontal blinker:

      3,4; 4,4; 5,4
  9. Complete getCells(matrix) so that it, assuming matrix is a two-dimensional array of numbers, it returns an array of pairs (themselves length-two arrays of integers corresponding to column-row coordinates) for each entry nonzero entry in matrix. For example:

     > let mat = [
           [0, 0, 1, 0],
           [0, 1, 0, 1],
           [1, 1, 1, 0]];
     > getCells(mat)
       [[2, 0], [1, 1], [3, 1], [0, 2], [1, 2], [2, 2]]
  10. Complete pairsToString(pairs) so that it returns a string representation of pairs, assuming pairs is an array of pairs (themselves length-two arrays of integers) where each pair is comma-separated, and the pairs themselves are semicolon-separated as in (continuing from the previous example):

     > pairsToString(getCells(mat))
       "2,0;1,1;3,1;0,2;1,2;2,2"

    Use .join. You can test the above two functions by clicking export when the universe is not empty - that should produce a string like the above one in the input area (and selected so that a simple copy and paste into a text file can be used to save the current contents of the universe).


    These next three problems combine together to play Conway’s Game of Life’s for one generation. Namely, for every cell in our universe if a cell is currently active and has 2 or 3 active neighbors then it remains active; otherwise it becomes inactive. If a cell is currently inactive and has exactly 3 active neighbors it becomes active.

  11. Complete countNeighbors(matrix, x, y) so that it returns the number of active cells that “touch” the specified column-row location in matrix. For example:

     > let mat = [
           [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]];
     > countNeighbors(mat, 4, 0)   // upper right corner
     1
     > countNeighbors(mat, 2, 3)
     4

    You can (and should) assume that x and y are valid coordinates.

  12. Complete computeChanges(matrix) so that it returns a pair of arrays: the first is an array of the column-row coordinates of newly active cells (those that are “born”), the second is an array of column-row coordinates of newly inactive cells (those that have just “died”). For the example above, the result might look like:

     > computeChanges(mat)
       [[[2, 1], [3, 2], [3, 3], [2, 4]],
        [[3, 1], [2, 3], [1, 4], [3, 4]]]

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

  13. Complete evolve(matrix) so that it plays Conway’s Game of Life for one generation. This is a side effecting function (it modifies matrix), but it should also return a pair of numbers indicating how many new cells were created and how many old cells were deactivated. (Hint: use computeChanges and setCells.) Test by clicking evolve.



Challenge problems

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


You are encouraged to experiment with the demonstration version. To experiment more directly with the solutions, you can open up on a console while viewing this page and try examples such as:

 > parsePairs('3,4;9,22;15,6')