Careful state simulation

42 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Conway's Game of Life is a grid of cells, each alive or dead. One generation later, each cell is decided by its eight neighbours in the old grid: a live cell with two or three live neighbours stays alive, otherwise it dies; a dead cell with exactly three live neighbours is born. Take a 4 × 3 board and work out the next generation by hand. You count neighbours for the first cell, write down its fate, move to the second cell, and somewhere around the third cell the mistake creeps in: you look at a neighbour you already updated, and count its new state instead of its old one. The rules are simple; the discipline is the hard part.

Simulation problems are all like this. There is no clever algorithm to discover. The marks go to modelling the rules exactly, keeping the smallest state that decides the next step, and updating in an order that never reads a value that has already changed.

Build the structure, one piece at a time

Piece one: the state. For Life the state is the grid itself; nothing else is needed, because the rules look only at the current grid.

Piece two: the update rule as a function of the old state only. Count live neighbours of cell (r, c) by looking at the up-to-eight cells around it, skipping any outside the board. Then apply the three rules. On the example, cell (1,1) is alive with three live neighbours, so it stays alive; (0,0) is dead with three live neighbours, so it is born; (1,3) is alive with no live neighbours, so it dies.

Piece three: an order that keeps old and new apart. The safe version writes every result into a second grid and swaps at the end. The in-place version, which interviewers ask for, encodes both states in one cell: 0 dead-to-dead, 1 alive-to-alive, 2 alive-to-dead, 3 dead-to-alive. While scanning, a cell's old state is "value is 1 or 2" and neighbours are counted that way; after the scan, one pass maps 2 to 0 and 3 to 1:

The same three pieces fit every simulation: a robot on a grid needs its position and facing direction; a queue at a door needs who is waiting, which way they want to go, and who went last; text justification needs the words of the current line and the spaces still to distribute.

Why it is correct

The invariant is that the modelled state, together with the rules, is enough to decide the next step. For Life, the next grid is by definition a function of the current grid alone, so the state is complete. The in-place encoding is correct because the "was" information is never destroyed during the scan: a cell with code 2 is still read as alive by its neighbours, and a cell with code 3 is still read as dead. Only after every cell has been decided does the second pass collapse the codes, and by then no cell needs the old values any more.

The general rule is: never read a value that has already been updated in the same step, unless the rules say the update happens in sequence. Some simulations are genuinely sequential, such as people passing through a door one per second; then the order is part of the rules and must be followed exactly, not avoided.

Why it is fast

Each generation visits every cell once and looks at at most eight neighbours, so it costs O(m · n) with a constant of about 8. There is no faster way in general: every cell's fate can change, so every cell must be computed. The in-place encoding keeps the memory at the grid itself, O(1) extra, against a second grid of O(m · n). Most simulation problems are O(steps × state size) and the whole skill is in not wasting the constant and not getting the order wrong.

How to recognise it in an interview

Cues: "apply these rules", "one generation", "simulate", "each second", "in place", a long statement with many special cases and no obvious trick. Say: "this is a simulation; I will define the state precisely, write the update as a function of the old state, and pick an order that never reads an already-updated value".

Game of Life is the walk-through above with the two-bit encoding. Time Taken to Cross the Door is sequential: at each second, the rule about who goes first depends on who used the door in the previous second, so the state must include the last direction and the last used time. Text Justification is a careful simulation of a typesetter: fill a line greedily, then distribute the leftover spaces from the left, with the last line left-aligned.

02The idea in one line

Model the rules exactly; keep the state minimal and update it in order.

Reach for it when: Game of life, spiral, robot bounded, text justification, time to cross the door.

Cost: O(steps · state) time.

03The walk-through, step by step

The video works one example: Game of Life one generation on a 4×3 board. These are its captions in order, so you can follow without the video or check a step you missed.

1. Every cell looks at its 8 neighbours in the old board, never the new one
2. (1,1) is alive with 3 live neighbours: stays alive
3. (0,0) is dead with 3 live neighbours: is born
4. (1,3) is alive with 0 live neighbours: dies
5. (0,1) is alive with 2 live neighbours: stays alive
6. (2,1) is alive with 2 live neighbours: stays alive
7. (1,0) is alive with 3 live neighbours: stays alive
8. The remaining cells follow the same rule
9. Only now does the new board replace the old one
10. In-place trick: encode old+new in one cell (e.g. 2 = was alive, now dead)
11. O(m·n) per generation; model the rules exactly, update in order

04Asked at Google

10 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Simulation: none in this topic.