127. Game of Life Step

Why this mechanism works

Sequentially overwriting old values would change later neighbor counts. Store old and new state in separate bits of each cell: bit zero is the original value, bit one is the next generation. Every neighbor read masks the old bit, and a final pass shifts the new bit into place.

State and boundaries

cell & 1 always gives original state during discovery. cell's second bit records the independently computed next state.

Protocol

1. For each cell count eight-neighbor old bits.
2. Set bit one if the survival or birth rule holds.
3. After all cells are evaluated, shift every cell right by one.

Visualization

encoding old -> new:
0: dead->dead   1: live->dead
2: dead->live   3: live->live
final shift keeps the new bit

Python implementation

def game_of_life(board):
    rows = len(board)
    cols = len(board[0]) if rows else 0
    for r in range(rows):
        for c in range(cols):
            neighbors = 0
            for dr in (-1, 0, 1):
                for dc in (-1, 0, 1):
                    nr, nc = r + dr, c + dc
                    if (dr or dc) and 0 <= nr < rows and 0 <= nc < cols:
                        neighbors += board[nr][nc] & 1
            old = board[r][c] & 1
            if neighbors == 3 or (old == 1 and neighbors == 2):
                board[r][c] |= 2
    for r in range(rows):
        for c in range(cols):
            board[r][c] >>= 1
    return board

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 game_of_life: rows = len(board)
board=[[0, 1, 0], [0, 1, 0], [0, 1, 0]]; rows=3

L3 game_of_life: cols = len(board[0]) if rows else 0
board=[[0, 1, 0], [0, 1, 0], [0, 1, 0]]; rows=3; cols=3

L4 game_of_life: for r in range(rows):
board=[[0, 1, 0], [0, 1, 0], [0, 1, 0]]; rows=3; cols=3; r=0

L5 game_of_life: for c in range(cols):
board=[[0, 1, 0], [0, 1, 0], [0, 1, 0]]; rows=3; cols=3; r=0; c=0

L6 game_of_life: neighbors = 0
board=[[0, 1, 0], [0, 1, 0], [0, 1, 0]]; rows=3; cols=3; r=0; c=0; neighbors=0

L7 game_of_life: for dr in (-1, 0, 1):
board=[[0, 1, 0], [0, 1, 0], [0, 1, 0]]; rows=3; cols=3; r=0; c=0; neighbors=0; dr=-1

L8 game_of_life: for dc in (-1, 0, 1):
board=[[0, 1, 0], [0, 1, 0], [0, 1, 0]]; rows=3; cols=3; r=0; c=0; neighbors=0; dr=-1; dc=-1

L9 game_of_life: nr, nc = r + dr, c + dc
board=[[0, 1, 0], [0, 1, 0], [0, 1, 0]]; rows=3; cols=3; r=0; c=0; neighbors=0; dr=-1; dc=-1; nr=-1; nc=-1

... 245 intermediate state changes omitted ...

L16 game_of_life: for c in range(cols):
board=[[0, 0, 0], [1, 1, 1], [0, 1, 0]]; rows=3; cols=3; r=2; c=0; neighbors=2; dr=1; dc=1; nr=3; nc=3; old=0

L16 game_of_life: for c in range(cols):
board=[[0, 0, 0], [1, 1, 1], [0, 1, 0]]; rows=3; cols=3; r=2; c=1; neighbors=2; dr=1; dc=1; nr=3; nc=3; old=0

L17 game_of_life: board[r][c] >>= 1
board=[[0, 0, 0], [1, 1, 1], [0, 0, 0]]; rows=3; cols=3; r=2; c=1; neighbors=2; dr=1; dc=1; nr=3; nc=3; old=0

L16 game_of_life: for c in range(cols):
board=[[0, 0, 0], [1, 1, 1], [0, 0, 0]]; rows=3; cols=3; r=2; c=2; neighbors=2; dr=1; dc=1; nr=3; nc=3; old=0

L2 game_of_life: rows = len(board)
board=[[1, 1], [1, 1]]; rows=2

L3 game_of_life: cols = len(board[0]) if rows else 0
board=[[1, 1], [1, 1]]; rows=2; cols=2

L4 game_of_life: for r in range(rows):
board=[[1, 1], [1, 1]]; rows=2; cols=2; r=0

L5 game_of_life: for c in range(cols):
board=[[1, 1], [1, 1]]; rows=2; cols=2; r=0; c=0

L6 game_of_life: neighbors = 0
board=[[1, 1], [1, 1]]; rows=2; cols=2; r=0; c=0; neighbors=0

L7 game_of_life: for dr in (-1, 0, 1):
board=[[1, 1], [1, 1]]; rows=2; cols=2; r=0; c=0; neighbors=0; dr=-1

L8 game_of_life: for dc in (-1, 0, 1):
board=[[1, 1], [1, 1]]; rows=2; cols=2; r=0; c=0; neighbors=0; dr=-1; dc=-1

L9 game_of_life: nr, nc = r + dr, c + dc
board=[[1, 1], [1, 1]]; rows=2; cols=2; r=0; c=0; neighbors=0; dr=-1; dc=-1; nr=-1; nc=-1

... 111 intermediate state changes omitted ...

L16 game_of_life: for c in range(cols):
board=[[1, 1], [3, 3]]; rows=2; cols=2; r=1; c=0; neighbors=3; dr=1; dc=1; nr=2; nc=2; old=1

L17 game_of_life: board[r][c] >>= 1
board=[[1, 1], [1, 3]]; rows=2; cols=2; r=1; c=0; neighbors=3; dr=1; dc=1; nr=2; nc=2; old=1

L16 game_of_life: for c in range(cols):
board=[[1, 1], [1, 3]]; rows=2; cols=2; r=1; c=1; neighbors=3; dr=1; dc=1; nr=2; nc=2; old=1

L17 game_of_life: board[r][c] >>= 1
board=[[1, 1], [1, 1]]; rows=2; cols=2; r=1; c=1; neighbors=3; dr=1; dc=1; nr=2; nc=2; old=1

Why the solution is correct

All transition decisions read only original low bits, so they match a simultaneous update. Writing a high bit cannot affect another cell's old-state count. The final shift exposes exactly the next state that was independently recorded for each cell.

Time and space

O(rows*cols) time and O(1) auxiliary space.

Common mistakes

Reading the whole encoded cell counts future state as current state. Using only four neighbors implements a different cellular rule.

Reasoning card

Transfer exercise

Implement a copy-based generation and verify two blinker steps restore the initial board.