# Lab 11: Multidimensional Arrays and Vectors

## Introduction

We have seen that we can use arrays or `vector`s to store sequences of values. For example, the declarations

`    double arrvec[50];`
and

`    vector<double> arrvec(50);`

define an object `arrvec` as a container that can store 50 `double` values.

We usually visualize such a container as one-dimensional objects — i.e., a linear sequence of values. And as we saw in the previous lab exercise, a single index is sufficient to access the elements of a one-dimensional array or vector because it is a linear structure.

There are, however, many objects that are more naturally visualized as having two (or more) dimensions such as a tic-tac-toe game

and a magic square

which are organized into rows and columns.

Such two-dimensional structures can be represented in a program as an array of arrays such as

`    int magicSquare[3][3];`
or as a vector of vectors:

`    vector< vector<int> > magicSquare;`
To access an element of a two-dimensional array or `vector`, two indices are needed: the first to specify the row in which it located and the second to specify a column within that row. For example, we could access the integer 17 in the upper left corner of `magicSquare` with the expression

`magicSquare[0][0]`

the integer 11 in the lower left corner with

`magicSquare[4][0]`

and the integer 13 in the center with

`magicSquare[2][2]`

In this lab exercise, we will use a two-dimensional array to implement an interesting game known as the game of life.

## The Game of Life

The Game of Life (also known simply as Life) is a cellular automaton that was devised by the British mathematician John Conway as a simple model of a society of organisms. The "playing board" is a rectangular grid of cells. Each cell in the grid (except along the border) has eight neighboring cells: 3 cells above it, 3 cells below it, and 1 on each side of it.

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

The game consists of a series of generations. You provide the initial configuration of organisms, and each generation thereafter is determined by applying the following rules to the previous generation:

1. If an empty 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.

For example, suppose that we begin with the following configuration of three organisms:

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

• Cells in the first column — locations `[0][0]`, `[1][0]`, `[2][0]`, `[3][0]`, `[4][0]` — and those in the last column — `[0][4]`, `[1][4]`, `[2][4]`, `[3][4]`, `[4][4]` — have no neighbors and thus remain empty.
• Cells `[0][1]`, `[1][1]`, `[0][2]`, `[0][3]`, `[1][3]`, `[3][1]`, `[3][3]`, `[4][1]`, `[4][2]`, and `[4][3]` each have one neighbor so they also remain empty.
• Cells `[1][2]`, and `[3][2]` each have one neighboring organism, so the organism in them dies of loneliness.
• Cells `[2][1]`, and `[2][3]` have three neighboring organisms, so an organism is born in each of them.
• Cell `[2][2]` has two neighbors, so it remains unchanged.

Represented graphically, the second generation is

To get the third generation, we apply the rules to the second generation. Organisms are born in cells `[1][2]` and `[3][2]` and the organisms in cells `[2][1]` and `[2][3]` die, which means that we have returned to the original configuration!

This particular configuration continues to oscillate back and forth from generation to generation. We might think of this as representing a society of organisms that although changing from one generation to the next, it 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 eventually become extinct. Examples of these kinds of behavior will be described later in this lab exercise.

## Files

• `life.cpp` implements the game of Life. It reads the initial configuration from a data file, stores it in a two-dimensional array, and displays its contents so it can be checked by the user. It will then ask the user for the number of successive generations to be produced and will then produce and output them to a file specified by the user.

You should download this file and add your name and other information required by your instructor to the opening documentation. As you work through this lab exercise, you will be adding to and/or modifying this program.

• The data files to be read by this program begin with the number of rows and columns in the grid followed by rows of 0s and 1s, one for each row in the grid, and each row containing an entry for each column in the grid — 0 representing an empty cell and 1 representing a cell occupied by an organism. For example, the file `test.life` that you will use in this lab exercise contains the following initial configuration for the simple three-organism oscillating pattern described earlier:
```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 ```

Here are other data files you should try with your program after you get it written: `stable.life`, `quick.life`, `cross1.life`, `cross2.life`, `glider.life`, `gliders.life`, and `blank.life`.

## Design

This lab exercise is to complete the `life.cpp` program. This will involve adding and testing code to do the following:

