Meridian Tower: Elevator Bank Dispatch and Replay

Meridian Tower: Elevator Bank Dispatch and Replay

Meridian Tower has 20 floors (the lobby is floor 1) and a bank of three cars, A, B and C. Building engineering keeps a discrete-time model of the bank, and replays recorded traffic through it before any controller change reaches the building. You have just joined the team that owns that model. It has two open defects from tenant complaints, and behind them sit four roadmap items: a service report for the facilities contract, taking a car out for maintenance, the new destination-dispatch kiosks (with express cars that only serve some floors), and a replay of a whole day of traffic that is currently far too slow to run in CI.

Codebase

config.py, dispatch.py, models.py, errors.py and traffic.py are known-good: the cost arithmetic and the generator are product decisions, not bugs. The defects and all the new work are in car.py, bank.py, stats.py and api.py.

The model

Time

Time is a whole number of ticks. The bank's clock starts at 0 and counts the ticks simulated so far. One step simulates one tick, from clock to clock + 1, in this order:

1. Dispatch. Every lit hall call that has no car yet is given one (see Hall calls).
2. Cars act, in car id order A, B, C (see What a car does).
3. The clock becomes clock + 1.

Every event that happens in a step is stamped with the new clock value: a rider who boards in the step from clock 9 to 10 has boarded_at = 10. Passengers and operations arrive *between* steps, so a rider who arrives at clock t is first seen by the step t -> t + 1 and has arrived_at = t.

An operation [name, ts, ...] takes effect at max(ts, clock): the bank first runs steps until the clock reaches ts (if it is already there or past it, nothing runs), then performs the operation. A settle can push the clock past later ts values; those operations simply take effect at the current clock. This happens for every operation with a known name, a valid ts and the right number of arguments, even if the operation then fails.

The building

Floors 1 to 20. Each car starts on floor 1, idle, doors closed, empty. A car carries at most 8 riders. Hall calls, riders and cars are all deterministic: anywhere an order is not stated, it is by car id, then by rider arrival order.

Riders and hall calls

arrive puts a rider on their origin floor. Their direction is up if dest > origin, else down. They wait until they board a car whose doors open on their floor while the car is leaving in their direction.

In hall mode (the default), the hall button lights once per (floor, direction) pair, however many riders wait there. A lit call has a sequence number (1, 2, 3, ...), given in the order calls are lit, and a car (or none yet).

• Dispatch. At the start of every step, each lit call with no car, in sequence order, goes to the in-service car with the lowest dispatch.hall_cost; equal costs go to the lowest car id. Calls assigned earlier in the same pass count towards a car's cost. The call joins that car's pickups (the set of (floor, direction) pairs it must answer).
• Boarding takes anyone. When a car opens its doors at floor f leaving in direction d, *every* rider waiting at (f, d) may board, in arrival order, until the car holds 8, whichever car the call was assigned to. Afterwards the call at (f, d) is cleared and removed from whichever car held it.
• Riders left behind (the car filled up) press the button again: a new call is lit at once for (f, d) with a fresh sequence number and no car, and is dispatched at the next step (to any car, including this one).

What a car does each tick

A car that is not in the middle of a stop works from its stops (the destinations of the riders aboard plus the floors of its pickups) and its here set (the directions of its pickups at its current floor):

1. Direction. Try the car's current direction first, then the opposite one (an idle car tries up first, then down). A direction is chosen if some stop lies *strictly beyond* the car's floor in that direction, or the car has a pickup here in that direction. If neither qualifies the car is idle.
2. Stop or move. The car opens its doors if a rider's destination is its floor, or if its direction is not idle and it has a pickup here in that direction. Otherwise it moves one floor in its direction (or does nothing if idle). A pickup in the *other* direction is skipped while the car still has work ahead.
3. Full cars. A car carrying 8 riders ignores its pickups in steps 1 and 2 (it cannot take anyone on). They stay assigned to it and count again as soon as it has room.

Opening the doors does these things, in this order: every rider whose destination is this floor gets off (delivered_at); the car's direction becomes the direction chosen in step 1 (possibly idle); if the car is in service and its direction is not idle, riders waiting here for that direction board; the car's stop starts. A stop lasts 3 ticks: the tick the doors open, then two ticks in which the car only counts down. After those, the car decides again. cars reports the doors as "open" while the countdown is still above zero (after the opening tick and after the next one) and "closed" otherwise.

Operations

Every operation is [name, ts, ...args] with ts an integer >= 0, and returns exactly one value. Errors are *returned* as "error: <code>" strings, never raised. An unknown name returns "error: unknown operation"; an operation that is not a list, has a bad ts (not an integer, a boolean, negative) or the wrong number of arguments returns "error: invalid arguments".

