What it is
Simulation questions describe a process with explicit rules — asteroids colliding, a board evolving generation by generation, a path traced through a grid — and ask you to compute the end state by carrying out those rules faithfully. There's usually no clever formula that shortcuts the work; the challenge is entirely in choosing the right data structure to make each step of the simulation efficient and correct (a stack for "the most recent unresolved thing," careful boundary tracking for a shrinking region) and in handling the process's edge cases (a collision chain, a boundary between regions, in-place updates that must not see already-updated data).
When it applies
- The problem statement is a sequence of rules applied over time or over positions, and the output is whatever remains once the rules stop applying.
- Each step depends only on a small, well-defined piece of prior state (the top of a stack, the four current boundaries, the previous generation's values) rather than on global recomputation.
- There's a natural stopping condition (no more collisions possible, every ring of the grid visited) that bounds the total work.
- If the "rules" instead define a recurrence where the current answer builds directly on best answers to smaller subproblems (not just a mechanical step-by-step process), you're more likely looking at dynamic programming than simulation.
Tells in the problem
- The problem is described as a physical or generational process ("collide", "move", "next generation") rather than as an optimization or a query.
- "Update in place" combined with "simultaneously" — a hint that you must not let an early update in the same pass affect a later one that should have seen the original state.
- A chain reaction where resolving one interaction can trigger another (one collision destroys a asteroid, which changes what the next asteroid meets) — a hint for a stack that represents "everything still unresolved so far."
- A geometric traversal order (spiral, boustrophedon) described precisely enough that the real task is bookkeeping which cells remain, not deciding which to visit.
- Small stated bounds (a few dozen rows and columns) that hint the intended solution is direct simulation, not an asymptotic optimization.
The classic mistake
Writing a new value into a cell or list, then later in the same pass reading that written value as if it were the untouched original, lets the simulation see its own in-progress output as if it were still the original input — the mistake that shows up most. This is easy to miss because a normal, in-order loop looks correct at first glance; the bug only shows up on inputs where an early write actually gets revisited before the pass finishes (adjacent cells in a "simultaneous" update, a chain of three or more collisions in one direction). The habit that catches it: before writing the loop, ask "could a later step in this same pass observe a value I already changed, when the rules say it should see the original?" — if yes, either snapshot the original state first, encode "new" values in a way distinguishable from "old" ones, or process in an order where the hazard can't occur.
Questions to start with
- Spiral Matrix — pure bookkeeping simulation: track four shrinking boundaries and know precisely when to stop.
- Game of Life — the sharpest version of the in-place hazard: every cell's next state depends on neighbors that must still show their original values.
- Asteroid Collision — introduces the chain-reaction structure, where a stack tracks everything still unresolved as new elements arrive.