Sp07 CS61C Homework 2: Conway's Game of Life
TA: David Eitan Poll (cs61c-tb@imail.eecs.berkeley.edu)
Due Wednesday, Jan 31, 2007 @ 11:59pm
Last updated Sunday, Jan 28, 2007 @ 10:47am

Ah, Life. Mikey likes it. You can spin for a number to move around the board, getting a job, having children, and paying off student loans. You can even model it in a computer program! I think we'll stick with the latter, but in all its forms, Life is good. I know, I know... Now that you've read that, you're going to tell me that I need to "get a life!" Well, that's your job.

--David Eitan Poll, Spring 07 CS61c TA

A "glider" as visualized by GOL in this project.


Please read the Wikipedia article on Conway's Game of Life for this assignment's context and a full description of the problem/simulation.

Also, please read K&R: 2.9, 7.2, 7.4, and 7.5 to learn how to manipulate bits, print strings, and work with files.

Getting Starred
Copy the contents of ~cs61c/hw/02 to a suitable location in your home directory.

  $ mkdir ~/hw
  $ cp -r ~cs61c/hw/02/ ~/hw
This will copy in GOL.c, an example PBM file, and a few other files.

You will be implementing Conway's Game of Life in C from scratch. Your implementation will use the wraparound technique for dealing with board edges. Specifically, cells on any edge of the board have neighbors on the opposite edge. You may assume you will be given boards with no more than 64 cells in any direction and that they are well formed (means no error checking needed when parsing). However, it may be in your best interest to come up with a solution that theoretically works for any board size. Also, all board names used on your program will end in ".pbm".

Of course, everybody lives life in his/her own way. Therefore, your implementation will have to play the game using arbitrary rules for when cells are born and die.

Your program must support the following:

  Usage: GOL <file> <bornRule> <dieRule> <max generations>
    This program simulates Conway's Game of Life, a cellular automaton devised
    by British Mathematician John Horton Conway in 1970. The rules for this
    zero-player game are the standard rules as described in the Wikipedia article
    about this game: http://en.wikipedia.org/wiki/Conway%27s_game_of_life. The
    only difference is births and deaths are determined by the two strings of
    digits passed as arguments.

    For example, if 34 is passed as <bornRule>, a cell will be born if and
    only if it has 3 or 4 living neighbors. The rule works similarly for deaths.
    The standard rules would be represented as <bornRule> = 3 and <dieRule> =

    This program will take as input a plain PBM file of the format:

      P1 <columns> <rows>
      <bits for each row indicating a living cell (1) or dead cell (0)>

    and output one PBM file (with identical formatting to the above) for each
    generation of cells in the game until you reach max generations. The PBM
    produced will have a comment in the first line indicating the programmer's
    login and the generation number of the current file. These files will be
    named the same as the input, but with the generation number appended before
    the ".pbm". For example, if the input file is "spaceship.pbm", the files
    written will be named "spaceship0.pbm", "spaceship1.pbm", etc. Generation 
    0 is the configuration initially given to the program.

    PBM files can be easily viewed using the xv command or converted to another
    format using the pbmto* and ppmto* utilities. A plain ascii PBM file can be
    created by adding a header line "P1 <WIDTH> <HEIGHT> and followed by
    a grid of data (0 = dead = white, 1 = live = black). A call to man pbm can
    help answer questions about the format.

      <file> is the location of a .pbm file to be used as input to the
      program. This image represents generation 0 for the simulation.

      <bornRule> is the born rule as explained above

      <dieRule> is the die rule as explained above

      <max generations> is the maximum number of generations to generate

      unix% GOL diesFast.pbm 3 0145678 2

      diesFast.pbm contains the following:
      P1 4 4
      0 0 0 0
      0 0 1 0
      0 0 0 0
      0 0 0 0

      The files output will be:

      P1 4 4 ## Generation 0 of Conway's Game of Life by cs61c-tb
      0 0 0 0
      0 0 1 0
      0 0 0 0
      0 0 0 0

      P1 4 4 ## Generation 1 of Conway's Game of Life by cs61c-tb
      0 0 0 0
      0 0 0 0
      0 0 0 0
      0 0 0 0

      P1 4 4 ## Generation 2 of Conway's Game of Life by cs61c-tb
      0 0 0 0
      0 0 0 0
      0 0 0 0
      0 0 0 0

Please remember that your program stops after a number of generations. It also needs to print the usage string if not enough arguments are given to your program.

Assignment Correctness

In order for your assignment to be graded properly, it must follow these output guidelines:

Handling Error Cases
Your program must never segfault/bus error due to input into your program. However, you may assume the PBM files we will give are valid. If the input doesn't satisfy the constraints, or any other user error occurs, print the usage string as specified above.

Compiling HW2
Please compile GOL.c with the following command:

  % gcc -Wall -g -std=c99 -o GOL GOL.c

We are providing you with an Oracle for this assignment to help you check your solutions. This program represents the behavior your program should have. It will accept the standard arguments as described in the specification above. You can run the oracle by typing "GOL_oracle" from the command prompt.

Extra Help
David Poll will have extra office hours the night before the homework is due. They will be held Tue, Jan 30 from 6-8pm in 271 Soda.

If you have other questions, you are welcome to post them on the newsgroup. However, please do not post the code of your assignment.

Submit a single file GOL.c by creating a directory called hw2 with your file GOL.c in it. From within this directory run submit hw2. Be certain that your program accepts command line arguments for the file name. If you interactively prompt for these values rather than accepting command line args, your program will hang and fail the autograder.

If you choose to do the second Extra for Experts below, you may also submit GOLUnlimited.c for EPA points.

3D Visualization
We normally think of Conway's Game of Life as a 2-dimensional game. Let's add another dimension! We can plot the generation as the 3rd dimension, producing lively images like you see above. (I know, the puns are getting "cell"fish forgive me!). I've provided for you a script that will let you view a 3D rendering of your Game of Life genealogy! Note: This is an optional part of the assignment. To get the files you need for this feature, use the following command:

  cp ~cs61c/hw/02/* .
Once you've run your program to generate the many generations of GOL, run the following command in the same directory that contains the PBM files generated by your program:
  python 3dScript.py baseFileName.pbm
This will generate a file, graphed.m, that can be read by a Java applet loaded in a browser. Open visual.html in your favorite browser, and voila! Earlier generations are more blue, while later generations are more green.

Extra for Experts
This section is optional, but will impact your EPA and could be really fun!