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

Constraints - `1 ≤ r, c ≤ 50` - `0 ≤ g ≤ 50` - every grid character is `0` or `1` - the grid wraps in both directions, so every cell has exactly eight neighbours - when `r` is 1 or 2, or `c` is 1 or 2, a neighbour position may coincide with the cell itself or be counted twice; that is what the wrap means - all cells change simultaneously, from the previous generation only