[BIO97 Logo] The British Informatics Olympiad
Sponsored by Data Connection.
[Data Connection logo]
-----
Sample Paper: Solution to Question 2
Question
statement
'Life' is a computer simulation played out on a rectangular board of squares. Each square has two possible states, on ('0' - zero) or off ('.'), and the state of the squares at the next generation is fully determined by the current state and some simple rules. The configuration at generation 0 is selected by the user.

Each square on the board has eight neighbours, those touching it directly (including diagonally), except border squares which have some of these pieces missing.

The rules for generating the next generation are:

Survival Any 'on' square with two or three neighbouring 'on' squares stays 'on' next generation.
Death Any 'on' square with less than two or more than three neighbouring 'on' squares goes 'off' next generation.
Birth Any 'off' square with exactly three neighbouring 'on' squares goes 'on' next generation. Otherwise it stays 'off'.
The rules stay the same for border squares, though they have fewer neighbours - in other words squares outside the 11x11 board are to be treated as permanently off. You should also remember that all births, deaths and survivals between generations occur simultaneously. For example:
Generation 0 ..0..
...0.
.000.
.....
.....
Generation 1 .....
.0.0.
..00.
..0..
.....
Generation 2 .....
...0.
.0.0.
..00.
.....
-----

The game of life is a good example of emergent behaviour, where a simple set of rules can produce a fascinating range of patterns. This question was designed to provide an introduction to the game - and uses very small boards for speed of entering data - but the idea can easily be adapted to very much larger boards, different rule sets, spontaneous generation and other interesting variations.

-----
Sample run
2 (a)
[25 marks]
You are to write a program to play Life on an 11x11 board. Your program should first read in a 5x5 board, which will be in the form of five lines of five characters (either '0' or '.'). This 5x5 board should be used as the centre section of the 11x11 board for generation 0, the rest of which is to be treated as off. This will be generation 0 for the entire run of your program. Once this is done you should display generation 0.