1. Read the grid configuration from a data file and store it in a two-dimensional array.
2. Display the contents of this file on the screen so they can be checked.
3. Write a `display()` function to output each generation to a file via an `ostream`.
4. Write a `generate()` function to generate the next generation.

## Implementation

Now that we have the operations identified, we can start writing code to implement them. So open the file `life.cpp` which contains a partially-written program that you will be completing and testing in this lab exercise.

### Modeling the Life grid

To represent the grid we will use a two-dimensional array (or if your instructor prefers, a `vector` of `vector`s.) However, to create this array, we need to know:

— its dimensions, and
— the type of its elements.

We can define a two-dimensional array type with a declaration of the form

```typedef ElementType ArrayTypeIdentifier[ROWS][COLUMNS];
```

where `ROWS` and `COLUMNS` are integer constants that specify the array's dimensions;
`ElementType` is the type of its elements; and
`ArrayTypeIdentifer` is the name of this new type that we have defined.

Question #11.1 Define an array type named `LifeGrid` at comment #1 near the beginning of `life.cpp`. For this exercise, all of the grids will have 50 or fewer rows and columns so you can use this to specify the number of rows and columns. As explained next, we will use `short` (or `short int`) for the type of the array elements.
We turn now to the question of why we are using `short` for the type of the cells when all of our examples represented the presence of an organism with an asterisk (`*`) and an empty cell with a blank. So wny not use `char` for the cell type?

If we look at the most important operation of a `LifeGrid` object — generating a new generation — and at the rules for producing a new generation, we see that they involve counting neighboring organisms. This would mean counting the number of times a certain character — an asterisk — appears in each of the neighboring cells by comparing each of their contents with an asterisk. And this must be done for every cell in the grid! But if we use a grid of integers rather than characters, representing the presence of an organism with 1 and an empty cell by 0, no comparisons are required — just sum the values in the neighboring cells! And because there are only eight neighbors, we can use short integers to reduce the memory requirements for this array.

But what about the earlier pictures of a `LifeGrid` object? If the asterisks are replaced by 1s and the empty cells with 0s, it surely won't be as picturesque as the asterisk-blank representation! The solution? Let's use the 0-1 representation in the data file that will be input and stored internally as a grid of 0s and 1s but then output it as the more visually pleasing grid of asterisks and blanks!

### Constructing the `LifeGrid`

After the opening information about the game of Life and the maximum size allowed for a grid, the `main()` function in `life.cpp` begins by creating the `LifeGrid` array `grid` as a `MAX_ROWS` x `MAX_COLUMNS` array. It then asks the user for the name of a file containing a Life pattern and vvvopens an `ifstream` named `fin` to that file.

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 those 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 5 × 5 grid (as specified in the first line of the file), each `1` represents a cell containing an organism and each `0` represents a cell without an organism. Note: Any whitespace can be used to separate the cells in the file; in this example, single spaces and newlines were used to make it easy to read.

Question #11.2 At comment #2 in `main()` of `life.cpp`, write code to read the number of rows and columns in the grid of cells from the data file via the input file stream fin. Then use nested for loops to copy the 0s and 1s from the data file via the `ifstream fin` into the upper-left corner of `grid` — i.e., this grid of cells would be copied into rows 0, 1, ..., 4 and columns 0, 1, ..., 4 of `grid`.

Now that the Life configuration has been transferred from the file to `grid`, we can move on to task #2 in our design plan:

2. Display the contents of this file on the screen so they can be checked.

Question #11.3 At comment #3 in `main()` of `life.cpp`, display the contents of `grid` using the same format as shown above:
```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```

### The `display()` Function

The format of our output of `grid` is the same as that in the data file from which its contents were transferred. But in the game of Life, the grids are shown as grids of cells in which an asterisk is used instead of 1 and a space instead of a zero. The function `display()` will output `grid` in this asterisk-space format. And to give it somewhat of a grid-like appearance, it will output periods to mark the corners of the cells.

Also, for some patterns it can take a large number of generations to study their behaviors. To make it easier to study the successive generations, we will output them to a file so they can be examined later.

Question #11.4 The opening statements of the function `display()` output a top border for the grid by writing a series of period-space combinations ( ` ". "` ) to a file via the `ifstream` `fout`. At comment #4 in the definition of this function, write nested loops to output the rest of the grid by outputting in each row:

