Game of Life

Given a 2D grid of 0s and 1s representing dead/live cells, update the board in-place to the next state according to Conway's Game of Life rules.

Rules for each cell (based on 8 neighbors):

• Live cell with <2 live neighbors dies.
• Live cell with 2 or 3 live neighbors lives.
• Live cell with >3 live neighbors dies.
• Dead cell with exactly 3 live neighbors becomes alive.

Why this is worth learning

This is a synchronous update. Two bits in each cell let old state and next state coexist until every next-state decision is complete.

Before coding: one-minute experiment

For the 3-by-3 board with only the middle row live, what is the next board?

Function signature

func GameOfLife(board [][]int)

Inputs / outputs

• board: 2D grid of 0/1 values.
• Return: nothing; modify board in-place.

Example

board = [
  [0,1,0],
  [0,0,1],
  [1,1,1],
  [0,0,0]
]

Constraints

• 0 <= m, n <= 1000; the board is rectangular.
• Every original value is 0 or 1. Cells outside the finite board are dead; there is no wrapping.

Core idea (near-solution)

Store two times in each integer: bit 0 is old state; bit 1 is next state.

Read every old state with value & 1. Set value |= 2 exactly when the next state should be live. After every cell has been decided, shift all cells right once.

Invariant: throughout pass one, every low bit still equals its original board value. Setting the high bit cannot change any later neighbor count.

Algorithm (step-by-step)

1. If the board has no rows or no columns, return.
2. For each cell, count the original live states of its in-bounds eight neighbors using board[nr][nc] & 1. Exclude the center.
3. Read this cell's old state with board[r][c] & 1. Its next state is live when the count is 3, or when it was live and the count is 2. In those cases set bit 1 with |= 2; otherwise leave that bit zero.
4. Only after completing the entire first pass, replace every cell by cell >> 1.

Correctness sketch

During the first pass, bit 0 of every cell remains its original state. Setting bit 1 for a future live cell cannot change any neighbor count because all neighbor reads mask with &1. Thus each next-state bit is calculated from exactly the original eight-neighbor configuration and the stated birth/survival rules. Once all cells have next-state bits, shifting right discards the old bit and installs the computed new state. The original board contains only 0 or 1, so no unrelated higher bits remain. Every cell consequently receives the same value as an independent two-board synchronous simulation.

Trace (hand walkthrough)

Original:       After encoding:    After shifting:
[0,1,0]         [0,1,0]            [0,0,0]
[0,0,1]         [2,0,3]            [1,0,1]
[1,1,1]         [1,3,3]            [0,1,1]
[0,0,0]         [0,2,0]            [0,1,0]

• Cell (0,1) was live and has one live neighbor, (1,2): it dies, encoded as 1.
• Cell (1,0) was dead and has three live neighbors, (0,1), (2,0), (2,1): it is born, encoded as 2.
• Cell (1,2) was live and has three live neighbors: it survives, encoded as 3.
• Later cells still read the low bits of these encoded values. A newly born 2 contributes zero to the old live-neighbor count.

Pitfalls to avoid

• Counting neighbors using the updated state instead of original.
• Forgetting the second pass.

Debugging lens

Compare against a copied-board oracle. Read neighbors with cell&1, not cell==1, because an encoded live-to-live cell has value 3. Count all eight neighbors but never the center.

Complexity

• Time: O(m*n)
• Extra space: O(1)

Implementation notes (Go)

• Encode old/new state with bits (bit0 old, bit1 new).
• Count neighbors with cell & 1, then shift right to finalize.

Reconstruction checkpoint

For the 3-by-3 board with only the middle row live, what is the next board?

Return to Matrix · Module quiz