In the previous section we have briefly mentioned the type array<array<int> >, which arises when the individual elements of an array are arrays themselves. Whereas an ordinary array extends only in one direction along the real axis, such an array of arrays extends in two directions, one direction per index set.

The special case that the inner arrays are all equally large, that is, that all of them store the same number of elements, occurs particularly often. The index set then can be illustrated as in Figure 2.5 as a rectangle of integer coordinates of the plane. Such a structure is called a two-dimensional array.

Figure 2.5. A two-dimensional array

For this case, namely that the index set is a rectangle of integer coordinates, LEDA offers the type array2. This type differs from the type array<array<int> > by its syntax for access to individual elements and by a somewhat lower memory consumption; if in contrast the inner arrays are not all equally large, the type array<array<int> > rather comes into consideration.

As an example for the use of an array2 we implement a famous population simulation, Conway's game of life: Comical little animals of a certain genre live, die and spawn in a two-dimensional, rectangular world that is divided up into parcels. At most one little animal lives in every parcel. Every parcel has 8 neighbor parcels (apart from the parcels on the edge). Time elapses in discrete steps of one month each. The population changes as follows from month to month:

Figure 2.6 shows how the succeeding population arises from an original population in one iteration step; it contains examples for each of the four rules.

Figure 2.6. The rules of Conway's game of the life

One iteration in Conway's game of life. Little animals 1 die from loneliness. Little animal 2 dies from overspill population. Little animal 3 survives. Little animals 4 are procreated.

Conway's game of life is an example of a cellular automaton. For the implementation of this automaton, that is for the representation of its states, we use a two-dimensional array

array2<bool> cell(N,M);

Every element cell(i,j) of this array specifies whether on parcel (i,j) in the current population a little animal is living or not.

To calculate the new state of the automaton, that is the next population, we look in a function compute_next_state() from every parcel (i,j) into all 8 neighboring parcels and count in a function count_neighbors() how many little animals are living in the neighbor parcels. Here the question arises how we can treat the problem of the edge efficiently. For this purpose, we initialize the parcels of the edge with 0 and count only the inner parcels as belonging to the actual domain. So the parcels on the edge are sentinels who simplify the access code. We iterate only over the inner parcels.

We store the information whether or not a parcel will house a little animal in the next state in a temporary, two-dimensional array cell_new. We copy this array in one single statement

cell = cell_new;

to cell at the end of the computation.

A simple print output of the population is carried out by the function print_cells(), which is invoked by main() in the main loop every time. After this the program waits for user input to give him the possibility of pursuing the evolution of the population step by step on the screen. He can let the simulation run into the next state by entering an arbitrary character except for q. An input of q (Quit) quits the program.

A problem arises at the initialization of the parcels in the function init_cells(). Best would be to use a (pseudo-)random number generator here; however, we will get to know such a generator not until in Section 2.5. (See also Exercise 18.) Therefore, we initialize the array with always the same Boolean values by a simple rule here.

#include <LEDA/array2.h>
#include <iostream>

using leda::array2;
using std::cout;
using std::cin;

const int N = 30; // number of cells on x-axis
const int M = 30; // number of cells on y-axis

array2<bool> cell(N+2,M+2), cell_new(N+2,M+2);

void init_cells();
void print_cells();
void compute_next_state();

int main() 
{
  char user_input;

  init_cells();
  
  while(true) { 
    print_cells();
    compute_next_state();
    cin >> user_input; // let user manually step through states 
    if(user_input == 'q') // q = 'Quit'
      break;    
  }    
}

void init_cells() 
{
  // init boundary
  for(int i = 0; i < N+2; i++) 
    cell(i,0) = cell(i,M+1) = false;
  for(int j = cell.low2(); j <= cell.high2(); j++) 
    cell(cell.low1(), j) = cell(cell.high1(), j) = false;
    
  // init interior
  for(int i = 1; i < N; i++)
    for(int j = 1; j < M; j++)
      cell(i,j) = (( i + j ) % 2 ? true : false); 
      // (better use random_source here)
}

void print_cells() 
{
  cout << "\n\n\n"; 
  for(int j = 1; j <= M; j++) {
    for(int i = 1; i <= N; i++) 
      cout << (cell(i,j) ? '*' : ' ');
    cout << "\n";
  }
}

int count_neighbors(const int i, const int j)
{
  int nn = 0; // number of neighbors of cell(i,j)

  nn += cell(i-1,j-1);
  nn += cell(i-1,j);
  nn += cell(i-1,j+1);
  nn += cell(i,j-1);
  // do not count cell(i,j) itself!
  nn += cell(i,j+1);
  nn += cell(i+1,j-1);
  nn += cell(i+1,j);
  nn += cell(i+1,j+1);

  return nn;
}

void compute_next_state() 
{  
  for(int i = 1; i <= N; i++)
    for(int j = 1; j <= M; j++) {
      int num_neighbors = count_neighbors(i,j);
      bool new_state = true; // assume there will be life
      if(cell(i,j)) // if populated
        switch (num_neighbors) {
         case 0: case 1: 
         case 4: case 5: case 6: case 7: case 8:
           new_state = false;
	 }
      else // not populated
        if(num_neighbors != 3)
          new_state = false;
      cell_new(i,j) = new_state;
    }
  
  cell = cell_new; // bitwise copy by LEDA rule 8
}

(We should run this program now on our machine and watch the output.)

The coordinates of the index rectangle must be specified at the definition of an array2. The above definition

array2<bool> cell(N+2,M+2);

with two arguments defines implicitly the rectangle [0..N+1] x [0..M+1]. (To remain solid with the definition of one-dimensional arrays, the number of elements per dimension is specified here.) All 4 coordinates can also be specified explicitly, like in

array2<bool> cell(0,N+1,0,M+1);

As a matter of course the lower bound of the interval does not have to be 0 here; it may well be any arbitrary (even negative) integer number.

The element at position (i,j) can be accessed via the overloaded function operator cell(i,j). It returns a reference to this element.

According to the methods low() and high() of class array, class array2 offers the methods low1(), high1(), low2(), and high2(), which return the smallest and largest index in the respective dimension, respectively. An example of the use of these methods is found in the second for-loop of init_cells().

Exercises

Exercise 6.

The eight-queens-problem consists of placing eight queens on a chessboard so that no queen attacks another one. Write a program that calculates all possible solutions of this problem. Use an array2 for the coding of the chessboard.

Exercise 7.

In the game Tic-Tac-Toe two players are facing each other on a field of 3 times 3 squares. They alternately mark crosses (player A) or circles (player B) on still free squares. A player wins if he can mark adjacent 3 crosses or 3 circles, respectively, in a line, column or diagonal. Figure 2.7 shows a game course in which player A wins in the 7th move. Figure 2.7. Tic-Tac-Toe Write a program that proves that the score is a draw from the very first move on, that is, that the game always ends in a tie if both players always make an optimal move in every position, or watch the film “Wargames”.