`    ". "` (to mark the left border) followed by `"* "` for each 1 and `". "` for each 0 in that row.

For the file "`test.file`", the first two generations will be output as:

``` Generation #1 . . . . . . . . . . . . . . . . . . . . . . . * * * . . . . . . . . . . . . . . . . . . . . . . . Generation #2 . . . . . . . . . . . . . . . . . * . . . . . . * . . . . . . * . . . . . . . . . . . . . . . . . ```

Here is an algorithm for this part of `display()` that may help with writing the code:

• For each index `r` in the range 0 .. numRows do the following:
• Output ".` `"     // for the left border
• For each index c in the range 0 .. numColumns do the following:
`    `If grid[r][c] is 1
`       `Display "*` ` "
`    `Otherwise
`       `Display ".` `"
• Move to a new line.

### Generating The Next Generation

The function `generate()` is the workhorse of this program because it must encode the rules of the game:

• For each cell c in the grid:
• If c has exactly three neighboring cells containing 1s, then
c should contain a 1.
• Otherwise if c has fewer than two neighbors containing 1s
or c has more than three neighbors containing 1s, then
c should contain a 0.

In order to process all of the cells, we will need two nested `for` loops again to process the rows and columns of `grid`. The inner loop should count the number of neighbors for the current cell and then set the value of that cell appropriately as required by the rules of the game.

But there are two problems. First, the next generation is determined by the current generation. We cannot overwrite the current generation with the next one because the current generation is needed to determine the next. So we will begin by making a copy of `grid` and then use this copy to calculate each cell's neighbors.

The second problem is that cells at the edges of the grid do not have the required eight neighbors. To simplify things, we'll assume that these are "boundary" cells and don't ever change; so we can simply exclude them from consideration by letting the row index run from 1 to `numRows` − 1 and the column index run from 1 to `numColumns` − 1.

This gives the following (partial) algorithm for generating the next grid of cells:

1. Make a copy `newgrid` of `grid`.
2. For each index `r` in the range from 1 to `numRows` − 1
For each index `c` in the range from 1 to `numColumns` − 1
a. Calculate topNeighbors = ```grid[r - 1][c - 1] + grid[r - 1][c] + grid[r - 1][c + 1]```
b. bottomNeighbors = ???
c. sideNeighbors = ???
d. Calculate `neighbors` = sum of the three preceding sets of neighbors.
e. Apply the rules of the game to set `newgrid[r][c]`
3. Now copy `newGrid` to `grid`. (Because it is a reference parameter, it will be passed back to `main()`.)

As we noted earlier, because 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 in Step 2-d of the algorithm.

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

Question #11.5
1. Complete the algorithm above for generating a new Life generation by finding the formulas to replace the ???s in the computations of bottomNeighbors and sideNeighbors.

2. Then, using this algorithm, complete the definition of the function `generate()`. Compile your code, and test the program using `test.life`. When completed, your program should be ready to process other initial configurations.

## Playing the Game of Life

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. Although `test.life` gave us a simple way to check how our program was working, it is a rather uninteresting configuration because very little changes as time passes.

Now try the configuration in `stable.life`. Here the generations don't change at all from one to the next — thus the name. Some initial configurations appear to be unstable but after awhile, they reach stability. Try `quick.life` for an example. And for some configurations, The society of organisms quickly breaks down and after a few generations, becomes extinct; `cross1.life` is one such example.

Sometimes adding or removing a few individuals makes all the difference between on how a society changes. To illustrate thus, here is the initial configuration in `cross1.life`; it is sometimes referred to as an iron cross:

```

* * *
*
*     *     *
* * *   * * *
*     *     *
*
* * *```
Now suppose we add an organism at the end of each cross, as in `cross2.life`:
```
*
* * *
*
*     *     *
* * * *   * * * *
*     *     *
*
* * *
*```

Question #11.6: How do the generations of this cross-society compare with those of 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 `glider.life`. This 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 #11.7: What happens with the gliders in `gliders.life`? Try at least 35 generations. (Looks like we've come full circle!)

## Experiment

The file `blank.life` contains a 25 × 35 grid of all 0s. Make several copies of this file and edit them to create your own original configurations and run them through the Life program. See if you can find a simple initial configuration that is still changing after 100 generations.