2008Su CS61C Homework 2 : Life 1D
TA: Richard Guo

Clarifications to spec will be posted in red.

## The Simulation Process

For hw2, you will be implementing an elementary cellular automaton, also known as Life 1D. A cellular automaton is composed of a space of cells, which can be dead or alive, and a rule describing the transition from one generation of cells to the next. In Life 1D, the cells live in a 1-dimensional array.

For example, here is an array of 7 cells. The value 7 was chosen arbitrarily for this example.

Cells are shaded if they are alive, otherwise they are dead. Therefore, only the center cell in this example is alive (Your initial row will look similar no matter how long it is; only the center cell starts out alive).

We produce the next generation of cells using a rule that ranges from 0-255. Note that such a number can be represented with 8 bits. For our example, we will consider the rule 30, which is equal to 0b00011110. Each bit is indexed by its "place" in the number.
 Place (decimal) Place (binary) Alive/Dead 7 0b111 0 6 0b110 0 5 0b101 0 4 0b100 1 3 0b011 1 2 0b010 1 1 0b001 1 0 0b000 0

Here is the same table graphically. Note that the 3 cells above represent its place in binary and the one below represents whether the corresponding bit is on or off in the rule number.

We have to check each cell in the array to see whether it will be alive or dead in the next generation. We use the alive/deadness of that cell along with the alive/deadness of its left and right neighbor as a 3-bit number, which we use to index the rule.

For example, starting with the same 7 cell array, we first look at the leftmost cell.

It's dead, as well as its two neighbors (for our purposes, we will assume all cells off the world are dead). This corresponds to 0b000, which for rule 30 is 0 (i.e. off, dead). This means that in the corresponding cell for the array representing the next generation, it will be dead.

Repeat the process for the second cell from the left. This one is also 0b000, so in the next generation it will be dead. What about the third cell?

We can see that this cell is dead as well as its left neighbor, but its right neighbor is alive. This corresponds to 0b001, which for rule 30 is 1 (i.e. on, alive). Therefore, the third cell of the next generation will be alive.

The fourth cell corresponds to 0b010, which is alive. We can repeat this process for the remaining cells to produce the following next generation array.

By repeatedly applying this generation process and putting each new generation below the previous one, we can produce the following graphic.

You will be writing a C program to do this for any rule and number of rows.

For context and a full description of this problem, read Wolfram's Elementary Cellular Automata . You should also refer to this site for example pictures of all 256 rules. Refer to this site instead for "cs61c solution" outputs.

## 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 takes 2 command line arguments, `rows` and `rule`. The rule is valid if it is a value between 0-255. The `rows` value determines the size of the picture, which will be (`rows`+1) high and (2*`rows`+1) wide. The first row consists of all dead cells except the center cell, which is alive. We use `rows`+1 because `rows` really refers to the number of generated rows, which doesn't include the aforementioned initial row. 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 display 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).  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
```    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
```    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
```    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 will 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
```

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

Look at this gallery for "cs61c solution" outputs.

## Output Format

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!