1. Due Date

  • Due 11:59 PM, Tuesday, April 7th

Your partner for this lab is: Lab 6 Partners

CS31 Partner Etiquette and Expectations.

Game of Life

2. Lab Goals

  • Experience with 2D arrays, command line arguments.

  • Gain additional practice with pointers, dynamic memory allocation, and passing pointers to functions.

  • Measure the execution time for parts of your program’s execution.

  • Gain expertise in gdb and valgrind for debugging C programs.

  • Designing input files to test correctness of your solution.

3. Handy References

Lab Video Links:

4. Lab Overview

For this lab, you will implement a program that plays Conway’s Game of Life. Conway’s Game of Life is an example of discrete event simulation, where a world of entities live, die, or are born based based on their surrounding neighbors. Each time step simulates another round of living or dying.

Your world is represented by a 2-D array of values (0 or 1).

If a grid cell’s value is 1, it represents a live object; if it is 0, it represents a dead object.

At each discrete time step, every cell in the 2-D grid gets a new value based on the current value of its eight neighbors:

  1. A live cell with zero or one live neighbors dies from loneliness.

  2. A live cell with four or more live neighbors dies due to overpopulation.

  3. A dead cell with exactly three live neighbors becomes alive.

  4. All other cells remain in the same state between rounds.

Your 2-D world should be a torus (a well known example of a torus is a donut), meaning every cell in the grid has exactly eight neighbors, even if it is on the edge of the grid. In the torus world, cells on the edge of the grid have neighbors that wrap around to the opposite edge.

For example, the grid locations marked with an 'x' are the eight neighbors of the grid cell whose value is shown as @.

             x  @  x  _  _  _  _
wraps        x  x  x  _  _  _  _
around       _  _  _  _  _  _  _
to the  <==  _  _  _  _  _  _  _
rightmost    _  _  _  _  _  _  _
column       _  _  _  _  _  _  _
             x  x  x  _  _  _  _

                     ||
                     \/
            wraps around to the top
            most row.

The Conway’s Game of Life description from Wikipedia shows some example patterns you can use to test the correctness of your solution (like Blinker, Toad or Beacon).

5. Getting Started

5.1. Getting Your Lab 6 Lab Repo

Both you and your partner should clone your Lab repo into your cs31/labs subdirectory:

  1. get your Lab ssh-URL from the CS31 git org. The repository to clone is named Lab06-user1-user2, where user1 and user2 are the user names of you and your Lab partner.

  2. cd into your cs31/labs subdirectory:

    $ cd ~/cs31/labs
$ pwd

  3. clone your repo

    $ git clone [your Lab06-user1-user2 url]
$ cd Lab06-user1-user2
$ ls
Makefile   gol.c	   oscillator_output  test_corners.txt
README.md  oscillator.txt  test_bigger.txt    test_edges.txt
commandlineargs.c twoDarray.c

5.2. Starting Point Code

The text files included in your repo are:

  • Makefile: builds gol executable file

  • README.md: some notes to you

  • oscilator.txt: an example input file to gol (you should create more as you test your solution)

  • oscilator_output: example output from a working solution. See Section 8 to see how you would compare your output with mine.

  • test_corners.txt, test_edges.txt: input test files for wrapping around.

  • test_bigger.txt: an input file for you to test on larger worlds and compare timings of run modes 0 and 1.

Code files in your repo:

  • gol.c: starting point for GOL lab. Your solution goes here.

  • twoDarray.c: examples to try out dynamically allocating, printing, manipulating 2D array.

  • commandlineargs.c: example that takes in multiple commandline inputs in main, and converts a string to an integer.

6. Implementation Details

Your program will take two command line arguments. The first is the name of a configuration file that specifies how to initialize the game-playing variables (dimensions of the grid, number of iterations, and initial values of the grid cells). The second is an integer flag (0 or 1) that indicates the game’s output mode – i.e. how its output should be displayed. The output mode values mean:

  • Mode 0: run gol with no output (this mode only outputs final game state statistics, including timing information about how long it took to run)

  • Mode 1: run gol with ascii animation (this mode also includes timing and outputs final game state statistics)

Here are some examples of valid command line invocations of the program:

