Homework 2 - Game of Life

Due Friday, February 4.

Be sure to read this entire file! There's some code at the end to help you.

Please turn in a HARDCOPY of your source code with your NAME and STUDENT ID...thanks!

For this homework, you will implement a program which allows a user to play the "game of life". This isn't really much of a game (as we normally think of the term).

The game of life was invented by the mathematician John Conway and popularized by Martin Gardner's popular Scientific American column. (See the book _Wheels, Life, and Other Mathematical Amusements_ by Martin Gardner for the original articles.) Here's a link for those who would like to learn more.

The game of life is played on a two-dimensional grid. Each cell of the grid is either "on" or "off" ("alive" or "dead"). The grid will be represented using a 2-D array in C, with values 1 and 0 representing "alive" and "dead", respectively.

The board can be set up however one likes (call this initial configuration of the board the configuration at time = 0), and then, there is a set of rules for computing the board at time = 1, time = 2, etc. (Notice that time increases discretely.) As an example, our initial board (6 x 6) might look like the following. Asterisks represent cells that are alive; spaces represent cells that are dead.

| | | | | | |
| | | | | | |
| | |*|*|*| |
| | | | | | |
| | | | | | |
| | | | | | |

Notice that cells not on the border of the board have eight "neighbors". In the small grid below, the cell marked X has eight neighbors, labelled with the numbers 1-8:

|1|2|3|
|4|X|5|
|6|7|8|

Cells on the border of the board have fewer neighbors. For instance, a cell in the corner has only three neighbors. Given a board, to find the board configuration at the next time step, we do the following:

1. Get out a new board (make another array);

2. On the new board, cells are on or off according to the following rules:

a) If a cell on the original board has 0 or 1 neighbors, the corresponding cell on the new board dies from isolation. If the cell on the original board has 4, 5, 6, 7, or 8 neighbors, the corresponding cell on the new board dies from overpopulation.

b) If the original cell (i) has exactly two neighbors, OR (ii) the original cell has three neighbors and is alive, the corresponding cell on the new board inherits the value of the original cell.

c) Finally, there are births: if the original cell is off but has exactly three neighbors, it becomes alive in the new board.

Check your understanding of the rules by examining a sample interaction with my program (note that I allow the user to "set up" an initially blank board by asking for a sequence of coordinates to be toggled; also note that the coordinate system starts at 0, corresponding to the fact that arrays in C are zero-indexed):

Here's the current board:
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |

Enter a y coordinate to be toggled, or -1 to stop: 1
Enter a x coordinate to be toggled, or -1 to stop: 0
Here's the current board:
| | | | | | |
|*| | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |

Enter a y coordinate to be toggled, or -1 to stop: 1
Enter a x coordinate to be toggled, or -1 to stop: 1
Here's the current board:
| | | | | | |
|*|*| | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |

Enter a y coordinate to be toggled, or -1 to stop: 1
Enter a x coordinate to be toggled, or -1 to stop: 2
Here's the current board:
| | | | | | |
|*|*|*| | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |

Enter a y coordinate to be toggled, or -1 to stop: 0
Enter a x coordinate to be toggled, or -1 to stop: 5
Here's the current board:
| | | | | |*|
|*|*|*| | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |

Enter a y coordinate to be toggled, or -1 to stop: 4
Enter a x coordinate to be toggled, or -1 to stop: 4
Here's the current board:
| | | | | |*|
|*|*|*| | | |
| | | | | | |
| | | | | | |
| | | | |*| |
| | | | | | |

Enter a y coordinate to be toggled, or -1 to stop: 4
Enter a x coordinate to be toggled, or -1 to stop: 5
Here's the current board:
| | | | | |*|
|*|*|*| | | |
| | | | | | |
| | | | | | |
| | | | |*|*|
| | | | | | |

Enter a y coordinate to be toggled, or -1 to stop: 5
Enter a x coordinate to be toggled, or -1 to stop: 4
Here's the current board:
| | | | | |*|
|*|*|*| | | |
| | | | | | |
| | | | | | |
| | | | |*|*|
| | | | |*| |