• arrive: pid is a non-empty string and origin and dest are integers (booleans are not integers), otherwise invalid arguments. Floors outside 1..20 are invalid floor; origin == dest is same floor; an id that was ever used (even by a delivered rider) is passenger exists.
• settle runs steps until nobody is waiting or riding, then returns the clock (immediately, if nobody is). It fails with stalled right after the first step in which every car both started and ended at rest (direction idle, countdown at zero) while someone is still waiting or riding, because then nothing can ever change. The clock stays where that step left it, and nothing is undone.
• cars: dir is "up", "down" or "idle", load the number of riders aboard, doors "open" or "closed".
• passenger: status is "waiting", "riding" or "delivered". car is null while the rider waits in hall mode, and the car's id from boarding on. boarded_at and delivered_at are null until they happen.

Worked example (one rider). cars start on floor 1.

[["arrive", 0, "P1", 3, 7],
 ["settle", 0],
 ["passenger", 0, "P1"],
 ["cars", 0]]

returns

[true, 10, {"status": "delivered", "car": "A", "boarded_at": 3, "delivered_at": 10},
 [["A", 7, "idle", 0, "open"], ["B", 1, "idle", 0, "closed"], ["C", 1, "idle", 0, "closed"]]]

At step 1 the call at (3, up) goes to A (all three cars cost the same; lowest id) and A moves up. It reaches floor 3 at step 2, opens at step 3 (boarded_at = 3), counts down at steps 4 and 5, climbs floors 4 to 7 in steps 6 to 9, and opens at step 10, when P1 gets off. settle returns as soon as P1 is delivered, so A is still counting down its stop.

Part 1: Fix the incident tickets (ELV-212, ELV-219)

Goal: the bank behaves exactly as described in *The model*. Two defects are open:

• ELV-212 "Nobody answered my call from the 2nd floor. The car sat in the lobby with the doors closed." Calls and rider destinations that are very close to a car are sometimes ignored, and the rider is never served. settle reports stalled.
• ELV-219 "At the top of its run the car stops, opens, and then opens again before it lets the next person in." Riders who should board at a turnaround wait an extra stop.

Do not change the model to match the code: the model above is the contract, and tests/ shows what the team already checks. Rules for the dispatcher cost and the boarding rules are as written.

Example (turnaround). Two riders, one going up from the lobby and one going down from floor 10:

[["arrive", 0, "P1", 1, 10],
 ["arrive", 0, "P2", 10, 1],
 ["settle", 0],
 ["passenger", 0, "P1"],
 ["passenger", 0, "P2"],
 ["cars", 0]]

returns

[true, true, 22,
 {"status": "delivered", "car": "A", "boarded_at": 1, "delivered_at": 13},
 {"status": "delivered", "car": "B", "boarded_at": 10, "delivered_at": 22},
 [["A", 10, "idle", 0, "closed"], ["B", 1, "idle", 0, "open"], ["C", 1, "idle", 0, "closed"]]]

A takes the lobby call, and B (cheaper than A for the call at 10) takes the down call. B arrives at floor 10 going up with nothing ahead, turns to go down, and the rider waiting for "down" boards in the same stop (step 10).

For comparison, the same four riders in hall mode: ["arrive", 0, "q1", 1, 10], q2 to 12, q3 to 14 and q4 to 12, all at the lobby at tick 0. They all share one hall call, so A takes all four, boarding at step 1, and delivers them at 13, 18, 23 and 18; settle returns 23.

Part 2: Service report and out-of-service cars (ELV-240, ELV-247)

Facilities wants numbers for the service contract, and maintenance needs to take a car out for the night without stranding anyone.

stats

Returns this object, about riders delivered so far (a rider still waiting or riding contributes nothing):

{"delivered": 3, "rejected": 0, "total_wait": 9, "total_ride": 40,
 "max_wait": 4, "p90_wait": 4, "by_car": {"A": 2, "B": 1, "C": 0}}

• A rider's wait is boarded_at - arrived_at, measured from when they first arrived, however many times they were left behind. Their ride is delivered_at - boarded_at.
• total_wait and total_ride are sums; max_wait is the largest wait; p90_wait is the nearest-rank 90th percentile of the waits: sort the waits ascending and take the one at 1-based rank ceil(0.9 * delivered) (for 10 deliveries rank 9; for 11, rank 10). max_wait and p90_wait are null when nothing has been delivered.
• by_car counts deliveries per car, with every car present, in car id order. rejected counts riders the building refused or gave up on (Part 3); it is 0 until then.

out_of_service and restore

