Homework 2: C Basics - Cellular Automata

As part of HW2, you’re going to put together a cellular automata in C. We’ve made a Github classroom assignment with all the code you need; you can accept the assignment by following the link here.

What is a cellular automata?

A cellular automata starts with a row of cells. Each cell is either alive (‘1’) or dead (‘0’). In the following representation, a shaded (black) box represents a cell that is alive, and a white box represents a cell that is dead:

At discrete time steps, the automata “evolves”, producing a new generation, which we represent as a new row. We decide whether each cell in the next generation is alive or dead using a “rule”. In this homework, we’ll be using 32-bit rules.

Let’s say our rule is the 32-bit number 0xDEADBEEF, or 3735928559. In binary, that’s 0b1101_1110_1010_1101_1011_1110_1110_1111.

We can think of our rule as lookup table with 32 entries. If the entry we look at is a 1, the cell will be alive, and if the entry we look at is a 0, the cell will be dead.

How do we know which cell to look at? We look at the cells surrounding the corresponding cell in the previous generation–two to the left, and two to the right–to form a five-bit number.

Let’s say we have the example row above, and we’re trying to figure out whether the cell at index 4 will be alive or dead in the next generation.

Looking at the cells to the left and right, we get 1 0 to the left, 0 as the current value of the cell, and 1 1 to the right. If we combine these bits into a 5-bit number, we get 0b10011 in binary, which is 19 as an unsigned number.

Going back to the table we created from our rule, we see that index 19 has a ‘1’. This means that the cell at index 4 will be alive in the next generation. We repeat the process for every cell to get the values for the next row.

What do we do about the cells on the very right and left, which don’t necessarily have all of the necessary neighbors? We assume that all cells off the grid are “dead” when calculating the next generation

This may seem quite simple, but the images produced by cellular automata can be quite beautiful. A more in-depth explanation of cellular automata can be found here. Cellular automata (and Rule 30 in particular) are a favorite of Wolfram Alpha founder Stephen Wolfram; you can read his blog post about Rule 30 here. Rule 30 is for 8-bit rules; the equivalent rule for our 32-bit assignment is 66847740. When you finish this assignment, you can run your cellular automaton using rule 66847740, and it’ll produce the image like the one below:

Getting Started

You’ll have to fill in code in the file cell_auto.c in three different places: Part 1, Part 2, and Part 4. Part 1 and Part 2 are meant to be fairly quick and simple introductions to essential skills in C; the more involved part of this exercise is in Part 4.

Once you’ve accepted the Github classroom assignment, you can clone the repo using the following command:

git clone <your Github classroom repo URL>

You should also add the staff starter code repo as a remote. (The instructions below are for HTTPS, but you are welcome to use SSH if you have that set up). Check Piazza to see if there are any changes that you should pull.

git remote add starter https://github.com/61c-teach/fa19-hw2-starter.git

Part 1: Command Line Arguments

Every C program has one thing in common: the main() function, which generally has the following function header:

int main (int argc, char ** argv) {
    
    ...
    
}

argc is the number of command line arguments that were provided, and argv is an array of strings; each string is one of the provided arguments.

Your Task: For Part 1, your task is to make sure that the input the user provided to cell_auto.c is appropriate, and convert the provided arguments from strings into the required type(s). If input is not in the correct format, call the usage() function.

Part 2: printf()

An essential part of programming (and debugging!) in C is being able to properly print output to STDOUT. If you’d like an in-depth introduction to printf(), I’d recommend starting here.

The output of our cellular automata program is a PBM (Portable Bit Map) file. The first line of a PBM is always P1 <width> <height>, and you can add comments starting with the # hash symbol.

For example, the following is a valid PBM file:

P1 7 8 ## This is a smiley face
0 0 0 0 0 0 0
0 1 0 0 0 1 0
0 1 0 0 0 1 0
0 1 0 0 0 1 0
0 0 0 0 0 0 0
1 0 0 0 0 0 1
0 1 0 0 0 1 0
0 0 1 1 1 0 0

You can read about PPM, PBM, and the related PGM file type in this quick explainer. You’ll be using a very similar file format (.ppm) in Project 1, so it’s worth taking a bit of time to look into what this file type is now.

Your Task: For Part 2, your task is to add the line(s) of code that will print the header of your PBM file. See cell_auto.c for the specified format that the autograder will be looking for.

