Host Stand: Waitlist, Reservations and Big Parties

Host Stand: Waitlist, Reservations and Big Parties

You've joined the team behind the host-stand tablet at Marlowe's Kitchen, a busy 6-table restaurant. The tablet keeps the walk-in waitlist, tells the host who to seat when a table frees up, and (soon) handles reservations and large parties. The hosts have filed three bug reports against the seating rules, and two features are queued behind them. Time is measured in whole minutes since opening.

Codebase

Floor plan (floor-plan order is the tie-break wherever a rule says "lowest floor-plan order"): T1 4 seats, T2 2, T3 6, T4 2, T5 4, T6 4.

How your code is run

run(operations: list[list]) -> list executes the operations in order against a fresh host stand and returns one result per operation. Every operation is [name, ts, ...args], where ts is an integer minute that never decreases. Errors are returned as "error: <code>" strings, never raised.

• A party id is a non-empty, case-sensitive string; a party size is an integer from 1 to 6 (true/false are not sizes). Party ids are never reused, even after the party has left (party exists).
• An unknown operation name returns "error: unknown operation". A wrong number of arguments or a non-integer ts returns "error: invalid arguments".
• walk_in returns "queued N" where N is the party's 1-based place in the queue after the operation has finished.
• free returns "<party>@<table>" for every party seated during that operation, in the order they were seated (empty list if nobody was). A table is "occupied" only if a party is sitting at it.
• board lists every table in floor-plan order: the id of the party sitting there, or "free". waiting is the queue, oldest first.

Part 1: Fix the seating rules (HOST-412, HOST-419, HOST-427)

Goal: make the waitlist seat parties exactly as the house rules below say. The hosts reported:

1. "A party of two got a 4-top while a 2-top sat empty."
2. "A single diner who had waited a full 30 minutes was still not offered the 4-top."
3. "Two parties both became eligible for a table at the same moment and only one was seated; the other sat there until something else happened."

Rules

1. The waitlist is ordered by arrival (the order of walk_in operations).
2. A seating pass goes through the waiting parties oldest first. For each party, the *best table* is the free table with at least size seats and the fewest seats; ties go to the lowest floor-plan order. If the party can be seated there it is, and the table is gone for the parties after it. A party that cannot be seated stays in the queue and never blocks the parties behind it.
3. Roominess limit: a party is not seated at a table with more than 2 spare seats (seats - size > 2) unless it has waited 30 minutes or more (ts - arrival >= 30). If its best table is too roomy it stays waiting; a still bigger table is never tried.
4. The seating pass runs at the start of every operation with a valid shape (so waiting time alone can make a party eligible), and again after walk_in and free have changed the room. A new walk-in joins the end of the queue and is seated by the pass if it can be.
5. Everything seated while handling an operation counts for that operation's result: walk_in reports whether *its* party was seated, free lists everyone seated during the operation, including parties who became eligible just because time had passed.

Worked example

[["walk_in", 0, "P1", 2], ["walk_in", 1, "P2", 2], ["walk_in", 2, "P3", 2], ["walk_in", 3, "P4", 6],
 ["walk_in", 4, "P5", 3], ["walk_in", 5, "P6", 4], ["walk_in", 6, "P7", 1], ["walk_in", 7, "P8", 2],
 ["free", 20, "T4"], ["free", 21, "T5"], ["walk_in", 22, "P9", 1], ["free", 25, "T3"], ["board", 52]]

returns

["seated T2", "seated T4", "seated T1", "seated T3", "seated T5", "seated T6", "queued 1", "queued 2",
 ["P7@T4"], ["P8@T5"], "queued 1", [],
 {"tables": {"T1": "P3", "T2": "P1", "T3": "P9", "T4": "P7", "T5": "P8", "T6": "P6"}, "waiting": []}]

P3 (two people) gets T1 because both 2-tops are taken and T1 is the first 4-top (2 spare seats is allowed). When T3 (6 seats) frees at minute 25, P9 (one person, waited 3) is refused it; at minute 52 P9 has waited exactly 30 minutes, so the pass at the start of board seats it.

tests/test_policy.py has a few failing tests that point at the first two reports.

Part 2: Reservations and quoted waits (HOST-433)

Goal: let hosts book a specific table in advance and quote walk-ins a wait. Reservations must keep walk-ins off the table around the booking time and release it again when the guests do not show up.

Rules

1. A reservation for table T at minute at holds T from at - 15 (inclusive) to at + 15 (exclusive). While a table is held and nobody is sitting at it, the waitlist may not use it. Holds are not affected by the 30-minute rule: no waiting time makes a held table available. A hold never evicts a party already sitting there.
2. No-shows: at the start of any operation with ts >= at + 15, a reservation that has not been checked in becomes a no-show and its hold ends. This happens *before* the seating pass of that same operation, so the freed table can go to the queue immediately. Time does not otherwise "start" a hold: a hold begins simply because ts >= at - 15.
3. reserve: reservation_id and table_id are non-empty strings and at an integer (else invalid arguments). Reservation ids share one namespace with party ids (party exists). invalid time if at <= ts. table conflict if another *still booked* reservation (not yet checked in or no-show) on the same table has abs(other_at - at) < 30, so reservations exactly 30 minutes apart are fine.
4. check_in seats the reservation at its table and returns "seated <table>". A reservation that was already checked in or has become a no-show is reservation not active; before at - 15 it is too early; if somebody is sitting at its table it is table busy (the reservation stays booked, and the guests may try again). The seated reservation behaves like any seated party: free on its table frees it, and its id is the party id on the board.
5. board shows a free table that is held as "held:<reservation_id>"; a table with someone sitting at it always shows that party.
6. Quote for a hypothetical walk-in of size (1 to 6) arriving now. It changes nothing.

