Simulation

Tactic

Simulation executes the rules of a process directly while keeping state explicit. The tactic is to model exactly what changes after each event or step.

The invariant is faithful state. At the top of each loop, the variables represent the real process after all previous events have been applied.

Good simulation code names the state and transitions clearly. If many branches appear, convert them into small helper functions or a table of directions, operations, or cases.

Value

The value is correctness under detailed rules. Some problems have no hidden trick. They need careful state updates, boundary checks, and termination conditions.

Direct complexity example

Brute force: Recompute the whole world after every event: $O(tn)$ or worse for t events and state size n.
With this tactic: Maintain only the changing state and update it per event: often $O(t)$ or $O(t \log n)$ depending on the needed data structure.
Space: Space is the explicit state representation, often $O(1)$ for counters or $O(n)$ for boards, stacks, maps, or queues.

Challenges this solves

spiral matrix
asteroid collision
string multiplication
plus one
LRU operations
game-like rule execution

When to use it

Use this tactic when these conditions are true:

the prompt gives concrete rules to execute
edge cases are about state transitions
the output is the final state after operations
no stronger invariant simplifies the process

When not to use it

Reach for a different tactic when these warning signs appear:

the state space repeats and needs cycle detection
the rules can be summarized by math or greedy logic
recomputing after each event is too slow and needs a data structure
the problem asks for an optimum rather than rule execution

Terminology clues

These prompt words often point toward this concept:

simulate
process
operations
after each
state
rules
collision
move