Part 3: Memory Management

In C, unlike many other high-level languages, the programmer manually controls dynamically allocated memory. This generally happens in three steps:

1. Allocating memory with a call to malloc(), calloc(), or realloc(), all of which return a pointer to the allocated memory
2. Checking to make sure the pointer returned is not NULL, and returning an error if that is the case
3. Calling free() to release the memory once finished with it

We’ve taken care of memory management for you in this homework; this will not be the case in future assignments. We recommend looking through each line of the provided code and making sure you know what it does.

Something that should be of special interest: when you use calloc() to allocate memory, the memory you are given is set so that every bit is a 0. Because you can count on this being the case, we recommend thinking about ways you can take advantage of this in Part 4.

Part 4: The Simulation!

Your Task: Given arguments rows and rule, print the initial generation followed by rows following generations, in the specified format, for a PBM file of width 2 * rows + 1 and height rows + 1.

The initial generation will begin with a single cell that’s alive. If you use 3 as your argument for rows, your first row will look like this:

You’re going to represent your rows with '1' representing alive and '0' representing dead, separated by spaces, meaning the row above would be represented by the following sequence:

0 0 0 1 0 0 0

If you use Rule 30 and 3 rows, the end result (what is printed to the terminal when you run ./cell_auto 30 3) will should like this:

P1 7 4 ## 3 rows of automata simulation (Rule 30)
0 0 0 1 0 0 0
0 1 1 1 0 0 0
1 0 0 0 0 0 0
1 0 0 0 0 0 0

The dimensions of your PBM file will be [7 x 4].

Make sure that there is no trailing whitespace at the end of your lines: 0 0 1 0 0 \n is NOT correct, you want to have 0 0 1 0 0\n. Every line (including the last) should end with a newline ('\n') character.

Testing Your Code

First, you’ll need to compile your code. You’ll want to compile your code using gcc, which is available on the hive machines, with the following command:

gcc -g -o cell_auto -std=c99 cell_auto.c

This will create an executable file called cell_auto.

You can run cell_auto as follows:

./cell_auto <rule> <rows>

We’ve included 3 tests for you, with reference files in .pbm format for you to compare your output to (test1_expected.pbm, test2_expected.pbm, and test3_expected.pbm). These are the parameters used to generate the test files:

You can view these .pbm files in any ordinary text editor, or in the terminal, using

cat testX_expected.pbm

where X is 1, 2, or 3.

Here’s how we recommend comparing your output to the expected output:

1. Run your version of cell_auto with the correct parameters, re-directing the output into a new .pbm file. For example, for Test 1 run ./cell_auto 2290659224 5 > my_test1.pbm.
2. Compare your output to the expected output using a vimdiff, e.g. for Test 1 run vimdiff test1_expected.pbm my_test1.pbm.

vimdiff will pull up the test1_expected.pbm on the left and my_test1.pbm on the right. Any rows that are different will be highlighted, and the specific parts of the line that are different will be highlighted in red, allowing you to pinpoint where your code went wrong.

If you’d like to create nice gifs of your automata to view, you can use the Linux utility ppmtogif. We’ve included a helper script, scale.sh, that will allow you to adjust the size of your gif. You can use both as follows:

./cell_auto 30 3 | ./scale.sh 40 | ppmtogif > rule30_3rows.gif

You may get the following message:

ppmtogif: maxval is not 255 - automatically rescaling colors

It’s totally normal, and you’ll find the gif you’ve created in the directory. If you find a rule that particularly appeals to your artistic sensibilities, please share in the HW 2 - Cellular Automata Piazza thread–we’d love to see it!

Advice: Test Automation

If you find yourself running the same terminal commands over and over again, it could be useful to write yourself a shell script.

Make a new file with the extension .sh, and put the line #!/bin/bash at the top of the file. Below this, you can put all of the commands you’d like to run as part of the script. For example, if I create a shell script called hello.sh as follows:

#!/bin/bash

echo "Hello!"
echo "World!"

when I run ./hello.sh, I’ll see

Hello!
World!

printed in the terminal.

Submission

Final submission for this homework will be on Gradescope, to the assignment titled “Homework 2 - Cellular Automata”. You will upload one file, cell_auto.c. The autograder on Gradescope will show you which tests you’ve passed and failed, and your final score. There are no hidden tests; this final score is your score on the assignment.