Wedding Seating Chart: Best-Fit Placement, RSVP Changes and Near-Preferences

Wedding Seating Chart: Best-Fit Placement, RSVP Changes and Near-Preferences

You've joined the team behind an event-planning app. Couples enter their tables and guest list, press Plan, and get a seating chart. The current planner hands out seats first-come-first-served, and planners are unhappy: big families get split up in spirit (stuck at whatever is left), exes end up at the same table, and the head table fills with random guests. Three tickets are queued.

Codebase

How your code is run

run(operations: list[list]) -> list executes the operations in order against a fresh event and returns one result per operation. Every operation is [name, *args]. Errors are returned as "error: <code>" strings, never raised.

• A party is a group of guests (size >= 1) that must sit together at one table. rsvp is the integer time the party replied (>= 0, smaller = earlier). head is a boolean. A table has an integer number >= 1, an integer capacity >= 1 and a head boolean. Booleans are never accepted where an integer is expected, and head must be a real boolean.
• Ids are case-sensitive non-empty strings, compared with ordinary string order.
• add_party_run is the spreadsheet import: sizes is a non-empty list of integers >= 1, and row i (counting from 1) becomes the non-head party <prefix><i> with rsvp = first_rsvp + i - 1. It is all-or-nothing: if any of those ids already exists, nothing is added.
• keep_apart is symmetric: the two parties must never sit at the same table. It is not transitive (a/b apart and b/c apart say nothing about a and c). Repeating a pair is fine.
• Check order for every setup operation: wrong argument count, types or ranges returns invalid arguments; then plan locked (see below); then the operation's own errors in the order listed in the table (for keep_apart, same party is checked before unknown party). An unknown operation name returns unknown operation. An operation that is not a non-empty list starting with a string returns invalid arguments.
• plan freezes the event: after the first plan, add_table, add_party and keep_apart (and prefer_near in Part 3) return plan locked. Calling plan again is allowed.
• The plan is {"tables": [[number, [party ids]], ...], "unseated": [party ids]}. Tables are listed by number ascending and every table appears, even an empty one. Party ids within a table are ordered by size descending, then id. unseated is ordered by size descending, then rsvp, then id.

Worked example

[["add_table", 1, 6, false], ["add_table", 2, 6, false],
 ["add_party", "aoki", 2, 1, false], ["add_party", "bell", 4, 2, false], ["add_party", "cruz", 3, 3, false],
 ["keep_apart", "aoki", "bell"],
 ["plan"]]

The last result is {"tables": [[1, ["bell"]], [2, ["cruz", "aoki"]]], "unseated": []}.

Part 1 — Replace the first-fit planner (PLAN-412)

Goal: make plan use the placement algorithm below instead of "first table with room, in RSVP order". Parties and tables are given by the setup operations; plan computes where everybody sits.

Rules

1. Order. Parties are placed one at a time sorted by size descending, then rsvp ascending, then id ascending.
2. Eligible tables for a party: (a) the table's head flag equals the party's head flag (head parties sit only at head tables and nobody else may use a head table); (b) at least size free seats; (c) no party already seated there is kept apart from it.
3. Best fit. Among eligible tables choose the one with the fewest free seats (before the party sits down); ties go to the lowest table number.
4. A party with no eligible table is unseated. It is skipped: smaller parties after it are still placed normally, and nobody is moved to make room.
5. plan always works from the current guest list and tables alone: calling it twice in a row returns the same result. Parties are placed whole, never split.

Example (the worked example above): order is bell (4), cruz (3), aoki (2). Both tables have 6 free, so bell takes table 1. cruz needs 3: table 1 has 2 free, so table 2. aoki fits table 1 (2 free) but bell must stay apart from her, so she joins cruz at table 2.

Part 2 — RSVP changes without reshuffling (PLAN-437)

Goal: guests change their minds after the chart is printed. Add rsvp so a size change is applied to the existing plan with as few moves as possible: nobody who is seated and still fits ever moves. (Re-running the whole placement would reshuffle tables people have already been told about.)

