Here are the new partnerships and here's a link to GitHub.

Lab 7 Goals:

• Use 2D arrays
• Write file I/O code
• Time parts of a program's execution
• Use pointers, dynamic memory, and pass by reference
• Devise your own test case
• Use valgrind and gdb for debugging

Contents:

• Overview
• Details
• Additional Requirements
• Hints, Tips, and Resources

For this lab, you will implement Conway's Game of Life. Devised by mathematician John Conway, Life is a grid-based simulation that demonstrates how complex behavior can emerge from simple rules. At each discrete time step, every cell in the grid is either "alive" or "dead." The cells get updated for the next time step based on how many of the eight adjacent cells contain alive cells (neighbors).

1. An alive cell with zero or one neighbors dies of loneliness.
2. An alive cell with four or more neighbors dies from overpopulation.
3. An alive cell with two or three neighbors stays alive.
4. A dead cell with exactly three neighbors becomes alive.

This video shows one solution to this lab in action:

You should represent the grid (or board) using a two-dimensional array, where a value of 0 indicates a dead cell and 1 indicates an alive cell. So that every cell in the board can have eight adjacent cells, we will think about the board as a torus. That is, cells on one edge of the board are considered adjacent to cells on the opposite edge.

In the boards shown below, cells marked with an 'x' are adjacent to the cell whose value is shown as 1.

0  x  1  x  0  0  0              x  0  0  0  0  x  x
0  x  x  x  0  0  0              0  0  0  0  0  0  0
0  0  0  0  0  0  0              0  0  0  0  0  0  0
0  0  0  0  0  0  0              0  0  0  0  0  0  0
0  0  0  0  0  0  0              0  0  0  0  0  0  0
0  0  0  0  0  0  0              x  0  0  0  0  x  x
0  x  x  x  0  0  0              x  0  0  0  0  x  1

Note that you cannot update the board in-place (with a single 2D array). As soon as you change the value held in a particular cell, you have also changed the neighbor counts for this cell's adjacent cells. So you will need two boards to run the simulation. On even-numbered iterations you will count neighbors using board #1 and write updates to board #2. On odd-numbered iterations, do the reverse.

Your program will read in a file that specifies the initial board configuration and the number of iterations to simulate. (Each iteration corresponds to one time step / board update.) The format of the input files is as follows:

number of rows
number of columns
number of iterations
numbers of cells that are alive initially
row index and column index of first alive cell
row index and column index of second alive cell
...

Here's an example of a valid input file (walker.txt):

10
10
50
5
9 1
8 2
7 0
7 1
7 2

If your program read in this file, it would start with a 10 by 10 board like the one below, and then update the board 50 times.

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

Your program will take two command line arguments. The first is the name of the configuration file. The second indicates whether the board updates should be animated (1) or whether we only care to see how long the updates took to compute (0).

$ ./gol oscillator.txt  0
19 iterations of a 19x19 board took 0.000665 seconds.
$ ./gol oscillator.txt  1
- - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - -
- - - - - - - - @ @ @ - - - - - - - -
- - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - -
number of live cells: 3
19 iterations of a 19x19 board took 3.872943 seconds.

In the second example run above, you are seeing the final board. Along the way the program should show all the intermediate boards.

• Use dynamically allocated memory to store the two boards.
• This link describes two methods for storing dynamically allocated 2D arrays in C. Use "Method 1," the more memory efficient option.
• When the second command line argument is 1, animate the Game of Life iterations. For each iteration, show what the board currently looks like and print the total number of alive cells at that point in the simulation.
• Handle invalid command lines by printing an error message and exiting the program. Any time you call a function that returns a status code, check this value and respond appropriately. If the function fails, print an error message and exit. You may assume that the input files are well-formed.
• In addition to the input files provided (oscillator.txt, walker.txt, and grow.txt), write one or more of your own input files. In the questionnaire, describe what your input file was designed to test or showcase about the program. For isntance, you may want input files that specifically test updates at the edges and corners of the board. Or you may want to test your program on a board that isn't a square.
• Time how long it takes to run the entire simulation, not including the time it takes to initialize the board. Do this regardless of whether the second command line argument is 0 or 1.
• Define and use at least three functions in addition to main. Each function needs a descriptive comment.
• Don't use global variables.
• Remove all valgrind errors from your program.

• Start with a top-down design that delegates high-level tasks to functions. For instance, you may want to define functions that: initialize the board, print the board, update the board, and count how many neighbors a particular cell has.
• Remember that a function can return a pointer. This may be useful if you have an initialization function that returns a pointer to the malloc'ed and initialized game board.
• The function calls usleep(microseconds) and system("clear") will be helpful for doing the animation. usleep pauses the program for the specified number of microseconds and system("clear") erases everything that has been printed in the terminal window.
• Use the gettimeofday function to time things. This function returns the current time as the number of seconds and microseconds that have passed since the Epoch (Jan 1, 1970). A single time value can be calculated by adding these two fields together. However, these fields are in different units, so be sure to convert one to one to the other before adding them.

  struct timeval start_time, stop_time;
  ...
  ret = gettimeofday(&start_time, NULL);
  // code you want to time
  ret = gettimeofday(&stop_time, NULL);
  

  The timeval struct is defined in the sys/time.h library.

  struct timeval {
    time_t      tv_sec;     /* number of seconds */
    suseconds_t tv_usec;    /* number of microseconds */
  };
  

  See the man page (man gettimeofday) for more information.
• atoi converts a string to an integer. For example, int x = atoi("1234"), assigns x the int value 1234.
• The code from this week's lab session contains examples of file I/O, getting command line arguments, using gettimeofday, and dynamic 2D arrays.
• This reference contains some information about file I/O in C.
• You do not need to read all of a file's contents at once. Your program can read part of a file, do something else, and then later read more of the file. If you do this, you may need to pass the file pointer to multiple functions.
• If you want to try printing in color, here is one way to do it:

  printf("%s", "\e[1;31mThis prints Red\e[0m");
  printf("%s", "\e[1;32mThis prints Green\e[0m");
  printf("%s", "\e[1;33mThis prints Yellow\e[0m");
  printf("%s", "\e[1;34mThis prints Blue\e[0m");
  printf("%s", "\e[1;35mThis prints Magenta\e[0m");
  printf("%s", "\e[1;36mThis prints Cyan\e[0m");
  printf("%s", "\e[1;37mThis prints White\e[0m");