One Generation, All At Once
A grid of cells is given, each alive (1) or dead (0). Compute ONE
generation and print the result. Every cell changes at the same instant,
according to its eight neighbours in the PREVIOUS generation:
alive with 2 or 3 living neighbours stays alive
alive with any other count dies
dead with exactly 3 living neighbours becomes alive
dead with any other count stays dead
Cells outside the grid do not exist and never count as alive. The grid does not wrap.
010 000
010 -> 111 a vertical bar becomes a horizontal one
010 000
## The whole problem is the word SIMULTANEOUS
Every cell must be decided from the grid as it was BEFORE this generation started. Updating cells in place, one after another, means a cell halfway through the grid sees neighbours above and to its left that have already changed, and neighbours below and to its right that have not. The result is neither this generation nor the next.
That version is not subtly wrong on rare inputs. On the three-cell bar above, the correct answer is a horizontal bar and the in-place version produces an empty grid, because by the time it reaches the middle cell the top one is already dead and the count is wrong.
Five of the nine declared tests here distinguish the two.
## So write to a second grid
next = a fresh grid of the same size
for every cell:
count its living neighbours IN THE OLD GRID
write the new state into NEXT
print next
Two grids is the straightforward fix and costs O(r c) extra memory. Doing it
in place with O(1) extra is possible by storing both states in one cell, for
instance keeping the old state in the low bit and the new state in the second
bit, then shifting everything down at the end. That trick is worth knowing and
is not required here.
## Counting the neighbours
Eight offsets, skipping (0, 0), with a bounds test on each. The bounds test is
where the other common bug lives: a cell on the edge has fewer than eight
neighbours, and reading outside the grid either crashes or, in languages where a
negative index wraps to the far end, silently counts a cell from the opposite
side of the grid.
## Cost
O(r c) time with eight neighbour reads per cell, so about 8 r c operations,
and O(r c) memory for the second grid.