• If a walk_in of that size at this minute would be seated immediately, the quote is 0.
• Otherwise let class be the seat count of the smallest table that fits size (sizes 1-2: 2, sizes 3-4: 4, sizes 5-6: 6), ahead the number of parties currently waiting whose own class is the same, and tables the number of tables with that seat count. The quote is ceil(DWELL * (ahead + 1) / tables) where DWELL is 45, 70, 90 for class 2, 4, 6 (DWELL_MINUTES in config.py), and never more than QUOTE_CAP_MINUTES (120). Example: two waiting parties of class 2 and a new party of 2 give ceil(45 * 3 / 2) = 68.

Worked example

[["reserve", 0, "R1", "T3", 60], ["reserve", 1, "R2", "T3", 70], ["reserve", 2, "R3", "T3", 90],
 ["board", 44], ["board", 45], ["walk_in", 46, "P1", 5], ["check_in", 47, "R3"],
 ["board", 75], ["check_in", 76, "R1"], ["check_in", 80, "R3"],
 ["quote", 81, 5], ["quote", 81, 2], ["free", 110, "T3"]]

returns (boards abbreviated; T1,T2,T4,T5,T6 stay "free" throughout)

[true, "error: table conflict", true,
 {"tables": {"T3": "free", ...}, "waiting": []}, {"tables": {"T3": "held:R1", ...}, "waiting": []},
 "queued 1", "error: too early",
 {"tables": {"T3": "held:R3", ...}, "waiting": ["P1"]}, "error: reservation not active", "seated T3",
 120, 0, ["P1@T3"]]

R1 (at 60) never shows, so at minute 75 it becomes a no-show; the same minute R3's hold begins (90 - 15), so P1 (size 5, only T3 fits) is still not seated. The quote for another party of 5 is ceil(90 * 2 / 1) = 180, capped at 120.

Part 3: Large parties and combined tables (HOST-451)

Goal: accept parties of up to 10 by pushing two tables together, without letting a big party's wait hold the whole room hostage. This changes the maximum party size and one rule from Part 1.

Rules

1. A party size may now be 1 to 10. A party of 7 or more is *large*. Large parties are seated only at a combination: one of the pairs in COMBOS (config.py), whose capacity is the sum of both tables' seats. Parties of 6 or fewer never use a combination.
2. A combination can be used only if both tables are usable by the pass (free, not held by a reservation, and not already taken earlier in the same pass). The party occupies both tables: walk_in returns "seated T5+T6" (tables in the order the pair is listed), board shows the party id on both tables, and free on either table frees both. Freed parties are listed as "P1@T5+T6".
3. Choosing a combination mirrors Part 1: the usable pair with at least size seats and the fewest combined seats; ties go to the pair listed first in COMBOS. The roominess limit (more than 2 spare seats) and the 30-minute exception apply to the combined seats.
4. Claims (no starvation either way). While the pass walks the queue, the first large party that has waited 20 minutes or more and could not be seated in this pass *claims* the pair with the fewest combined seats that fits it (ties: COMBOS order) whether or not its tables are free right now. Every party *after it in the queue* may not use the two claimed tables in this pass, unless that party has itself waited 30 minutes or more. At most one claim per pass; claims are not remembered between passes. (This is the one case where a waiting party holds up those behind it. Part 1 rule 2 still holds for everything else.)
5. Quote for a large party: 0 if it would be seated immediately; otherwise min(100 * (ahead + 1), 120) where ahead is the number of waiting large parties. The Part 2 quote for smaller parties counts only waiting parties of 6 or fewer in its ahead, and is otherwise unchanged. A quote (including the immediate check) sees claims exactly as the pass would.
6. All Part 1 and Part 2 rules still apply. A held table is never part of a usable pair.

Worked example

[["walk_in", 0, "A", 6], ["walk_in", 1, "B", 4], ["walk_in", 2, "C", 4], ["walk_in", 3, "D", 4],
 ["walk_in", 4, "E", 2], ["walk_in", 5, "F", 2], ["walk_in", 6, "G", 8], ["walk_in", 7, "H", 2],
 ["free", 10, "T5"], ["walk_in", 12, "I", 3], ["free", 30, "T6"], ["free", 31, "T5"]]

returns

["seated T3", "seated T1", "seated T5", "seated T6", "seated T2", "seated T4", "queued 1", "queued 2",
 ["H@T5"], "queued 2", [], ["G@T5+T6"]]

At minute 30 T6 frees, but G (size 8, waited 24) cannot be seated because T5 is taken by H, so G claims T5+T6. I (waited 18, below 30) is therefore not given T6, even though it is free and fits. At minute 31 T5 frees, the claimed pair is free and G is seated. I then waits for the next 4-top.