Simulation & Enumeration

Sometimes there’s no trick

A whole class of problems just asks you to follow the rules: move a robot, run a Game of Life step, walk a spiral, apply a list of operations, parse and execute. The challenge is correctness and clean state-handling, not cleverness. These reward readable code with the state changed in one place.

Grid movement with direction vectors

Replace four ifs with a list of offsets; index into it to turn:

DIRS = [(0, 1), (1, 0), (0, -1), (-1, 0)]    # E, S, W, N
d = 0                                         # facing index
# turn right: d = (d + 1) % 4 ; turn left: d = (d - 1) % 4
r, c = r + DIRS[d][0], c + DIRS[d][1]         # step forward

This cleanly handles “spiral matrix,” “robot bounded in a circle,” “walking robot simulation,” “snake game.” For 8-directional moves, list all eight offsets.

Snapshot vs in-place updates (the classic bug)

When every cell updates from the previous state simultaneously (Game of Life, cellular automata), reading already-updated neighbors corrupts the step. Two fixes:

• Copy first — compute into a fresh grid (simple, O(n) extra space).
• Encode both states in one cell — e.g. use bit flags (next << 1 | cur) so the old state is still readable while you write the new one, then shift down. O(1) space, the “in-place Game of Life” trick.

State machines

“Valid number,” “string to integer (atoi),” “robot/parser” problems are cleanest as an explicit state machine: enumerate states, define transitions per input class, and step through. It turns a thicket of conditionals into a table you can verify.

Centralize the fiddly bits

• One bounds/visited helper (in_grid(r, c)) instead of scattered checks.
• Modular arithmetic for cyclic motion / wrap-around (pos = (pos + step) % n).
• Name the state explicitly (position, direction, score) and mutate it in one place.

Enumeration (bounded brute force)

When the search space is small, just try everything and keep the best — all pairs, all start points, all subsets. Bound the work first from the constraints:

• n ≤ ~10–12 → permutations / O(n!) may be fine.
• n ≤ ~20 → subset enumeration via bitmasks (see the bit-manipulation primer).
• small grids → brute force over cells/paths.

If enumeration is exponential and overlaps, lift it to backtracking (with pruning) or DP (see those primers). Stating “n ≤ 20, so 2ⁿ enumeration is ~10⁶ — fine” is exactly the reasoning interviewers want.

Pitfalls

• Reading updated state mid-step (snapshot or encode both states).
• Off-by-one at boundaries — test the first step, the last step, and wrap-around explicitly.
• Mutating the input when the caller needs it preserved.
• Over-engineering — if the constraints are tiny, clean brute force beats a clever algorithm you might get wrong.

Choosing in an interview

• “Follow these rules / steps” → simulate, with direction vectors and one state-update site.
• Simultaneous-update grid → snapshot or encode two states.
• Parser/validator → state machine.
• Small constraints, “find any/best arrangement” → bounded enumeration (→ backtracking/DP if it blows up).

The win condition is provably-correct, readable code: name the state, change it in one place, and test the edge steps.