# Lab 13: Multidimensional Vectors

## Introduction

We have seen that the `vector` type allows us to construct objects in which we can conveniently store a sequence of values. For example, the statement:

`vector<double> aVector(8);`
defines the object `aVector` as a container capable of storing eight `double` objects.

We usually visualize a `vector` as a linear sequence of values that has one dimension: just one index is sufficient to manipulate the elements of a one dimensional vector. Consequently, a `vector` has just a length or size.

There are, however, many objects that are more naturally visualized as having two dimensions, such as a tic-tac-toe game, which is organized by rows and columns:

One way to build a data structure of such an object is by defining a `vector` that stores other `vector`s:

`vector< vector<char> > ticTacToeGame;`
Now two indices are needed to specify an element of a two-dimensional `vector`: the first specifies the particular row being accessed, and the second specifies the particular column within that row.

For example, we could access the `X` in the upper left corner of `ticTacToeGame` with the expression:

`ticTacToeGame[0][0]`
We could access the `X` in the lower left corner with the expression:
`ticTacToeGame[2][0]`
The `O` in the upper right corner is accessed with the expression:
`ticTacToeGame[0][2]`
The `X` in the lower right corner is accessed with the expression:
`ticTacToeGame[2][2]`

In this lab's exercise, we will use this idea to build a class that allows us to play an interesting game known as the game of life.

## The Game of Life

The game of life was invented by mathematician John Conway as a simple model representing a society of organisms. The basic premise is to create a rectangular grid of cells. Each cell in the grid (except along the border) has eight neighboring cells:

Each cell may have an organism in it, that we'll represent for now as an asterisk, `*`.

