Simulation

You’ll recognise it when

• The statement reads like a rulebook: “each turn”, “every minute”, “when a machine is free, it takes the next job”.
• You’re asked for the final state (positions, scores, finish times), not an optimum.
• Several things can happen at the same moment, and the statement says (or should say) which goes first.
• The input is small enough that following the rules directly is fast enough, or the time between events is large and you can jump over it.

It’s often confused with a greedy or a scheduling-optimisation problem. In a simulation the rules are given; your job is to follow them exactly, not to choose a better schedule.

The idea

Think of a referee with a stopwatch and a notebook. The referee doesn’t predict the game. They look at the clock, write down everything that happened at that moment, and then apply the rulebook to decide what happens next. When two things happen in the same second, the rulebook says which counts first.

A simulation is that referee in code. Three habits keep it right. Keep one clock and only move it forward. When several things happen at the same moment, handle them in a fixed, stated order, so the run is deterministic. And keep the bookkeeping (applying what just happened) apart from the rules (deciding what to do next), so a rule change touches one block of code.

How it works

A bakery has k ovens, numbered from 0. Orders arrive at given minutes, each needing some minutes of baking. An arriving order joins a first-come, first-served line. Whenever ovens are free and orders are waiting, the lowest-numbered free oven takes the order at the front. If an oven finishes at the same minute an order arrives, the oven counts as free first.

Nothing happens between events, so instead of ticking minute by minute, jump the clock straight to the next event. Keep events in a min-heap ordered by (time, kind, id): kind puts finishes before arrivals, and id breaks the rest of the ties.

1. Seed the heap with one arrival event per order. Every oven is in free, a min-heap of oven ids, and waiting is an empty queue.
2. Jump the clock: now becomes the time of the earliest event.
3. Bookkeeping: pop every event at now. A finish puts its oven back in free; an arrival goes to the back of waiting.
4. Rules: only after the whole minute is applied, pair the lowest free oven with the oldest waiting order, as many times as you can. Each pairing pushes a finish event at now + minutes.
5. Repeat until the heap is empty. Every order has been baked exactly once.

With k = 2 and orders #0 (arrive 0, bake 5), #1 (1, 3), #2 (2, 4), #3 (4, 2), #4 (5, 1):

Why the order of step 3 and step 4 matters: if two ovens finish at the same minute, say 2 and then 0, and you ran the rules after each event, oven 2 would grab the waiting order before oven 0 is back. Applying the whole minute first, then the rules, gives the lowest oven as the statement says. The run is deterministic because every tie is broken by a key you chose, never by heap or hash order.

import heapq
from collections import deque

FINISH, ARRIVE = 0, 1    # at the same minute, ovens free up before orders arrive


def run_bakery(k, orders):
    """orders[i] = (arrive, minutes). Returns (oven, done_at) for each order."""
    events = []                                   # (time, kind, order id), a min-heap
    for i, (arrive, _) in enumerate(orders):
        heapq.heappush(events, (arrive, ARRIVE, i))
    free = list(range(k))                         # free oven ids, a min-heap
    waiting = deque()                             # order ids, first come first served
    result = [None] * len(orders)

    while events:
        now = events[0][0]                        # jump the clock to the next event
        # Bookkeeping: apply everything that happens at this minute.
        while events and events[0][0] == now:
            _, kind, i = heapq.heappop(events)
            if kind == FINISH:
                heapq.heappush(free, result[i][0])
            else:
                waiting.append(i)
        # Rules: lowest free oven takes the oldest waiting order.
        while free and waiting:
            oven, i = heapq.heappop(free), waiting.popleft()
            done = now + orders[i][1]
            result[i] = (oven, done)
            heapq.heappush(events, (done, FINISH, i))
    return result

#include <deque>
#include <functional>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

const int FINISH = 0, ARRIVE = 1;   // at the same minute, ovens free up before orders arrive

// orders[i] = {arrive, minutes}. Returns {oven, done_at} for each order.
vector<pair<int, long long>> run_bakery(int k, const vector<pair<long long, long long>>& orders) {
    using Event = tuple<long long, int, int>;                  // (time, kind, order id)
    priority_queue<Event, vector<Event>, greater<>> events;     // a min-heap
    for (int i = 0; i < (int)orders.size(); i++) events.push({orders[i].first, ARRIVE, i});
    priority_queue<int, vector<int>, greater<>> free;           // free oven ids
    for (int o = 0; o < k; o++) free.push(o);
    deque<int> waiting;                                         // first come first served
    vector<pair<int, long long>> result(orders.size());

    while (!events.empty()) {
        long long now = get<0>(events.top());                  // jump the clock to the next event
        // Bookkeeping: apply everything that happens at this minute.
        while (!events.empty() && get<0>(events.top()) == now) {
            auto [t, kind, i] = events.top();
            events.pop();
            if (kind == FINISH) free.push(result[i].first);
            else waiting.push_back(i);
        }
        // Rules: lowest free oven takes the oldest waiting order.
        while (!free.empty() && !waiting.empty()) {
            int oven = free.top(), i = waiting.front();
            free.pop();
            waiting.pop_front();
            long long done = now + orders[i].second;
            result[i] = {oven, done};
            events.push({done, FINISH, i});
        }
    }
    return result;
}