# run with config values read from file1.txt and does not print the board
# state as runs (does print out total time and live cells at the end):
./gol file1.txt  0

# run with config file file2.txt and do ASCII animation, printing
# the board state after each step (plus total time and live cells at end)
./gol file2.txt  1

6.1. File Format

The input file format consists of several lines of ASCII text.

  • The first three lines specify the grid dimensions and number of iterations.

  • The fourth line lists the number of coordinate pairs that will follow.

  • The remaining lines specify i j (row index, column index) coordinate values to indicate which grid cells should be initialized to 1 (alive) at startup (all others should be 0 / dead). The origin (0,0) is the top left corner.

number of grid rows
number of grid cols
number of iterations to simulate
number of coordinate pairs (set each (i, j) value to 1) that come next
i j
i j
...

You may assume that the grid will have at least four rows and four columns. In other words, you do not need to worry about weird cases (e.g., 2x2 grid) in which another cell is both the left and right neighbor at the same time.

6.2. Create your own input files

You can create your own input files by writing text that conforms to the file input format specification. For example, a file with the following contents generates an interesting pattern that starts in the lower left and walk up to upper right of grid:

30
30
100
5
29 1
28 2
27 0
27 1
27 2

6.3. Computing Values at Each time step

One problem you will need to solve is how to update each grid cell value at each time step. Because each grid cell’s value is based on its neighbor’s current value, you cannot update each cell’s new value in place (otherwise its neighbors will read the new value and not the current value in computing their new value).

6.4. Reading Command line arguments and atoi

