How to design an elevator system

An elevator design splits cleanly in two: an easy object model, and the scheduler where the design actually lives.

Two decisions, two objects

• Hall call HallCall(floor, direction): request from outside a car, wanting to travel a direction.
• Car call CarCall(floor): request from inside a car, direction implied by where the car is.
• Which car answers a hall call = Dispatcher’s job (a policy, changes).
• What order one car serves its calls = ElevatorCar’s job (an algorithm, LOOK, does not change).
• Keep those two decisions in separate objects. That split is the whole design.

Core objects

• No Floor class: a floor is an int plus two lit-button booleans. Adding it later touches one file.

LOOK vs the naive rules

• FCFS (first-come first-served): serve in press order. Slow, doubles back, but starves no one.
• LOOK: sweep one direction to the furthest pending call, serving everything on the path, then reverse. Looks ahead before reversing. (SCAN runs to the physical top/bottom every time, wasting the empty end.)
• SSTF / nearest-first: greedy, and it starves — lobby traffic at 2,3,4 keeps overtaking a call at 20 forever.
• Sample burst, car at floor 1, calls 15↓ 3↑ 18↑ 6↑ 11↓:
  • FCFS 1→15→3→18→6→11 = 58 floors
  • LOOK 1→3→6→18→15→11 = 24 floors (up-sweep 17 + down-sweep 7), 59% less.

Numbers that matter

• FCFS cost/request (random floors, n=20): (n²−1)/(3n) ≈ 6.65 floors, flat forever.
• Full LOOK sweep: 2(n−1) = 38 floors, serves all m pending → 38/m per request.
• Break-even ≈ 38/6.65 ≈ 6 concurrent requests; above that LOOK wins and keeps falling.
• LOOK worst-case wait is bounded at one sweep = 38 floors → no starvation.

The one detail the bound rests on

• The one-sweep bound holds only if the sweep’s target is frozen when the sweep begins (sweep_target, set once by _begin_sweep, cleared only by arrive).
• Recompute the furthest pending stop every step and a steady stream of same-direction calls extends the sweep forever — the far end starves like SSTF.
• The 500-tick assertion turns that bound from a claim into a test.
• LOOK’s one bad case: a single call one floor behind an idle car waits for the turn. Real controllers cheat: idle + empty queue → take the nearest call and start the sweep there.

Patterns and fixed vs variable bets

• Strategy (dispatch): DispatchStrategy.choose(cars, call). NearestCarStrategy (min distance), LookCostStrategy (min added sweep ≈ distance + penalty × queued), FairnessStrategy (min max-wait).
• Command (requests as objects): buys audit log + deterministic replay; costs an allocation per press vs an int bitmask.
• State (car): IDLE → MOVING → DOORS_OPEN; described, not implemented — code is a scheduler, not a door controller.
• Variable → interface/param: which car answers, which floors a car serves (can_serve), availability (in_service), car/floor counts, objective.
• Fixed → baked in: per-car LOOK (hard-coded, not swappable), one authoritative dispatcher, one car per call never reassigned, plan is a set of floors not a timed schedule, integer positions, one shaft per car.

Gotchas

• Two request types, not one Request with Optional[direction] and a None check everywhere.
• peek_next_stop is pure; advance_to_next_stop mutates (flips heading, freezes target). A dispatcher scoring a car must peek, not advance.
• Car heading ≠ hall-call direction: a car at 10 answering HallCall(5, UP) heads DOWN first, then sweeps up.
• Don’t model Floor, don’t make Dispatcher a Singleton (one-per-building is deployment, not language), don’t make door timing a Strategy.
• Fairness aging must weight the car by its oldest waiting call, not subtract the call’s age from every score (a constant can’t change the argmin).
• A flat state set can’t express fire recall (it preempts every state); needs a hierarchical machine or a mode flag.