Life on a large field
John Conway’s Game of Life runs on a field of H rows of W cells. Each cell is alive or dead. In one generation all cells change simultaneously: a live cell with two or three live neighbours stays alive, a dead cell with exactly three live neighbours comes alive, and all other cells are dead in the new generation. A cell’s neighbours are the eight cells around it. There are no cells beyond the edge of the field: you can assume it is always dead there.
How many cells will be alive after k generations? In one of the tests the starting field is the photograph “Water and mountains” after Floyd–Steinberg dithering from the article on vectorization: black pixels are live cells.
Input
The first line holds H, W and k (1 ≤ H, W ≤ 600, 0 ≤ k ≤ 100). Then H lines of W characters: # is a live cell, . a dead one.
Output
A single number: how many cells are alive after k generations.
Examples
Example 1
6 6 4 .#.... ..#... ###... ...... ...... ......
5
Example 2
5 5 12 ..... ..#.. ...#. .###. .....
4
Limits
- Time · Python
- 5000 ms
- Time · Go
- 2000 ms
- Memory
- 256 MB
- Judging
- 10 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Count the amount of work: 600 × 600 cells, a hundred generations, eight neighbours per cell. How many Python interpreter steps is that if each cell is visited by a loop?
2Hint 2
Generations go strictly one after another: the next cannot be computed until the previous one exists. But within one generation cells do not depend on each other: all new values are computed from the old field. How do you count all neighbours of all cells at once?
3The idea
Vectorise over the field, loop over generations. The number of live neighbours of all cells at once is the sum of eight shifted copies of the field, exactly like the 3 × 3 blur in the article. Surround the field with a border of dead cells, and each shifted copy becomes a slice of this array. The new field is one logical expression over whole arrays: “three neighbours” or “two neighbours and the cell is alive”.
4Walkthrough
In Python with numpy: an array padded of size (H + 2) × (W + 2) filled with zeros; each generation the current field is placed in its middle, and the number of neighbours is the sum of eight slices like padded[:-2, 1:-1]. All eight slices are views of one array, with no copying; they are added in uint8, where eight fits with room to spare. The new field is (n == 3) | ((n == 2) & (alive == 1)). Inside numpy this is a few passes over 360 thousand bytes, and a generation takes a fraction of a millisecond.
In Go there is no reason to vectorise: an ordinary double loop over cells is machine code, and it gets through a hundred generations of a 600 × 600 field in tenths of a second. All it needs is two buffers, the old field and the new, and a border of dead cells so as not to check bounds.
4+Solution
5Complexity
O(k·H·W) with any method: 3.6·107 cell updates. The difference is in the cost of one update: in a Python loop it is dozens of interpreter steps, in numpy and in Go a few machine instructions.
6Common mistakes
- A Python loop over cells. Correct, but does not fit in the time; this is
wrong.py. - The field in one array. If new values are written straight into the same field, the neighbours to the right and below will be counted from the new generation already. A second field is needed, or, as in numpy, the new field computed whole from the old one.
np.roll. The best-known way to count neighbours in numpy is shifting withnp.roll. Butrollcarries what goes past the edge to the other side: the field becomes a torus, and cells at the left edge see neighbours at the right. In this problem it is dead beyond the edge, and the answer diverges already on the second example: on a torus the glider passes through the corner and flies on, five cells instead of a block of four.- A sum of Boolean arrays. If the field is stored as
booland the shifts are added, numpy adds them as “or”:True + Truein a Boolean array isTrue. Then there is never more than one neighbour, no cell ever comes alive, and the answer is zero everywhere. An integer type is needed before adding.