Let’s look at an example C program that takes command line arguments. Open commandlineargs.c in an editor. Note is the change in main’s definition: int main(int argc, char **) { …​ .

The first parameter to main, argc, is the number of command line arguments. For example, if the user enters:

./prog hello 1234 cs31

Here, argc= 4. The name of the program prog counts as the first input, and hello, 1234, and cs31 are the next three inputs. Each command line argument is passed to main in the second parameter, argv, as a string.

argv is an array of strings:

        -----
argv[0]:| *-|-----> "./prog"
        -----
argv[1]:| *-|-----> "hello"
        -----
argv[2]:| *-|-----> "1234"
        -----
argv[3]:| *-|-----> "cs31"
        -----
argv[4]:| *-|-----|     (NULL pointer: no more command line strings)
        -----

atoi()

In the example above, we often don’t want the string "1234", but instead an integer whose value is 1234. In Python, we use int() to do the conversion. In C, we use atoi to convert from an ASCII string to an integer. atoi stands for "ASCII to integer". See the man page for more information (man atoi).

int x = atoi(argv[2]);  // x gets the int value 1234
Try compiling and running this program with different command line arguments and see what happens.

6.5. Dynamically Allocated 2-D Arrays in C

Read through Method 1:Memory Efficient Allocation in the textbook. This is the method we will be using in this lab to dynamically allocate 2D arrays.

Next, let’s open twoDarray.c and look at two different ways in which 2D arrays can be declared, allocated, and accessed in C.

7. Example Output

Here is an example of what you might see from different runs. We’re printing '@' for live cells and '_' for dead ones because it is easier to see than '0' and '1' characters.

The first example shows the end board configuration from a run that is initialized to run from the oscillator.txt config file. And, the second is the same configuration, but run with 0 as the second parameter (notice the time difference between the two):.

# a run with output might end like:
$ ./gol oscillator.txt 1
@ : alive
- : dead
Round: 20
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
 _ _ _ _ _ _ _ _ @ @ @ _ _ _ _ _ _ _ _
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
Live cells: 3


Total time: 2.074092

A run with 0 as the second parameter should print no output the total time then measures just the gol computation part because the prints and sleeps should not be executed.

$ ./gol oscillator.txt 0
Total time: 0.001066

7.1. Correctness Testing

Part of this lab involves you designing gol input files that are desgined to test, debug, and verify the correctness of different aspects of your gol solution. We suggest that you start with some input files to test small, simple worlds.

  • With the starting point code are three test files to use for your own testing, and submit with your solution. You are welcome to, and encouraged to, submit more test files than these three, but these are required:

    1. test_edges.txt: this file creates a board used for testing and verifying the correctness of updating edge cells (cells on the north, or south, or east, or west edge of the grid, but not including the corner cells). This file includes a test for jsut one of the 4 edges. You should test all edges with seperate test files for each edge.

    2. test_corners.txt: this file creates a board used for testing the correctness of updating one or more of the 4 corner cells. Like the test_edges.txt file, this does not include a test for all 4 corners simultaneously; it can test just one of the corners. You should, however, make sure you have additional files that you use to test the other 3 corners for correctness.

In addition to these, you will want to create other input files to test correctness and features of your solution, and also just for fun!

8. Requirements

Design

  • Your solution should be well-commended and apply good top-down design, dividing functionality into functions. Consider the big steps: initializing the game board, updating one round of play, printing the game board, etc.

    • main has calls to high-level functions that perform each of the big steps (listed above).

    • The high-level functions in turn should use helper functions to implement well-defined pieces of functionality.

    • Generally, a function should not exceed 100 - 150 lines. There are exceptions, but if your function is getting really long, break it up into several parts, each implemented by a separate helper function.

Input/Output

  • Your program must take only two command line arguments: the config file name and an integer to determine the output mode:

    • 0: Report the time at the end, but don’t print the board to the terminal.

    • 1: Report the time at the end and print the board at each iteration.

When running in output mode 1, you should print the board using the provided print_board function’s formatting. That is, you should NOT make changes to the fprintf(stderr, …​) that are already there.

  • You are welcome to add your own printf() calls though. Feel free to contact your instructor(s) for help with output formatting. You can verify that your output conforms to the expected format (for easier grading) by comparing your output against mine with the diff command:

    # Run your program and save all the fprintf output to a file named output.txt
./gol oscillator.txt 1 2> output.txt

# Compare your output against mine
diff -u -s output.txt oscillator_output.txt

    • If formatted correctly, you’ll see: "Files output.txt and oscillator_output.txt are identical".

    • If not, you’ll see output that compares how the two files differ.

Starting Code/Dynamic Allocation

  • Your starting code has timing information given to you. Use this to print out the total time for the GOL simulation at the end of the simulation.

  • Your starting code uses the C FILE interface (fopen, fscanf, etc.) for file I/O. Look through the detection and handling of errors, (calling exit(1) if the error is unrecoverable) to understand I/O.

do not just assume that every function call and every C library or system call is always successful!

  • The GOL board(s) should be dynamically allocated on the heap according to the grid dimensions specified in the input configuration file.

    • See the example from lab as well as Arrays in C for more information.

  • Your solution should not use global variables. Instead, the board(s) and other variables should be passed to the functions that need them using the provided gol_data struct. If you want a function to change the value of an argument, remember you need to pass that argument as a pointer.

Full Credit

  • For full credit, your solution should be correct, robust, and free of valgrind errors. You should get no errors or warnings for output modes 0 and 1.

9. Tips

  • Implement and test incrementally! Use valgrind as you go to catch memory access errors as you make them.

  • As you test and debug, you may find it useful to use config files with small numbers of iterations and to comment out the call to system(clear) so you can examine the results of every intermediate iteration.

  • Recall that passing pointers to a function allow you to "return" more than one value from a function, since that function’s execution can have "side effects" that modify the value that’s pointed to.

  • usleep: pauses the program for some number of micro seconds. This is useful in print mode to slow down your program after each step so that you can see what it is doing. About .2 seconds is a good amount to sleep:

    usleep(100000);  // sleep for 100,000 micro seconds (0.1 seconds)

  • system("clear"); clears the text on the terminal so that the next output is at the top of the window (useful for printing the grid at each timestep to the same window location).

  • atoi converts a string to an integer. For example, int x = atoi("1234"), assigns x the int value 1234. This is useful in your command line parsing functions for converting command line arguments that are read in as strings to their numeric values. See the man page for atoi for other similar functions to convert stings to other numeric types (man atoi).

  • CNTRL-C will kill your program if it seems to be stuck in an infinite loop.

10. Submitting

Please remove any debugging output prior to submitting.

To submit your code, simply commit your changes locally using git add and git commit. Then run git push while in your lab directory. Only one partner needs to run the final push, but make sure both partners have pulled and merged each others changes. See the section on Using a shared repo on the git help page.