The British
Informatics Olympiad Sponsored by Data Connection. |
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:
|
..... ..... ...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.