new_size is an integer >= 0; 0 means the party declined. seating returns the plan as it stands now (after any rsvp calls). plan always recomputes everything from the current party sizes and is the only operation that may move everyone.

Rules for rsvp

1. The party's size becomes new_size. A declined party (size 0) is not seated and does not appear in unseated; a later rsvp with a positive size brings it back.
2. If the party is seated and new_size > 0: it stays at its table if the table can hold the new size alongside the others already there (this covers shrinking, and growing into free seats). Otherwise it is taken off its table and needs a new one. If new_size is 0 it is simply removed.
3. Afterwards, every unseated party (the one that just lost its table included) is offered a table in the Part 1 order (size descending, then rsvp, then id), using the Part 1 table choice (eligibility and best fit) against the plan as it currently stands. Anyone who finds a table sits there; anyone who does not stays unseated. Nobody who is seated is ever moved to make room.
4. The result lists one move [party_id, from_table, to_table] per party whose table changed (null for "not seated"). The changed party comes first (if its table changed), then the other parties that got a seat, in the order they were seated. No change returns [].

Example (tables 1 and 2 hold 6, table 3 holds 4; parties a 4, b 3, c 3, d 2, e 2, f 1 with rsvp 1 to 6 in that order, none head, no keep-apart). The plan is T1 [b, c], T2 [d, e, f], T3 [a].

Afterwards seating returns {"tables": [[1, ["b", "c"]], [2, ["d", "f"]], [3, ["e"]]], "unseated": []}.

Part 3 — "Seat us together" and the printable chart (PLAN-455)

Goal: couples want to say "these two parties should share a table if possible". Add soft preferences that influence placement without ever breaking a Part 1 rule, plus a chart planners can print.

weight is an integer from 1 to 10 (anything else is invalid arguments). A pair may be given again; the latest weight wins. Preferences are symmetric. A party with at least one preference is called *linked*; the rest are unlinked.

Rules

1. Table choice. For a party, each eligible table gets an *affinity*: the sum of the weights of the party's near-partners that are currently seated at that table. Choose the eligible table with the highest affinity, then fewest free seats, then lowest number. For a party with no seated partner every affinity is 0, so this is exactly the Part 1 rule. Eligibility never changes.
2. Pulling partners forward (plan only). Parties are still offered tables in the Part 1 order, but after a party has been placed (or found unseatable) its *unplaced* near-partners with positive size are placed immediately next, highest weight first (ties: Part 1 order), and each of them pulls its own unplaced partners in turn, before the next partner of the first party is handled (depth first). Then the walk resumes with the next unplaced party in Part 1 order. Unlinked parties are never pulled and keep their place in the order.
3. rsvp re-placements (Part 2, rule 3) use the new table choice (rule 1) but never pull partners.
4. near_score is [S, T]: T is the sum of the weights of all preferences, S the sum over those whose two parties are seated at the same table right now.
5. Chart. chart returns one line per table by number ascending, then an Unseated line, then a score line:

• Table <n> <used>/<capacity>: <parties>, or Table <n> (head) <used>/<capacity>: ... for head tables. <parties> is the table's parties ordered by size descending then id, each written <id> x<size>, joined by , ; an empty table prints -.
• Unseated: <parties>, in unseated order, each <id> x<size>; - when nobody is unseated.
• Near-score: <S>/<T>.

Example (tables 1 and 2 hold 6, table 3 holds 4; lee 4 rsvp 1, kim 3 rsvp 2, ono 2 rsvp 3, pak 2 rsvp 4; ["prefer_near", "pak", "kim", 5]; then plan, chart, near_score): lee takes table 3 (4 free is the tightest fit). kim takes table 1, and then pak is pulled forward ahead of ono: table 1 has affinity 5 for pak and room, so she sits with kim. ono goes to table 2.

["Table 1 5/6: kim x3, pak x2", "Table 2 2/6: ono x2", "Table 3 4/4: lee x4", "Unseated: -", "Near-score: 5/5"]

and near_score returns [5, 5]. Without the preference pak would have been placed last, in table 2.