2006Fa CS61C Homework 2 : Life 1D
TA: David Poll


Life 1D : Rule 30

Reading

You should read Wolfram's excellent Elementary Cellular Automata for context and a full description of the problem/simulation.

Hint

Check your understanding of how rules work, it's very important and somewhat confusing in the reading. Here's a brief overview:
There are rules from 0 to 255, which is the range of an 8-bit number (28 - 1 = 255). So, another way of interpreting a rule such as, say, 30, would be to write it as: 00011110. Observe that if we label the bits from 0 to 7, bits 1, 2, 3, and 4 are on.

We can represent the numbers 0 through 7 as 3-bit strings (000, 001, ..., 111). This combination of 3 bits tells us what patterns in one generation of Life1D will spawn a new bit. If the rule's 3rd bit is on, 011 (dead, alive, alive) will spawn a new cell. Similarly, if the rule's 7th bit is off, 111 will not spawn a new cell in the next generation.

As a result, we end up with the following generation key from rule 30 (from the Wolfram site):

This information should help you interpret rules in Life1D, allowing you to determine what each generation will look like.

Problem

You are to implement a one-dimensional variant of Conway's Game of Life, heretofore called "Life 1D". Specifically, you will write the following program in C (from scratch) which supports the following:
Usage: Life1D <rows> <rule>
    This program simulates 1D Life: the simplest class of one-dimensional
    cellular automata in a <ROWS=rows+1> x <COLS=2*rows+1> grid starting
    with a single live cell in the middle of the top row using rule <rule>.
    These 1D rules are defined in Wolfram's Elementary Cellular Automata:
    http://mathworld.wolfram.com/ElementaryCellularAutomaton.html
    This program will print to stdout data in plain PBM file format.
    This output can be easily viewed using the xv command or converted to a
    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 about the format.
    Add a comment on the first line with a brief description of the image.
  Arguments:
    <rows> is a positive integer specifying the number of rows to generate
    (not counting the first "seed row" which is all dead except for a central
    live cell). The columns are computed automatically -- enough so that
    the rule, if it were to grow in the normal triangular pattern, would
    just perfectly reach the edge. Off the board is considerered "dead".
    <rule> is a number from 0-255 specifying the rule to use
  Examples:
    See Rule 60 : http://mathworld.wolfram.com/Rule60.html
    unix% Life1D 3 60
    P1 7 4 ## 3 rows of Life1D (Rule 60) by Yourfirstname Yourlastname
    0 0 0 1 0 0 0
    0 0 0 1 1 0 0
    0 0 0 1 0 1 0
    0 0 0 1 1 1 1

    See Rule 90 : http://mathworld.wolfram.com/Rule90.html
    unix% Life1D 5 90
    P1 11 6 ## 5 rows of Life1D (Rule 90) by Yourfirstname Yourlastname
    0 0 0 0 0 1 0 0 0 0 0
    0 0 0 0 1 0 1 0 0 0 0
    0 0 0 1 0 0 0 1 0 0 0
    0 0 1 0 1 0 1 0 1 0 0
    0 1 0 0 0 0 0 0 0 1 0
    1 0 1 0 0 0 0 0 1 0 1

    See Rule 250 : http://mathworld.wolfram.com/Rule250.html
    unix% Life1D 4 250
    P1 9 5 ## 4 rows of Life1D (Rule 250) by Yourfirstname Yourlastname
    0 0 0 0 1 0 0 0 0
    0 0 0 1 0 1 0 0 0
    0 0 1 0 1 0 1 0 0
    0 1 0 1 0 1 0 1 0
    1 0 1 0 1 0 1 0 1

Assignment Correctness

The assumption that all cells off the grid are always considered "dead" causes will cause discrepancies in your results for certain rules when comparing your results to what you see at Mathworld. For example, your solution may generate this for rule 139:
  $ Life1D 17 139
  P1 35 18 ## 17 rows of Life1D (Rule 139) by cs61c
  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0
  1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1
  1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0
  1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0
  1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1
  1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 0
  1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 0 0
  1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 0 0 1
  1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 0 0 1 0
  1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 0 0 1 0 0
  1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 0 0 1 0 0 1
  1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 0 0 1 0 0 1 0
  1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0
  1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1
  1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0