The game consists of a series of generations. Each generation (except the first) is determined by the previous generation. (You have to provide the game with the initial generation; that's the trick to the game!) To determine the next generation, we follow these rules:

1. If a cell has exactly three neighboring organisms, then an organism is born in that cell.
2. If a cell has fewer than two neighboring organisms, then an organism in that cell dies of loneliness.
3. If a cell has more than three neighboring organisms, then an organism in that cell dies of overcrowding.

These three simple rules are sufficient to observe some fascinating behaviors. For example, suppose that we begin with this configuration of three organisms:

Then applying the rules, we can generate the next generation:

• Cells `[0][0]`, `[1][0]`, `[2][0]`, `[3][0]`, `[4][0]`, `[0][4]`, `[1][4]`, `[2][4]`, `[3][4]`, and `[4][4]` have no neighboring organisms, and so they remain empty.
• Cells `[0][1]`, `[1][1]`, `[0][2]`, `[0][3]`, `[1][3]`, `[3][1]`, `[3][3]`, `[4][1]`, `[4][2]`, and `[4][3]` have one neighboring organism, and so they remain empty.
• Cells `[1][2]`, and `[3][2]` have one neighboring organism, and so the organisms in them die of loneliness.
• Cells `[2][1]`, and `[2][3]` have three neighboring organisms, and so an organism is born in each of them.
• Cell `[2][2]` has two neighbors, and so its organism remains unchanged.

Consequently, the second generation is

To get the third generation, we re-apply the same rules to the second generation. Organisms are born in cells `[1][2]` and `[3][2]`, while the organisms in cells `[2][1]` and `[2][3]` die, returning us to the original configuration!

This particular configuration continues to oscillate back and forth from generation to generation. It can be thought of as representing a society of organisms that, while changing from generation to generation, remains stable if it is not disturbed by outside influences. Other configurations grow larger and larger with each generation until the entire grid is nearly filled---a population boom. Others grow smaller and smaller until all organisms are dead, modeling societies that lead to the extinction of their organisms. We will see examples of each of these at the end of this exercise.

## Files

Directory: `lab13`

Create the specified directory, and copy the files above into the new directory. Only `gcc` users need a makefile; all others should create a project and add all of the `.cpp` files to it.

Add your name, date, and purpose to the opening documentation of the code and documentation files; if you're modifying and adding to the code written by someone else, add your data as part of the file's modification history.

## Looking at the Files

The files `LifeGame.h`, `LifeGame.cpp` and `LifeGame.doc` provide the skeleton for a `LifeGame` class, a class to represent and perform the appropriate operations on a game of life. The file `test.life` contains the initial configuration for the simple three organism oscillating pattern that you can use to test what you write. The file `lifedriver.cpp` contains a complete driver that constructs a `LifeGame` object with an initial configuration from a file, and then it displays the subsequent generations as controlled by the user. The calls to methods of class `LifeGame` are commented out at present, but we will uncomment these during the course of this exercise. Take a few moments to study `lifedriver.cpp` until you understand what it is doing and why.

## Design

This lab's exercise is to complete the `LifeGame` class. In addition to defining the methods for the class, this will involve implementing the following operations for class `LifeGame`:

• `LifeGame` will implement a constructor that reads an initial configuration from a file.
• `LifeGame` will provide two accessor methods, `getRows()` and `getColumns()`, to report on the dimensions of the life-game grid.
• `LifeGame` will provide a `nextGeneration()` method to generate the next generation of the game.
• `LifeGame` will provide `print()` method to print the current generation to an `ostream`. The output operator `<<` will be overloaded for a `LifeGame` object which will use this `print()` method.

We have provided prototypes and function stubs in `LifeGame.h` and `LifeGame.cpp` for each of these functions. This exercise will consist of completing class `LifeGame` and its methods.

## Implementation

Once we have the operations identified, we can begin the actual construction of the class. Begin editing the file `LifeGame.h`, where you should find a skeleton for class `LifeGame`.

### Instance Variables

Each cell in a game of life may or may not have a living organism within it, and this can (and hopefully will) change over time. There are a variety of ways to represent such an organism: a `char`, a `bool`, an `int`, etc.

Let's think about what operations we want to do these organisms. In the pictures above we represented organisms as an asterisk, and this works quite well displayed on a screen or in this lab exercise. However, the most important operation of a `LifeGame` object is to generate a new generation. Look at the rules for generating a new generation. All of the rules involve counting neighboring organisms. Sure, we can count the number of times a certain `char` (like an asterisk), `string`, or `bool` appears in the neighboring cells, but the most natural counting object in C++ is an `int`. So, we will represent a living organism with the integer 1, and we will represent a dead or missing organism with the integer 0. We won't even have to do any comparisons: just add up the values in the neighboring cells!

Since a game of life involves a grid of cells, we need a two-dimensional structure of cells. As suggested at the beginning of this exercise, we can implement this two-dimensional structure using a `vector` of `vector`s. Keep in mind that we'll still think and use it like a two-dimensional structure, but underneath it all, we'll have a `vector` of `vector`s.

First we'll declare a new datatype named `Row` to be a one-dimensional `vector` of integers; as the name suggests, this will represent one row of the grid. Then we can create a `vector` of `Row`s to represent the entire grid.

So let's first create this new datatype `Row` using C++'s `typedef` mechanism. Add the following statement to the private section of class `LifeGame`:

`typedef vector<int> Row;`
The keyword `typedef` declares `Row` as an alternative name for the type `vector<int>`---essentially a new datatype.

The general form of the `typedef` mechanism is thus:

`typedef `Type` `Identifier`;`
The effect of such a statement is to declare `Identifier` as a synonym for the type `Type`.

Once the identifier `Row` is declared as a synonym for `vector<int>`, we can then define a two-dimensional grid of cells as a `vector` of `Row` objects. Add the following statement to the private section of class `LifeGame`, following the `typedef` statement:

`vector<Row> myGrid;`

Our `LifeGame` class now has a instance variable named `myGrid` that is, technically, a `vector` of `vector`s of `int`s. However, we'll think of `myGrid` as just simply a two-dimensional `vector` of `int`s.

### The Constructor

In order to define and initialize a `LifeGame` object we need at least one constructor. The constructor should somehow be able to initialize the game with some initial generation. To make things a little easier, we'll put the initial generations into files. (Check out the `.life` files.) So our constructor will need access to a file to initialize the game.

Our program `lifedriver.cpp` begins by reading the name of the file from the user, and then it passes the name to the `LifeGame` constructor function which reads the contents of the file and uses them to initialize the `myGrid` instance variable.

For simplicity, we will assume that the first line of the file contains two integers, the number of rows and the number of columns in the grid of cells. The remainder of the file will then be a grid of starting values for the cells. For example, our `test.life` input file provides the starting configuration for the three organism oscillating pattern:

```5 5
0 0 0 0 0
0 0 1 0 0
0 0 1 0 0
0 0 1 0 0
0 0 0 0 0```
In this five-by-five grid (determined by the two `5`s at the beginning of the file), each `1` represents a cell containing an organism, and each 0 represents a cell without an organism. Any whitespace can be used to separate organisms; we've used spaces and newlines in this file so that it's a little easier for humans to read and write.

We can specify the behavior of this operation as follows:

Specification:
receive: `fileName`, a `string`.
precondition: `fileName` contains the name of an input file, the first line of that file specifies the rows and columns, and the remainder of the file is a configuration for a game of life.
postcondition: `myGrid` has been initialized to the configuration given in the input file.

This turns out to be a non-trivial function, so open the implementation file, and find the stub for the `LifeGame` constructor. Using object-centered design, we can derive the following algorithm for this function:

1. Receive `fileName`.
2. Open `inStream`, an `ifstream` to `fileName`, and verify that it opened successfully.
3. Read `rows` and `columns` from `inStream`.
4. For each index `r` in the range 0..`rows`-1:
1. Declare `aRow`, an empty Row.
2. For each index `c` in the range 0..`columns`-1:
1. Read `value` from `inStream`.
2. Append `value` to `aRow`.
End loop.
3. Append `aRow` to `myGrid`.
End loop.
5. Close `inStream`.

The first few steps should be quite familiar to you now (up to the nested loops), so write those first.

The two nested `for` loops build `myGrid` as a `rows`-by-`columns` `vector` of `vector`s of `int`s. The loops themselves aren't tricky. You've been writing loops for a while now, so write those `for` loops next. Keep in mind that the algorithm talks about ranges like "0..`last`-1"; this is an inclusive range, including both 0 and `last`-1. Typically, when working with `vector`s in C++, you start at index 0 and continue the loop while the loop index is less than `last`. For example:

`for (int i = 0; i < `last`; i++) ...`
You can write these loops with different bounds, but it's not recommended. This is the pattern used by nearly all C and C++ programmers.

Now let's tackle the other steps. The nested loops are used to initialize the two-dimensional `myGrid`. Since `myGrid` is actually a `vector` of `vector`s, these loops read in one row of `myGrid` with the inner loop, and then the outer loop adds the current row to the end of `myGrid` itself. We first declare an empty `Row`:

`Row aRow;`
Remember that `Row` is a `vector<int>`, so we're really asking for an empty `vector` of `int`s as if we had written this:
`vector<int> aRow;`

Inside the inner loop, we fill `aRow` with values from the file. Reading in the value is old hat. Adding the value to the end of `aRow` can be done with `push_back()`:

```inStream >> value;
aRow.push_back(value);```
Note that you'll have to declare `value` somewhere in the constructor.

Once `aRow` is a complete `Row` (i.e., we've left the inner loop), we then use `push_back()` to append `aRow` to `myGrid`:

`myGrid.push_back(aRow);`

Complete the stub for the `LifeGame` constructor. Check the syntax of what you have written by uncommenting the declaration of `theGame` in `lifedriver.cpp` and then compiling the code. Continue when your constructor compiles correctly.

### The `getRows()` Accessor

How many rows are in the grid? Any question like this is really an operation for the class, which means that it's a method of the class. Since it's relatively simple, we consider it an accessor. The specification for this accessor would be this:

Specification:
return: the number of rows in my configuration.

Even though we do not have instance variables that store the number of rows and columns in our configuration, defining an accessor to retrieve this information is fairly simple, using the `size()` function of the `vector` class. That is, since `myGrid` is a `vector` of `Row`s, the `size()` of `myGrid` is the number of rows in the configuration.

Our algorithm is thus as follows:

1. Return the size() of myGrid.

Since this is such a simple algorithm, we define it inline in the header file. Uncomment the `getRows()` stub in the header file, and complete the definition. Compile everything, and fix any syntax problems. When it is correct, copy-and-paste a copy into `LifeGame.doc` and continue.

### The `getColumns()` Accessor

You might expect that if knowing the number of rows is a good idea, then knowing the number of columns is also a good idea. It is.

Specification:
return: the number of columns in my configuration.

Solving this problem is again fairly simple using the `size()` function, but is slightly more tricky than our `getRows()` accessor. Again, `myGrid` is a `vector` of `Row`s. The number of columns in our configuration is the `size()` of a `Row` of `myGrid`. Since we've assumed that our grid is rectangular, the `size()` of any `Row` in `myGrid` will do.

Of course, the row index must be valid, so row `myGrid[0]` seems best. Unless there are no rows at all. Then we can assume that there are no columns. So we end up with this algorithm:

1. If getRows() > 0,
Return the size() of myGrid[0].
Else
Return 0.

Some compilers might find this to complicated to make it inline, so you can find it in the implementation file. Uncomment the stub, and complete the definition. Compile and fix any syntax problems.

### The `print()` Method

There's already an overloaded definition of `operator<<` in the header file, and this definition calls the `print()` method of class `LifeGame`. However, we don't have a definition for `print()` yet.

In the driver, uncomment the line that displays the value of `theGame`, and compile your code. You should get a linker error which complains that `print()` cannot be found.

Let's define the `print()` method and take care of this error. Using object-centered design, we can specify the behavior of this method as follows:

Specification:
receive: `out`, an `ostream`.
output: my current configuration.
passback: `out`, containing my configuration.

Completing our design, we can derive the following algorithm that uses nested `for` loops, an inner loop to output the values in each row and an outer loop to output the rows:

1. Receive `out`, an `ostream`.
2. For each index `r` in the range 0..getRows()-1:
1. For each index `c` in the range 0..getColumns()-1:
If `myGrid[r][c]` is 1:
Display "* ".
Otherwise
Display " ".
End if.
End loop.
2. Display a newline.
End loop.

Do you suppose it's any coincidence that whenever we work through our two-dimensional `vector` we end up with two loops, one nested in the other?

This algorithm scans cell-by-cell through `myGrid`, displaying two spaces for those cells containing 0 (i.e., nothing living) and displaying an asterisk and a space for each cell containing 1 (i.e., a living organism). This makes for more readable output than a display of ones and zeros.

Since this algorithm is fairly complicated, define this method in the implementation file. Uncomment the stub, and complete the definition. To test your code, uncomment the statement in the driver that displays `theGame`. Compile and run your code. Use `test.life` as the configuration-input file. If all is well, you will see the starting configuration of our simple five-by-five oscillating configuration. Move on when this is working properly.

### Generating The Next Generation

The method `nextGeneration()` is the workhorse of the class since it must encode the rules of the game. We can specify what it does as follows:

Specification:
postcondition: For each cell `c` in `myGrid`:
• If `c` had exactly three neighboring cells containing 1s, then `c` contains a 1.
• Otherwise, if `c` had less than two neighbors containing 1s, or if `c` had more than three neighbors containins 1s, then `c` contains a 0.

This postcondition is really a rephrasing of the rules of the game of life.

In order to process all of the cells, we will need two nested `for` loops (again!) to process the rows and columns of `myGrid`. Within the inner loop, we can count the number of neighbors for the current cell, and set its value appropriately as required to satisfy the postcondition.

We do, however, have to worry about two problems. First, the next generation is determined by the current generation. We cannot overwrite the current generation with the next one since the current generation is needed to determine the next. Consequently, we begin by making a copy of `myGrid` to remember the current generation, and then we use this copy to calculate the neighbors.

The second problem is that cells at the edges of the grid do not have the required eight neighbors. We'll make things easy for us by excluding them from consideration.

We thus end up with the following (incomplete) algorithm:

1. Define `tempGrid` = `myGrid`.
2. For each index `r` in the range 1..getRows()-2:
1. For each index `c` in the range 1..getColumns()-2:
1. `northNeighbors` = `tempGrid[r-1][c-1]` + `tempGrid[r-1][c]` + `tempGrid[r-1][c+1]`
2. `sideNeighbors` = ???
3. `southNeighbors` = ???
4. ```neighbors = northNeighbors + sideNeighbors + southNeighbors```
5. If `neighbors` is 3:
Set `myGrid[r][c]` to 1.
Else if `neighbors` is less-than 2 or `neighbors` is greater-than 3:
Set `myGrid[r][c]` to 0.
End if.
End loop.
End loop.

Since each cell is an integer, 0 representing an empty cell and 1 representing an organism, we can simply add the values in the surrounding cells to compute the number of neighbors.

The algorithm, though, leaves two of the computations unfinished for you to complete. Use the `northNeighbors` computation and the picture of a cell at the beginning of this exercise to finish the other computations:

Question #13.1: Come up with computations for `sideNeighbors` and `southNeighbors`.

The `sideNeighbors` computation should look at only the neighbors directly west and east of the current cell. Do not include the current cell.

Using this algorithm, uncomment and complete the stub for function `nextGeneration()` in the implementation file. Compile your code, and test the program using `test.life`. Your program should now be fully functional and ready to use to play the game of life.

## Playing The Life Game

Playing the game of Life consists of creating initial configurations of organisms, and then running the program and stepping through the generations to see what happens to the society as time passes. While `test.life` gave us a simple way to see if our program was working correctly, that particular configuration is actually quite dull, because very little changes as time passes.

To see an even more stable configuration, try the configuration in `stable.life`. The organisms in this configuration don't change at all from generation to generation, and are effectively immortal under the rules of the game.

By contrast, some initial configurations are very unstable, and the society of organisms quickly breaks down, resulting in their extinction. Try `quick.life` for an example.

With other configurations, the society seems to flourish for a while, and then extinction occurs quite suddenly and unexpectedly. Try `cross1.life`.

Sometimes a few individuals make all the difference between whether a society flourishes or becomes extinct. The initial configuration in `cross1.life` is the following iron cross:

```
* * *
*
*     *     *
* * *   * * *
*     *     *
*
* * *```
`cross2.life` simply adds another organism at the end of each cross:
```
*
* * *
*
*     *     *
* * * *   * * * *
*     *     *
*
* * *
*```

Question #13.2: How does this second cross-society fare compared to the first cross-society?

Each of our configurations has thus far been symmetric, but there is no requirement that this be the case. Some asymmetric configurations are more interesting than the symmetric ones. For example, try out `glider.life`. This particular society goes through a periodic cycle of four configurations, and each cycle moves a space across the grid. The result is a migratory society that moves through the grid as time passes. This behavior is similar to that of some insect colonies, or flocks of birds.

When two gliders collide, the results are unpredictable. Sometimes they lead to extinction of both societies and sometimes they result in something entirely different.

Question #13.3: What happens with the gliders in `gliders.life`?

Make copies of `blank.life`, and edit these copies to create your own original configurations. Run them through your program. Keep experimenting until you find a simple initial configuration that after 100 generations is still changing.

## Submit

Submit a copy of all of your code as well as your answers to the questions posed in this lab exercise. Also submit your alive-after-100-generations configuration, and a transcript of a sample execution of your program on this configuration.

## Terminology

cell, column, game of life, generation, one dimension, organism, row