The goal of this lab is to gain more comfort with C++ functions and arrays by implementing simple one-dimensional cellular automata.

To get started, run update35 from a computer science lab computer. The program update35 will create a cs35/labs/01 directory in your CS home directory, and the program handin35 will subsequently submit files from that directory.

Cellular automata (singular: automaton) are an abstract model of computation where a program's state consists of a grid of cells (with each cell storing a single value) and the program itself is a set of rules that define how the cell values change over time. To run the program, an automaton generates the next state of the program from the current state by examining each cell and its neighbors, finding the rule that matches that cell and its neighbors' states, and setting the new value for that cell using the rule that matched.

In this assignment we will consider just simple one-dimensional automata where the program state is a line of cells, with each cell containing a 0 or 1. For a 1-dimensional automaton, the program is defined by a set of eight rules, one rule for each possible combination of states of a cell and its adjacent neighboring cells.

For instance, consider the following set of rules (from the current Cellular Automaton Wikipedia page):

a cell's old value and its neighbors:	000	001	010	011	100	101	110	111
new cell value:	0	1	1	1	0	1	1	0

When a cell and its neighbors match a pattern in the first row of the table, the automaton generates the next value of the (center) cell as the value in the second row.

At any point in time, the state of the program is defined by the values of all the program's cells. To get from one state to the next state, a cellular automaton applies the program rules to all cells (and their neighbors) to determine the next state for all cells. For instance, suppose the current state is 00001 and the program's rules are as the table above:

By applying the program rules to each cell, the next state is computed to be 00011. The first and last cells of an input do not change, because they each have just one neighbor and therefore do not match any pattern.

A program can is executed by applying the program's rules repeatedly. For instance, given the rules above and an initial state of 00001, we would get the following execution:

generation 0:	00001
generation 1:	00011
generation 2:	00111
generation 3:	01101
generation 4:	01111
generation 5:	01001
generation 6:	01011
generation 7:	01111
...

and so on. From here, the states at generation 5 through 7 would repeat forever.

Your program should read (as input from the user) the number of cells in an automaton, the number of generations to compute, the pattern-matching rules, and the automaton's initial state. It should then execute the automaton's program by computing the subsequent states for the automaton, printing each state. For this assignment you may assume that the user enters valid input and that the the automaton will never contain more than 1000 cells.

Consider the following example which mimics the example above. (The user typed the blue text.)

$ ./life
How many cells are in your automaton?  Enter an integer: 5
How many generations do you want to compute?  Enter an integer: 7
Enter the 8 automaton patterns and the value that pattern generates, 
separated by whitespace.
000 0
001 1
010 1
011 1
100 0
101 1
110 1
111 0
Enter the initial state of the automaton cells.
00001
00001
00011
00111
01101
01111
01001
01011
01111

• Your program should prompt the user for the number of cells in the automaton, the number of generations to compute, the rules for how the automaton generates state, and the initial state of the automaton.
• Do not start programming until you are sure how cellular automata work.
• Because you only need to support automata with at most 1000 cells, represent the automaton state with a statically-allocated array of size 1000. It's OK if you don't use all of the array for each automaton.
• Develop and test your program incrementally. For reference, the sample solution included a main function and six helper functions, each of which were tested independently of the other functions in the program. Develop and test your functions in an order that allows you to continuously test your new code as you work.
• When computing the next state of the cellular automaton, compute the new state into a separate array and then copy that state back to the original array when you finish computing it. This prevents you from corrupting the array state, which might happen if you compute new cell values from a mixture of old and new values.
• Lazy typists make good programmers: as you write and test your code, develop habits that allow you to test your work quickly while typing as little as possible.

  One trick is to avoid typing your program's sample input each time you test your program. Instead, save your sample input as a separate file (e.g., test.in) and redirect that file as input to your program using the < operator in your terminal, e.g., ./life < test.in. We've provided three sample input files and their corresponding output to help you test your program, and you should develop your own test cases, too. To correctly use our sample input, you need to read your inputs in the same order as our sample solution.

• With 1s and 0s the patterns can be hard to see. You can change your output format to print *s and blank spaces (for 0) if you want the patterns to be easier to read. (Keep the input format the same, though, with 1s and 0s.)

Once you are satisfied with your program, hand it in by typing handin35 at the unix prompt.

You may run handin35 as many times as you like, and only the most recent submission will be recorded. This is useful if you realize after handing in some programs that you'd like to make a few more changes to them.

Pretty patterns! Higher dimensions! Life!? Cellular automata can generate many interesting and repeating patterns, especially when you allow automata with higher dimensions. In 1-dimension each cell has only 2 neighbors which allows for 2^(2^3), or 256, distinct automata programs. In 2-dimensions each cell has 8 neighbors and there are 2^(2^9), or 2^512, distinct programs -- more programs than the number of atoms in the universe! For those of you who took CS21b, Conway's Game of Life is just one specific 2-dimensional automaton program out of those 2^(512).

While experimenting with your program, what awesome patterns can you find? Can you, for instance, find a pattern that repeats every 11 generations? Can you find a pattern that spawns a so-called glider, a moving repeated pattern that moves to the right or left with each generation? For examples of the kinds of patterns that can be generated use the life modes on the xlock program:

$ xlock -nolock -mode life1d
$ xlock -nolock -mode life

A common simplification is to define generic state transition rules based on the number of so-called live neighbors for each cell, rather than the exact neighbor pattern, just as in Conway's Game of Life.

You will earn some pidling extra credit if you find cool patterns. You can submit a new pattern by leaving a new pattern-name.in file in your handin directory.

You can earn slightly-less-pidling extra credit if you implement a second program, life2d that implements 2-dimensional cellular automata. Note, though, that this is moderately more difficult than implementing 1-dimensional automata, and also moderately more difficult in C++ than in Python. If you attempt this, I recommend that you define the state transition rules (a la. Conway's Game of Life) rather than require the user to input 512 pattern-matching rules.