• car must be a car id (unknown car otherwise, including non-strings). out_of_service on a car that is already out fails with already out of service; restore on a car that is in service fails with not out of service.
• An out-of-service car is no longer a candidate for dispatch. The hall calls assigned to it are released, keeping their sequence numbers, and are dispatched at the next step together with any other unassigned calls, oldest first. If no car is in service they stay unassigned (riders keep waiting).
• The car keeps serving the riders already aboard: it moves and stops exactly as before, and riders get off at their floors. But it takes nobody new: when its doors open nobody boards, so a rider waiting at that floor stays put (their call is not cleared).
• restore puts the car back in service where it stands. It does not take any call back.

Example. Rider P1 goes from 5 to 8. Car A is taken out of service one tick after the call was lit; B takes over.

[["arrive", 0, "P1", 5, 8],
 ["out_of_service", 1, "A"],
 ["settle", 1],
 ["passenger", 1, "P1"],
 ["stats", 1]]

returns

[true, true, 12, {"status": "delivered", "car": "B", "boarded_at": 6, "delivered_at": 12},
 {"delivered": 1, "rejected": 0, "total_wait": 6, "total_ride": 6, "max_wait": 6, "p90_wait": 6,
  "by_car": {"A": 0, "B": 1, "C": 0}}]

Step 1 gives the call to A, which starts up. After the operation at tick 1 the call is released; in step 2 it goes to B (B and C cost the same, lowest id), which needs steps 2 to 5 to reach floor 5 and boards at step 6.

Part 3: Destination dispatch and zoned cars (ELV-260)

The lobby is getting destination kiosks: riders enter their floor *before* boarding, and the system promises each of them a car on the spot. That replaces the hall-call model, so a bank can now run in one of two modes.

Modes

• set_mode mode with "hall" (the default, everything above) or "destination". Anything else is invalid mode. The bank must be empty to change anything: if any rider is waiting or riding, or any scheduled traffic (Part 4) has not arrived yet, the result is busy. Setting the current mode again on an empty bank is fine. Checks happen in that order.
• In hall mode nothing changes from Parts 1 and 2.

Destination mode

• Assignment at arrival. arrive validates exactly as before (invalid arguments, invalid floor, same floor, passenger exists). It then picks a car right away among the cars that are in service and serve both the origin and the destination floor (see zones below). If there is none, the result is no service, no rider is created (the id stays free), and the bank's rejected count goes up by one. Otherwise the rider is promised to the cheapest car by dispatch.destination_cost (lowest cost, ties to the lowest id, using the state of the bank at that moment, including promises made earlier). passenger reports the promised car while the rider waits.
• No hall calls. Nothing is lit and the dispatch step of a tick does nothing. A car's pickups are the (floor, direction) pairs of the riders promised to it who are still waiting, so it moves and stops by the same rules as before.
• Boarding takes only your own riders. When a car opens its doors leaving in direction d at floor f, the riders promised to *that car* waiting at (f, d) board, in arrival order, until it holds 8. Riders who do not fit stay promised to the same car (there is no re-press and no re-assignment); their pickup stays with the car, which picks them up when it next has room and passes their floor in their direction.
• Out of service. out_of_service releases the car's promised riders at once and re-picks a car for each, in arrival order, with the same rule as at arrival (the car just taken out is no longer a candidate). A rider with no candidate is given up on: their status becomes "rejected", their car becomes null, and rejected goes up by one. Riders already aboard are unaffected.
• stats, cars, settle and the rest work as before. by_car counts deliveries.

Zones: set_floors car floors

An express car can be restricted to certain floors, e.g. the lobby plus the upper floors.

• Only valid in destination mode, otherwise wrong mode. Checks happen in this order: a floors that is not a list is invalid arguments; hall mode is wrong mode; an unknown car is unknown car; then floors must be a non-empty list of distinct integers in 1..20 (booleans are not integers) or the result is invalid floors; finally the bank must be empty (busy, as for set_mode).
• The car then serves only those floors for assignment: it is a candidate for a rider only if it serves both origin and destination. It still travels past the floors it does not serve. The lobby is not special: a car whose floors omit it never gets lobby riders.
• A new set_floors for the same car replaces the previous list. By default every car serves every floor. Zones are remembered when the bank returns to hall mode, but hall mode ignores them completely.

Example. The same four lobby riders, in destination mode (compare the hall-mode figures in Part 1):

[["set_mode", 0, "destination"],
 ["arrive", 0, "p1", 1, 10], ["arrive", 0, "p2", 1, 12],
 ["arrive", 0, "p3", 1, 14], ["arrive", 0, "p4", 1, 12],
 ["passenger", 0, "p4"],
 ["settle", 0],
 ["passenger", 0, "p1"], ["passenger", 0, "p2"], ["passenger", 0, "p3"], ["passenger", 0, "p4"]]

