2007Sp CS61C Homework 2: Conway's Game of Life

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.

Updates

Jan 28 @ 10:47am -- It is possible for both the born and die rules to share numbers. (e.g. bornRule=034 dieRule=1487). The way to handle situation is to apply the bornRule only if a cell is dead and the dieRule only if it is alive in each generation. In other words, for each generation, a given cell can only have a bornRule or a dieRule applied to it and not both.
The oracle has been updated to address the above problem as well as a few others. If you have finished testing, please retest again to verify your submission.
Jan 25 @ 12:23am -- corrected PBM file header description in usage string. It is "P1 <cols> <rows>".

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

Assignment
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> =
    0145678.

    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.

    Arguments:
      <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

    Examples:
      unix% GOL diesFast.pbm 3 0145678 2
      unix%

      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:

      diesFast0.pbm:
      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

      diesFast1.pbm:
      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

      diesFast2.pbm:
      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:

The first line in each of the output files MUST follow this format:
```
  P1 [a] [b] ## Generation [c] of Conway's Game of Life by [d]
```
where [a] is the number of cols, [b] is the number of rows, [c] is the generation number, and [d] is your login.
Do not have any extraneous whitespace characters at the end of the row. This means your rows should end in "0\n" or "1\n" and NOT "0 \n" or "1 \n".
All rows end with a newline character. After your program exits, the UNIX prompt should start on a new line and not on the same line.
You must have spaces in between your columns (like in the examples above).
You must copy the usage string verbatium (this means the Usage, Arguments, and Examples). It should be printed if no arguments are given for GOL. Note, we do provide the text of the usage string in usage_string.txt.

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

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

Submission
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!

This assignment will be used as the basis for a performance competition at the end of the semester. We will give huge boards and patterns and have you produce many generations, and see how quickly your implementation can handle them. See how efficiently you can make your code run! You'll learn techniques throughout the semester that might help you with this.
There are lots of ways to handle edges in GOL, but they all have their limitations. For brave souls, try making an infinite board that grows as necessary. If you write this, please provide that code in GOLUnlimited.c for submission and leave the implementation that matches the spec in GOL.c.