g Generations On a Grid With No Edges
An r by c grid of cells, each 0 or 1, steps through g generations
under this rule, applied to every cell simultaneously from the previous
generation only:
a live cell stays alive if 2 or 3 of its neighbours are alive, otherwise it dies
a dead cell becomes alive if exactly 3 of its neighbours are alive
A cell has eight neighbours, and the grid WRAPS in both directions. The cell below the bottom row is in the top row of the same column, the cell left of column 0 is in the last column of the same row, and the corners wrap diagonally. There is no edge anywhere, so every cell has exactly eight neighbours.
Print the grid after exactly g generations, as r lines of c characters.
r = 3, c = 3, g = 1, grid = 010 / 010 / 010 -> 111 / 111 / 111
That answer surprises people, and it is the point of the problem. On a
non-wrapping three by three grid the same input gives a single horizontal bar.
Here the column of three live cells wraps, so every cell in the grid has
exactly three live neighbours, and the whole grid comes alive at once. Compare
#2127, which is this rule for one generation with hard edges.
## What most people try first
Writing the bounds test and then "also handling" the wrap, which usually turns
into clamping: an index of -1 becomes 0, and an index of r becomes
r - 1. Clamping makes a cell its own neighbour instead of reaching the far
side, so edge cells get neighbour counts that are too high and the grid behaves
nothing like a torus. There is no bounds test in a wrapping grid at all.
## Two ways to wrap, and both are worth knowing
Modulo in the index:
a = (i + di + r) mod r
b = (j + dj + c) mod c
The + r and + c matter: in C, C++, Java and JavaScript a negative value
modulo a positive one is negative, so -1 mod r is -1 and the read goes
before the start of the array. Python is the exception.
Or a halo copy, which is the version used in production code because it keeps
the inner loop free of arithmetic. Build an (r + 2) by (c + 2) grid, put the
real grid in the middle, fill the extra top row from the real bottom row, the
extra bottom row from the real top row, the extra left column from the real
right column, the extra right column from the real left column, and the four
extra corners from the diagonally opposite real corners. After that, plain
indexing from 1 to r and 1 to c is correct, and no modulo appears in the
hot loop. Both are correct and the two are used to verify each other here.
## Why it is correct
The rule defines generation k + 1 cell by cell as a function of generation
k, so the two requirements are that every neighbour read comes from the
previous generation and that the eight neighbours named are the right eight.
The first is handled by writing into a separate grid, as in #2140. The second
is what the wrap specifies: the neighbours of (i, j) are the eight cells
((i + di) mod r, (j + dj) mod c) for the eight non-zero offsets, and modulo
arithmetic is exactly the statement that the grid is a torus. The halo copy
agrees with it because each border entry of the halo is filled with the cell
that the modulo formula would have reached, so reading the halo at
(i + 1 + di, j + 1 + dj) returns the same value as reading the real grid at
the wrapped position.
## The small grids, settled
On a one by one grid the single cell is all eight of its own neighbours, so its
neighbour count is 8 if it is alive and 0 if it is dead. Either way it is dead
next generation, since 8 is not in {2, 3} and 0 is not 3. When r is 2, the
rows above and below a cell are the same row, so that row's cells are counted
twice. When c is 2 the same happens with columns. These are legal inputs, they
are what the stated wrap means, and three of them are declared tests.
## Cost
O(r c) per generation with eight reads each, so O(r c g), at most about a
million cell reads at the stated limits, and O(r c) memory.