returns

[true, true, true, true, true,
 {"status": "waiting", "car": "B", "boarded_at": null, "delivered_at": null},
 17,
 {"status": "delivered", "car": "A", "boarded_at": 1, "delivered_at": 13},
 {"status": "delivered", "car": "B", "boarded_at": 1, "delivered_at": 15},
 {"status": "delivered", "car": "C", "boarded_at": 1, "delivered_at": 17},
 {"status": "delivered", "car": "B", "boarded_at": 1, "delivered_at": 15}]

p1, p2 and p3 each go to an empty car (an empty car costs 0, and an empty car beats one that has a promise), but p4 shares floor 12 with p2, so B is cheaper for it than A or C.

Part 4: Replaying the day (ELV-281)

Recorded days are too big to type as operations, so the replay tool describes traffic compactly and the bank must run a full day fast.

traffic prefix seed count span schedules count riders (1 to 20000; prefix a non-empty string; seed an integer >= 0; span an integer >= 1, otherwise invalid arguments). Rider i (1-based) has the id <prefix><i>. Their arrival tick and floors come from traffic.generate(seed, count, span): entry i - 1 is (offset, origin, dest), and rider i arrives at tick T + offset where T = max(ts, clock) is the tick the operation takes effect. If any of the generated ids is already used (as a rider, or by traffic that has not arrived yet) the operation fails with passenger exists and schedules nothing. It returns count.

• A scheduled rider arrives exactly like an arrive operation at their tick: same validation of floors (always valid here), same assignment in destination mode. Riders that share a tick arrive in order of (tick, scheduling order): earlier traffic operations first, then by i.
• Scheduled arrivals at a tick happen before any explicit operation at that tick, and before the step that leaves it. A rider whose arrival is refused in destination mode (no service) is dropped: they never exist (passenger not found) and rejected goes up.
• Until their tick, passenger reports a scheduled rider as {"status": "scheduled", "car": null, "boarded_at": null, "delivered_at": null}, and their id is taken (arrive with it fails with passenger exists).
• settle also waits for scheduled riders: it runs until nobody is waiting, riding or scheduled. When the bank is completely idle and only scheduled arrivals remain, the clock simply moves to the next arrival tick. Scheduled traffic also makes set_mode and set_floors busy.
• Everything else is unchanged: a scheduled day produces exactly the same results as the same riders typed out as arrive operations at the same ticks.

Performance. Hidden tests schedule thousands of riders across a full day of 86,400 ticks (and one across millions of idle ticks), with checkpoints along the way, out-of-service cars and rush hours that keep every car full. The output must be identical to a plain tick-by-tick simulation, but each run has a time limit of a few seconds.

Example. Three riders over a span of 8 ticks (generate(27, 3, 8) gives (3, 1, 16), (4, 1, 19), (5, 1, 12)):

[["traffic", 0, "T", 27, 3, 8],
 ["passenger", 0, "T1"],
 ["passenger", 3, "T1"],
 ["passenger", 3, "T2"],
 ["settle", 3],
 ["passenger", 0, "T1"], ["passenger", 0, "T2"], ["passenger", 0, "T3"],
 ["stats", 0]]

returns

[3,
 {"status": "scheduled", "car": null, "boarded_at": null, "delivered_at": null},
 {"status": "waiting", "car": null, "boarded_at": null, "delivered_at": null},
 {"status": "scheduled", "car": null, "boarded_at": null, "delivered_at": null},
 26,
 {"status": "delivered", "car": "A", "boarded_at": 4, "delivered_at": 22},
 {"status": "delivered", "car": "B", "boarded_at": 5, "delivered_at": 26},
 {"status": "delivered", "car": "C", "boarded_at": 6, "delivered_at": 20},
 {"delivered": 3, "rejected": 0, "total_wait": 3, "total_ride": 53, "max_wait": 1, "p90_wait": 1,
  "by_car": {"A": 1, "B": 1, "C": 1}}]

T1 lights the lobby call at tick 3 and boards A at step 4. T2 arrives at tick 4 while A is stopped; the call goes to B (cheaper than A, which is busy counting down). T3 arrives at tick 5, while both A and B are busy, and goes to C.

Notes

• You may use the AI assistant freely. Later parts must not break earlier ones; the hidden tests re-check all of them, including Part 1 behaviour after the destination-mode and replay features exist.
• Your AI assistant does not know this bank. The state of the world (pickups, promises, scheduled riders, which cars are in service) is spread over Bank and Car; read how they share it before you change either.