import java.util.*;

class Bakery {
    static final int FINISH = 0, ARRIVE = 1;   // at the same minute, ovens free up before orders arrive

    // orders[i] = {arrive, minutes}. Returns {oven, done_at} for each order.
    static long[][] runBakery(int k, long[][] orders) {
        // (time, kind, order id), a min-heap
        PriorityQueue<long[]> events = new PriorityQueue<>((a, b) ->
                a[0] != b[0] ? Long.compare(a[0], b[0])
                : a[1] != b[1] ? Long.compare(a[1], b[1]) : Long.compare(a[2], b[2]));
        for (int i = 0; i < orders.length; i++) events.add(new long[]{orders[i][0], ARRIVE, i});
        PriorityQueue<Integer> free = new PriorityQueue<>();       // free oven ids
        for (int o = 0; o < k; o++) free.add(o);
        ArrayDeque<Integer> waiting = new ArrayDeque<>();          // first come first served
        long[][] result = new long[orders.length][];

        while (!events.isEmpty()) {
            long now = events.peek()[0];                           // jump the clock to the next event
            // Bookkeeping: apply everything that happens at this minute.
            while (!events.isEmpty() && events.peek()[0] == now) {
                long[] e = events.poll();
                int i = (int) e[2];
                if (e[1] == FINISH) free.add((int) result[i][0]);
                else waiting.addLast(i);
            }
            // Rules: lowest free oven takes the oldest waiting order.
            while (!free.isEmpty() && !waiting.isEmpty()) {
                int oven = free.poll(), i = waiting.pollFirst();
                long done = now + orders[i][1];
                result[i] = new long[]{oven, done};
                events.add(new long[]{done, FINISH, i});
            }
        }
        return result;
    }
}

Tick by tick: grids, robots and games

When something changes at every step (a robot’s moves, Game of Life, a snake), a plain loop over steps is the clock. Two habits carry over:

• Directions as data. dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)] for north, east, south, west. Turning right is d = (d + 1) % 4, left is (d + 3) % 4, and a move is x += dirs[d][0]. No if chain per direction.
• Read the old state, write a new one. When every cell’s next value depends on its neighbours’ current values, compute the next board into a fresh grid (or encode old and new together in one cell), then swap. Updating in place lets cells see half-updated neighbours.

Why it’s O(n log n)

Each order creates two events, an arrival and a finish. Each event is pushed and popped once, and each oven id is pushed and popped once per order, at O(log n) per heap operation. That’s O(n log n) for n orders, however far apart the minutes are. The heap holds at most n events, so space is O(n + k).

A minute-by-minute loop would cost O(T × k) for a timeline of T minutes, which is fine when T is small and hopeless when times reach a billion. That’s the main reason to jump the clock from event to event.

Common mistakes

heapq.heappush(events, (t, order))         # ✗ ties fall back to comparing orders
heapq.heappush(events, (t, kind, order_id))  # ✓ finishes first, then by id

for e in due_now: apply(e); dispatch()     # ✗ the first event sees half a minute
for e in due_now: apply(e)                 # ✓ the whole minute first
dispatch()

board[r][c] = rule(board, r, c)            # ✗ later cells see new values
nxt[r][c] = rule(board, r, c)              # ✓ read old, write new, then swap

done = now + minutes - 1                   # ✗ the oven looks busy one minute too long
done = now + minutes                       # ✓ busy during [now, done), free at done

Variations

• Huge step counts. When asked for the state after 10^9 steps of a deterministic process, record each state in a dict with the step you first saw it. Once a state repeats, the process cycles, and you can skip whole cycles with modular arithmetic.
• Infinite boards. Store only the live cells in a set and count neighbours with a Counter. The cost then depends on the live cells, not on the board’s size.
• Elevators and controllers. Each call picks a machine by a ranked rule (closest, then idle, then lowest id). Write the rule as a sort key, and you can test it on its own.
• Calendar arithmetic. Days between dates without a library: count days from a fixed origin (whole years, then months, then days, with the leap-year rule), and subtract.
• Rules from text. Formatting and wrapping problems are simulations of a cursor moving along lines: track the current line’s length and decide, word by word, whether it fits.

Climb the ladder

Our simulation problems in ladder order, warm-ups first and multi-part OAs last.

1. Robot on a walled grid: direction arrays and bounds checks.
2. Rain barrel log: the order of operations within one day.
3. Pick the elevator that answers a call: a ranked rule as a sort key.
4. Days between two dates: calendar rules, counted from an origin.
5. Walking Robot Simulation: obstacles in a set, turning as arithmetic.
6. Spiral Matrix: shrinking bounds without double counting.
7. Design Snake Game: a deque body and the tail-moves-first rule.
8. Game of Life: old state versus new state, then an infinite board.

The rest add bigger rulebooks: Tetris drops, bubble boards, an overheating chip, 2048, Connect-N and a labeling scheduler. See all simulation problems.