However, the images at Mathworld suggest that it should be like this:
  $ Life1D 17 139
  P1 35 18 ## 17 rows of Life1D (Rule 139) by Mathworld
  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Can you spot the difference? The cs61c solution has several diagonals of zeros while the Mathworld solution does not. This is due to Mathworld assuming the grid is an infinite grid (versus a finite grid in this assignment). Therefore, for the sake of simplicity, the cs61c solution is considered the "correct" solution for this assignment. This means, you do not need to write additional C code to produce the Wolfram solution. For those of you who want to have a more "correct" solution, see the
Extra for Experts Section.

Output Format

In order for your assignment to be graded properly, it must follow these output guidelines:
  1. The first line printed out in your program MUST follow this format
      P1 [a] [b] ## [c] rows of Life1D (Rule [d]) by [e]
    where [a] is the number of displayed cols, [b] is the number of displayed rows, [c] is the <row> parameter. [d] is the <rule> parameter, [e] is your name

  2. Do not have any extraneous whitespace characters at the end of the row. Meaning, each row print out ends with "0\n" or "1\n", not "0 \n" or "1 \n". Otherwise, you will most likely fail all the the autograder tests because of the extra whitespace at the end of the line.

  3. All rows end with a newline character. Meaning, after your program exits, the UNIX prompt starts on a new line and not on the same line as your last row.

  4. You must have spaces in between your columns (just like you see in the examples above) when you print out a row. Meaning, this is invalid (no spaces between columns):
       000010000
       000010100
       000010010
    
    and this is valid:
       0 0 0 0 1 0 0 0 0
       0 0 0 0 1 0 1 0 0
       0 0 0 0 1 0 0 1 0
    
  5. You need to use the usage string above. It is reprinted here without the HTML formatting:
      Usage: Life1D <rows> <rule>
          This program simulates 1D Life: the simplest class of one-dimensional
          cellular automata in a <ROWS=rows+1> x <COLS=2*rows+1> grid starting
          with a single live cell in the middle of the top row using rule <rule>
          These 1D rules are defined in Wolfram's Elementary Cellular Automata:
          http://mathworld.wolfram.com/ElementaryCellularAutomaton.html
          This program will print to stdout data in plain PBM file format.
          This output can be easily viewed using the xv command or converted to a
          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 = black, 1 = live = white).
          A call to "man pbm" can help answer questions about about the format.
          Add a comment on the first line with a brief description of the image.
        Arguments:
          <rows> is a positive integer specifying the number of rows to generate
          (not counting the first "seed row" which is all dead except for a central
          live cell). The columns are computed automatically -- enough so that
          the rule, if it were to grow in the normal triangular pattern, would
          just perfectly reach the edge. Off the board is considerered "dead".
          <rule> is a number from 0-255 specifying the rule to use.
    

Handling Error Cases

If the input doesn't satisful the constraints (i.e., rows or rule aren't valid integers in the specified range), you should print the Usage string above (just copy it into your code).

Test your code!

A great way to test your code is to run it through all the rules with 15 rows and check it against the catalogue of images on the bottom of the
Elementary Cellular Automata page. You can generate a gif image by piping the output into ppmtogif and redirecting the output to a file. E.g.,
unix% Life1D 3 60 | ppmtogif > Life1D_3_60.gif
Here are the gifs resulting from the examples above:

Life1D 3 60

Life1D 5 90

Life1D 4 250

Submission

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

Extra for Experts

If you want a "Wolfram" correct solution, add a new optional parameter named "Wolfram" to generate the correct result. For example:
  % Life1D 17 139
  ;; would produce the cs61c solution
  % Life1D 17 139 Wolfram
  ;; would produce the image that matches the website
If you really enjoy this project, you might want to consider implementing a
Totalistic Cellular Automaton, otherwise known as "Life1D in grayscale/color". Enjoy!