Enter a y coordinate to be toggled, or -1 to stop: 5
Enter a x coordinate to be toggled, or -1 to stop: 5
Here's the current board:
| | | | | |*|
|*|*|*| | | |
| | | | | | |
| | | | | | |
| | | | |*|*|
| | | | |*|*|

Enter a y coordinate to be toggled, or -1 to stop: 3
Enter a x coordinate to be toggled, or -1 to stop: 5
Here's the current board:
| | | | | |*|
|*|*|*| | | |
| | | | | | |
| | | | | |*|
| | | | |*|*|
| | | | |*|*|

Enter a y coordinate to be toggled, or -1 to stop: 2
Enter a x coordinate to be toggled, or -1 to stop: 5
Here's the current board:
| | | | | |*|
|*|*|*| | | |
| | | | | |*|
| | | | | |*|
| | | | |*|*|
| | | | |*|*|

Enter a y coordinate to be toggled, or -1 to stop: -1


How many time steps would you like to see? 4

Board at time 0:
| | | | | |*|
|*|*|*| | | |
| | | | | |*|
| | | | | |*|
| | | | |*|*|
| | | | |*|*|

Board at time 1:
| |*| | | | |
| |*| | | | |
| |*| | | | |
| | | | | |*|
| | | | | | |
| | | | |*|*|

Board at time 2:
| | | | | | |
|*|*|*| | | |
| | | | | | |
| | | | | | |
| | | | |*|*|
| | | | | | |

Board at time 3:
| |*| | | | |
| |*| | | | |
| |*| | | | |
| | | | | | |
| | | | | | |
| | | | | | |

Board at time 4:
| | | | | | |
|*|*|*| | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |

And finally, here's some of my code. Please flesh out the functions which are blank. Feel free to add other functions, but please implement the given functions as described. Don't forget a main function!

(Note that I have

#define SIZE 6

at the top of my code.)

/* print_board prints out the board, representing live cells with asterisks
   and dead cells with spaces.  It is assumed that board contains
   non-zero values for live cells and zero values for dead cells. */

void print_board( int board[SIZE][SIZE] )
{
  int i, j;
  for( i = 0; i < SIZE; i++ )
    {
      printf( "|" );
      for( j = 0; j < SIZE; j++ )
	{
	  if( board[i][j] ) printf( "*|" ); 
	  else printf( " |" );
	}
      printf( "\n" );
    }
  printf( "\n" );
}


/* clear_board sets every "cell" in the board to zero ("dead") */
void clear_board( int board[SIZE][SIZE] )
{
  int i, j;
  for( i = 0; i < SIZE; i++ )
    {
      for( j = 0; j < SIZE; j++ )
	{
	  board[i][j] = 0;
	}
    }
}


/* user_init_board allows the user to type in coordinates to be toggled
 */

void user_init_board( int board[SIZE][SIZE] )
{
  /* YOUR CODE HERE */
}


/* given the number of neighbors (assumed to be in the range 0-8)
   and the original value of a cell (assumed to be 0 or 1),
   new_value returns the value of this cell at the next time step 
   (0 or 1) */

int new_value( int num_neighbors, int old_value )
{
  /* YOUR CODE HERE */
}


/* value_of_cell returns board[y][x] so long as y and x are not
   out of bounds.  Otherwise, 0 is returned. */

int value_of_cell( int board[SIZE][SIZE], int y, int x )
{
  /* YOUR CODE HERE */
}


/* copy_board copies the array source_board into the array target_board */

void copy_board( int source_board[SIZE][SIZE], int target_board[SIZE][SIZE] )
{
  int i, j;
  for( i = 0; i < SIZE; i++ )
    {
      for( j = 0; j < SIZE; j++ )
	{
	  target_board[i][j] = source_board[i][j];
	}
    }
}


/* number_neighbors returns the number of neighbors that the cell
   board[y][x] has (an integer in the range 0-8) */

int number_neighbors( int board[SIZE][SIZE], int y, int x )
{
  /* YOUR CODE HERE */
}


/* update_board accepts a board, and updates it one time step */

void update_board( int board[SIZE][SIZE] )
{
  int new_board[SIZE][SIZE];

  /* YOUR CODE HERE: compute new_board from board using the given
     transition rules */

  copy_board( new_board, board );
}