The Generation It Stops Changing
An r by c grid of cells, each 0 or 1, steps through generations. A
cell's eight surrounding cells are its neighbours; cells outside the grid are
never alive and the grid does NOT wrap.
The rule is given as two sets of digits:
B a dead cell becomes alive if its number of live neighbours is in B
S a live cell stays alive if its number of live neighbours is in S
Anything not covered by those two lines leaves the cell dead. Each set is
written as its digits in increasing order with no spaces, or as a single -
when the set is empty. All cells change simultaneously, from the previous
generation only.
Print the smallest generation number t, counting from 1, such that generation
t is identical to generation t - 1. If no such t exists within the first
g generations, print -1.
``` r = 3, c = 3, g = 5, B = 3, S = 23, grid = 010 / 010 / 010 -> -1
this blinker alternates between a vertical and a horizontal bar forever, so it never equals its own previous generation
r = 3, c = 3, g = 5, B = 3, S = 23, grid = 110 / 110 / 000 -> 1
a block is already stable, so generation 1 equals generation 0 ```
## What most people try first
Testing whether the grid has stopped changing by checking whether it equals one
seen EARLIER, rather than the one immediately before. That answers a different
question. The blinker above returns to generation 0 at generation 2, so an
"equals any earlier generation" test reports 2, while the answer asked for here
is -1 because the grid never stands still.
The other common version is to check for stability by looking at whether any single cell changed during the generation, which is the same test written differently and is fine, as long as the flag is set from the comparison of the new value with the OLD value and not with a value already overwritten.
## The method
for t from 1 to g:
build nxt from cur, every cell at once
if nxt equals cur: print t and stop
cur = nxt
print -1
Note that t is reported, not t - 1: the question asks for the generation
that turned out to be a copy, so a grid that is stable from the start answers 1.
## Why it is correct
The loop computes generation t from generation t - 1 for t ascending, and
compares each new generation with the one it was built from. So the first t
at which the comparison succeeds is by construction the smallest t with
generation t equal to generation t - 1, and if the loop runs to g without
succeeding then no such t is at most g, which is exactly when -1 is
correct.
There is one thing worth noticing about such a t: once found, the grid is
frozen forever. Since generation t + 1 is a function of generation t alone,
and generation t equals generation t - 1, generation t + 1 equals
generation t, and by induction every later generation is the same. So this
single comparison really does detect permanent stability rather than a
coincidence, and there is no need to keep looking.
## The boundary that breaks a careless implementation
The corner and edge cells have fewer than eight neighbours, and the missing
ones count as dead rather than being skipped from the count. On a one by one
grid a cell has zero live neighbours always, so with B = 3 a dead cell stays
dead and generation 1 equals generation 0, giving 1; with the same B a LIVE
cell has 0 neighbours, 0 is not in S = 23, so it dies at generation 1 and
generation 2 is the first copy, giving 2. Both are declared tests.
An empty set written as - is legal on either line. S = - means every live
cell dies immediately whatever its neighbours.
## Cost
O(r c) per generation with eight neighbour reads each, so O(r c g) in
total, at most about a million cell reads at the stated limits, and O(r c)
memory for two grids.