Game of Life

Problem

You are given an m x n board of cells, each either alive (1) or dead (0). Every cell has up to eight neighbors (horizontal, vertical, diagonal). The next generation is computed for all cells simultaneously from the current generation using these rules:

• A live cell with fewer than two live neighbors dies.
• A live cell with two or three live neighbors stays alive.
• A live cell with more than three live neighbors dies.
• A dead cell with exactly three live neighbors becomes alive.

Update the board in place to the next generation.

• The board has at most a few dozen rows and columns.
• Cells outside the board are considered dead.

Examples

• [[1,0,0],[0,1,1],[1,1,0],[0,0,1]] → [[0,1,0],[0,0,1],[1,0,0],[0,1,0]]. One generation of an irregular starting pattern.
• [[1,1],[1,0]] → [[1,1],[1,1]]. The dead cell at (1,1) has three live neighbors and is born; each live cell has two live neighbors and survives.
• [[1]] → [[0]]. A lone live cell has no neighbors and dies.

Hints

1. Rules apply simultaneously, so you cannot update a cell before its neighbors have read its old value. A copy of the board makes this trivial; how do you avoid the copy?
2. Each cell only needs to carry two bits of information: its old state and its new state.
3. Encode the transition in the cell itself (for example, use bit 0 for the current state and bit 1 for the next state), then do a second pass shifting every cell right by one.