UNIVERSITY OF CAMBRIDGE COMPUTER LABORATORY

Computer Science Tripos 1975/76

Assessed Exercise No.1

Conway's Game of Life

An infinite rectangular two-dimensional grid is such that at a given "generation" each grid point may or may not be occupied by a single "spot".

Each grid-point is adjacent to eight others (diagonal adjacency is counted) and the rules for determining whether a grid-point is occupied at the next generation are as follows:

  1. An extant spot will survive to the next generation if and only if it is adjacent to two or three other spots.
  2. A spot will be created at an unoccupied grid-point if and only if that point is adjacent to exactly three occupied grid points.
  3. (Obvious point.) The evaluation of all grid-points is supposed to be simultaneous and the changeover from one generation to the next is instantaneous. There are no intermediate stages.

By way of example, an isolated L array develops thus:

  o      o     oo     oo
  ooo    oo    oo    o  o
          o    oo     oo

The last pattern is stable since each occupied grid-point is adjacent to two other occupied grid-points and no unoccupied grid-point is adjacent to three occupied ones.

Outline of problem

Write a program to simulate the above, which will accept the following data:

  1. An easy to understand way of representing an initial arrangement of spots.
  2. The number of the generation to which you want the program to run (you may count the initial arrangement as generation zero).
  3. A number whose reciprocal gives the fraction of the total number of generations which gets displayed. (This is to save paper! Thus 6 would mean only generations 0, 6, 12, etc. get displayed.)

The program should interpret the date and display, in a suitable way, on printer or console paper, the initial arrangement and appropriate subsequent arguments.

Points to note

  1. You may use any programming language you like and any computer you can get hold of.
  2. You may display the changing spot arrangement in any way you please. When the complete pattern can be contained on one page of printer paper it should be shown in its entirety. You must make a reasonable decision about patterns which will not fit.
  3. Your program should be able, in principle, to cope with at least 1000 spots anywhere on a 1000000 x 1000000 grid.(Thus only time should prevent a run to 50000 generations if no generation on the way involves more than 1000 or so spots.)

Specific requirements

After writing the program you should produce a report which includes two parts:

Part 1 should provide very simple documentation sufficient to enable an unskilled user to drive your program. The manner of the presentation of data and the use of defaults must be clearly described. Note that unskilled users like to see EXAMPLES OF COMPLETE JOBS.

Part 2 should document how your program works. You should explain very clearly (WITH DETAILED DIAGRAMS) how the program allocates and manages storage space. Part 2 should enable an experienced programmer to make changes to your program without much effort.

If keywords are permitted in data then (e.g.) ROWS (no quotes) is deemed more acceptable than "ROWS"!

Completed exercises must be handed to Mrs. Hedge by 20 November 1975.

F.H. King

J.K.M. Moody

25 October 1975