Until your program terminates you should repeatedly wait for input, and then:

  1. If you receive an integer 'n' with a hash before it (such as #5), you should calculate generation 'n' and display it on the screen.
  2. If you receive an integer 'n' with a plus before it (such as +5), you should calculate 'n' generations on from the last generation shown, and then display the new one on the screen.
  3. If you receive the number -1 you should terminate.
  4. Ignore any other input.
.....
.....
...0.
....0
..000

...........
...........
...........
...........
...........
......0....
.......0...
.....000...
...........
...........
...........


#5
...........
...........
...........
...........
...........
...........
...........
......0.0..
.......00..
.......0...
...........


+1
...........
...........
...........
...........
...........
...........
...........
........0..
......0.0..
.......00..
...........
-----

The solution to this part can be broken up into three stages:

Representing the board

The board on which the game of life is played must have the following characteristics. It must represent the on or off state (a simple Boolean (true/false) variable will suffice for this). It must be large enough to hold the data, and must also include space for one extra line of cells outside the board, which we are told must be treated as permanently off.

In Pascal, suitable definitions are:

const
  BoardSize = 11;

var
  Gen0,
  OldBoard,
  Board: array[0..BoardSize+1, 0..BoardSize+1] of Boolean;

We have allocated three such variables, one to represent the initial board (generation 0), and two to store the state of the board as it evolves. The cells from (1,1) to (BoardSize, BoardSize) represent the actual board, and the extra border at 0 and BoardSize+1 - which will be set 'off' - allows us to use a simple routine to count the number of 'on' neighbours.

Reading in the data

The first step, before reading in the data, is to initialise the board holding generation 0, including the border outside, to be off. This is accomplished by:

var
  i, j: Integer;

  for i := 0 to BoardSize+1 do for j := 0 to BoardSize+1 do
    Gen0[i, j] := False;

We read the keyboard input into a sub-board, and then copy this into the main board:

const SubBoardSize = 5;
var
  SubBoard: array[1..SubBoardSize, 1..SubBoardSize] of Boolean;
  c: Char;

  WriteLn('Enter starting board with . representing off, anything else means off');
  for i := 1 to SubBoardSize do
  begin
    for j := 1 to SubBoardSize do
    begin
      Read(c);
      SubBoard[i, j] := not (c = '.');
    end;
    ReadLn;
  end;
  Write('Board read in...');

  for i := 1 to SubBoardSize do for j := 1 to SubBoardSize do
    Gen0[
      i + (BoardSize - SubBoardSize) div 2,
      j + (BoardSize - SubBoardSize) div 2] := SubBoard[i, j];
  WriteLn('making Generation 0 as follows:');
  Board := Gen0;
  ShowBoard;

(Not all languages will allow you to copy one array onto another with a statement like Board := Gen0; - but this can be done using a pair of for loops.)

The last line fulfils another requirement set out in the question, that of displaying generation 0. We call a procedure ShowBoard, which displays Board in the required format. This will also be useful later on.

procedure ShowBoard;
var i, j: Integer;
begin
  for i := 1 to BoardSize do
  begin
    for j := 1 to BoardSize do
    begin
      if Board[i, j] then Write('0') else Write('.');
    end;
    WriteLn;
  end;
end;

Calculating generation n

We must now implement the rules of the game of life to step from one generation to the next. Going to generation n can then be derived by stepping n times from generation 0.

Consider a procedure Step, which takes the current state of Board and computes the next generation. We must make a copy of the board (using OldBoard), then for each square count the number of 'on' neighbours. If c is the count of neighbours, then the square will be on if c=3 (birth or survival) or if c=2 and it was on in the previous generation (survival).

Pascal code which does this is as follows:

procedure Step;
var i, j, c: Integer;
begin
  OldBoard := Board;
  for i := 1 to BoardSize do for j := 1 to BoardSize do
  begin
    c := 0;
    if OldBoard[i, j - 1] then Inc(c);
    if OldBoard[i, j + 1] then Inc(c);
    if OldBoard[i - 1, j - 1] then Inc(c);
    if OldBoard[i - 1, j] then Inc(c);
    if OldBoard[i - 1, j + 1] then Inc(c);
    if OldBoard[i + 1, j - 1] then Inc(c);
    if OldBoard[i + 1, j] then Inc(c);
    if OldBoard[i + 1, j + 1] then Inc(c);
    Board[i, j] := (c = 3) or (OldBoard[i, j] and (c = 2));
  end;
end;

The final stage of the program is to take the required keyboard input, and step to the specified generation or exit as appropriate.

In Pascal, the function Val(s, n, c) reads an integer value from string s and places the value in n. If there is an error (such as a non-numeric character), c points to the offending character, otherwise it is zero. We can then use a case statement to choose the appropriate action depending on whether +, # or - start the line of text. The program's main loop is then:

var
  o: Char;
  s: String;
  n: Integer;
  c: Integer;

  repeat
    WriteLn;
    WriteLn('Type command: +N - step N generations, #N - go to generation N, -1 - exit.');
    ReadLn(s);
    case s[1] of
      '+': begin
             s := Copy(s, 2, 255);
             Val(s, n, c);
             if (c = 0) and (n >= 0) then { no error }
             begin
               WriteLn('Stepping ', n:1, ' generations on.');
               StepN(n);
               ShowBoard;
             end
             else
               WriteLn(s, ' is not a valid number.');
           end;
      '-', 'x', 'X': WriteLn('Bye...');
      '#': begin
             s := Copy(s, 2, 255);
             Val(s, n, c);
             if (c = 0) and (n >= 0) then { no error }
             begin
               WriteLn('Stepping to generation ', n:1);
               Board := Gen0;
               StepN(n);
               ShowBoard;
             end
             else
               WriteLn(s, ' is not a valid number.');
           end
    end;
  until (s[1] = 'x') or (s[1] = 'X') or (s[1] = '-');

which should be called after the board has been read in. The procedure StepN simply calls Step n times.

Marking

25 marks are available for 2(a).

In a test which uses only the cells of the centre 5x5 sub-board, 14 marks are awarded as follows: [2] printing generation 0; [8] understanding #1 and advancing a generation; [3] understanding +1; [1] terminating cleanly.

An additional 11 marks are available from a test which examines boundary conditions using the starting board

00000
00000
00.00
00000
00000

as follows: [2] printing generation 0; [8] printing generation 9 with the correct border conditions; [1] terminating cleanly.

If #n is interpreted incorrectly but +n functions OK, +9 should be substituted for #9 in the second of these tests and a total of 7 marks deducted.

A program solving this part of the question on the game of life can be found in life.pas.

-----
2 (b)
[4 marks]
Why is it not feasible to have a '-n' option, which would calculate 'n' generations earlier?
-----

There are three main points to be made for this:

For example,

.0.
0.0
...
or ...
0.0
.0.
give rise to: ...
.0.
...

And

0000
0000
0000
0000

can have no preceding generation according to the rules of the game of life.

Marking

3 marks are awarded for making the points described above. A further mark is available by giving an example, with a total of 4 marks for this part.

-----
2 (c)
[3 marks]
A 'rule set' for Life is the collection of Survive, Death, and Birth rules. Another rule set, for example, could have the same Survive and Death rules, but allow Birth with 3 or 4 adjacent 'on' squares. Note Survive, Death and Birth rules can only depend on the number of adjacent 'on' or 'off' squares. How many possible rule sets are there?
-----

Firstly, this question is (deliberately) misleading. There are not three different sets of rules (survival, birth and death): there are two, as death is simply the opposite of survival.

Consider these two different sets of rules. If the cell is on, the survival rule applies. Depending on the number of neighbours (0 to 8), it will be on or off in the next generation. This rule can be represented by a 9-bit binary number, one bit for each number of neighbours and a 1 or 0 depending on whether the cell will be on or off in the next generation - a total of 2 to the power 9, that is 512, possibilities. If the cell is off, the birth rule applies, with another 2 to the power 9 possibilities of birth (or non-birth) for each number of neighbours.

Marking

3 marks were available for the correct answer, 512 x 512 or 262,144.

Partial marks were awarded for stating only that there are 512 birth or that there are 512 survival/death rules (one mark), or for considering only a number of other sub-sets of the problem.

-----
2 (d)
[8 marks]
Suppose we now limit rule sets so that the only valid Birth rules require "exactly 'n' neighbouring 'on' squares". Consider when generation 0 consists of the middle 5x5 squares all 'on', and all the other squares 'off'. How many rule sets produce, at generation 5, an 11x11 board with all squares 'off'?
-----

It is now specified that there can only be 9 different birth rules, with birth for n neighbours, with n in the range 0 to 8. There are still 512 survival/death rules.

Solving this question needs a further program (or subroutine) to be written which runs through each of the 9 x 512 = 4608 possibilities and tries to see if they satisfy the requirements.

Marking

8 marks are available for the correct answer, 1426. Incorrectly excluding the zero neighbour state for survival gives the answer 1408, for which 6 marks are awarded.

A total of 40 marks are available in question 2.

-----

Solution program

-----
The 1997 British Informatics Olympiad