2144. 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.

Constraints - `1 ≤ r, c ≤ 50` - `1 ≤ g ≤ 50` - each of `B` and `S` is either `-` or distinct digits from `0` to `8` in increasing order - every grid character is `0` or `1` - the grid does not wrap and cells outside it are never alive - all cells change simultaneously, from the previous generation only