Tournament Brackets: Seeding, Double Elimination and Regional Separation

Bracket Service: Seeding, Double Elimination and Regional Separation

You've joined the tournament-tech team at an esports organizer. Their bracket service builds the brackets for every open qualifier and reports results as matches finish. Players have been complaining: the top two seeds meet in the semifinal, and 8-player events somehow get a whole extra round of byes. Your job is to fix the single-elimination brackets, then teach the service double elimination, then honor a new rule from the league office: players from the same region must not meet early.

Codebase

How your code is run

run(operations: list[list]) -> list executes the operations in order against a fresh service and returns one result per operation. Every operation is [name, *args]. Errors are returned as "error: <code>" strings, never raised. An unknown operation name returns "error: unknown operation"; a wrong number of arguments (or an operation that is not a non-empty list starting with a string) returns "error: invalid arguments". Both are checked before anything else. Any operation other than create before a successful create returns "error: no tournament". A service holds exactly one tournament.

• entrants is a list of [name, region] rows in seed order: the first row is seed 1. A name is a non-empty string (case-sensitive, used as given); a region is a string or null. Anything else makes the row malformed.
• Large fields do not have to be written out: instead of a list, entrants may be a generator object {"count": n, "prefix": "s", "regions": [...]} (prefix and regions optional). Entrant i (1-based) is named prefix + i (default prefix "s", so s1, s2, ...) and gets regions[(i - 1) % len(regions)] (no region when regions is missing or empty). See expand_entrants in seeding.py; the entrant limits apply to the result.
• A non-string match_id, winner, absent, name or mode returns invalid arguments.
• report and walkover use the same checks. A match that is already decided (including byes) is already decided; one that does not yet have two entrants is match not ready; naming someone who is not playing in it is not a participant. A walkover records absent as the loser exactly like a played loss: the result routes the same way and only the status differs.
• simulate plays every match that can be played until none is left. "favorites": the better seed (lower number) wins every match. "upsets": the worse seed wins every match. Results do not depend on the order matches are played in. Any other mode is invalid arguments.
• status.played counts matches with status played, walkovers those with status walkover; byes and skipped matches count as neither.

Bracket model (single elimination)

Entrants are seeded 1..N. The bracket has S positions, where S is the smallest power of two that is at least N (N = 8 gives S = 8) and R = log2(S) rounds. Positions are numbered 0..S-1 from the top.

Seed order. The seed at each position comes from this construction: start with [1]. To double a list of length m into one of length 2m, replace every seed x (left to right) by the two seeds x, 2m + 1 - x.

• size 2: [1, 2]
• size 4: [1, 4, 2, 3]
• size 8: [1, 8, 4, 5, 2, 7, 3, 6]
• size 16: [1, 16, 8, 9, 4, 13, 5, 12, 2, 15, 7, 10, 3, 14, 6, 11]

Round 1 match j (1-based) is played between the entrants at positions 2j-2 and 2j-1.

Byes. Seeds above N do not exist, so their positions are empty. A seed that would face an empty position has a bye: its round 1 match is decided immediately with status bye, nobody is eliminated, and the entrant is already waiting in round 2. Because of the seed order, the byes always go to the top S - N seeds. pairings shows an empty position as null (in the second place of the pair).

Matches. The id of match j of round r is W{r}-{j} (W1-1, W2-3, ...). The winner of W{r}-{j} moves to W{r+1}-{ceil(j/2)}, into slot a if j is odd and slot b if j is even. The winner of the last round's only match is the champion. A match has status pending (an entrant is still missing), ready (both entrants known, not decided), played, walkover, bye or skipped. In match and next, null means no entrant is known (yet).

Queries. next returns the entrant's current undecided match and the opponent, null while that opponent is still unknown. An entrant who lost is eliminated; the champion has no further matches. path lists the matches the entrant has to win to become champion, starting with the current one: after a bye, round 1 is not on the path.

Part 1: Fix single-elimination brackets

Goal: make create, pairings, match, report, walkover, next, path, simulate and status behave exactly as described above. The service currently produces brackets with the wrong shape: read tests/ for failing examples, then find the causes in seeding.py and engine.py.

1. Round 1 must follow the seed-order construction above for every size.
2. The bracket size and the number of byes must follow the rules above for every N.
3. Bye holders must land in the correct round 2 slot, so that when the sibling match is reported nobody is overwritten.

Example (6 entrants named s1..s6, no regions):

[["create", [["s1", null], ["s2", null], ["s3", null], ["s4", null], ["s5", null], ["s6", null]]],
 ["pairings"],
 ["match", "W2-1"],
 ["report", "W1-2", "s5"],
 ["match", "W2-1"],
 ["next", "s5"],
 ["path", "s1"]]

returns

[{"size": 8, "rounds": 3, "byes": 2},
 [["s1", null], ["s4", "s5"], ["s2", null], ["s3", "s6"]],
 {"id": "W2-1", "a": "s1", "b": null, "status": "pending", "winner": null},
 {"winner_to": "W2-1", "loser_to": null},
 {"id": "W2-1", "a": "s1", "b": "s5", "status": "ready", "winner": null},
 ["W2-1", "s1"],
 ["W2-1", "W3-1"]]

Part 2: Double elimination

Goal: create accepts an optional second argument, an options object. {"format": "double"} builds a double-elimination bracket: losing once drops an entrant into a losers' bracket, losing twice eliminates them, and a grand final decides the champion. The default ("single", or no options) is exactly Part 1. Part 1's rules for seeding, byes, queries and errors stay in force for the winners' bracket.

Options error handling (checked after already created and the invalid arguments check on the entrants list): an options value that is not an object is invalid arguments; an unknown key, a format other than "single" or "double" is invalid option. Then the entrant count checks run, with the minimum raised to 3 entrants for a double bracket (too few entrants).

Let S, R be as before. Match ids are W{r}-{j} for the winners' bracket (as in Part 1, with the final W{R}-1 now feeding the grand final), L{k}-{j} for the losers' bracket, GF1 and GF2.

1. Losers' bracket shape. It has 2R - 2 rounds. Round k has S >> (ceil(k/2) + 1) matches (for S = 16: 4, 4, 2, 2, 1, 1).
2. Round 1 drop. Losers of W1-j go to L1-ceil(j/2): slot a if j is odd, slot b if j is even.
3. Later drops. For r >= 2 the loser of W{r}-j goes to slot b of L{2r-2}-c, where n = S >> r and c = j if r is odd, c = n + 1 - j if r is even (the "cross" that keeps entrants from meeting again right away).
4. Winners within the losers' bracket. The winner of L{k}-j goes to: L{k+1}-j, slot a, when k is odd; L{k+1}-ceil(j/2), slot a if j is odd and b if j is even, when k is even and k < 2R - 2; GF1, slot b, when k = 2R - 2. The loser of any losers' bracket match is eliminated.
5. Grand final. GF1 is W{R}-1's winner (slot a) against L{2R-2}-1's winner (slot b). If slot a wins, they are champion, the other entrant is eliminated, GF2 becomes skipped, and the result is {"winner_to": null, "loser_to": null}. If slot b wins (the bracket reset), both entrants go to GF2 in the same slots and the result is {"winner_to": "GF2", "loser_to": "GF2"}; the winner of GF2 is champion and the other is eliminated.
6. Byes in the losers' bracket. A slot fed by a bye match (nobody lost it) is *empty forever*. A match with both slots known and exactly one empty is a bye: the other entrant is its winner and moves on at once, and its loser is "nobody", which fills the loser slot of that match (if it has one) as another empty slot. A match whose slots are both empty is also a bye; nobody wins it and it sends empty slots on. This can cascade through several matches the moment the bracket is created or a loser arrives. A match with one empty slot and one slot still unknown stays pending until that slot is filled.
7. report and walkover return where the winner and the loser were routed, as ids; the loser of a losers' bracket match, and the final results above, give null. Routed ids are returned even when the match they point to resolves itself as a bye.
8. next and path work across both brackets. path lists the matches the entrant must win, starting with the current one and following winners only, ending with GF1 (GF2 is never listed); matches that are or will be byes (an empty slot) are left out. A walkover is a loss for absent: they drop or are eliminated exactly as if they had lost a played match.
9. simulate plays GF2 too if it is ready when simulate runs. A bracket without a reset has N - 1 playable matches (single) or 2N - 2 (double). The crossing in rule 3 is not a rematch guarantee: two entrants can meet again (always possible in the grand final, and in small brackets).

Example (4 entrants, double elimination):

[["create", [["s1", null], ["s2", null], ["s3", null], ["s4", null]], {"format": "double"}],
 ["report", "W1-1", "s4"],
 ["report", "W1-2", "s2"],
 ["report", "L1-1", "s1"],
 ["report", "W2-1", "s2"],
 ["next", "s4"],
 ["report", "L2-1", "s1"],
 ["path", "s1"],
 ["report", "GF1", "s1"],
 ["match", "GF2"],
 ["report", "GF2", "s2"],
 ["status"]]

returns

[{"size": 4, "rounds": 2, "byes": 0},
 {"winner_to": "W2-1", "loser_to": "L1-1"},
 {"winner_to": "W2-1", "loser_to": "L1-1"},
 {"winner_to": "L2-1", "loser_to": null},
 {"winner_to": "GF1", "loser_to": "L2-1"},
 ["L2-1", "s1"],
 {"winner_to": "GF1", "loser_to": null},
 ["GF1"],
 {"winner_to": "GF2", "loser_to": "GF2"},
 {"id": "GF2", "a": "s2", "b": "s1", "status": "ready", "winner": null},
 {"winner_to": null, "loser_to": null},
 {"champion": "s2", "played": 7, "walkovers": 0}]

Part 3: Regional separation

Goal: the league office wants entrants from the same region kept apart in the opening rounds. create options gain "separation": k (an integer >= 0, default 0, a bool is not an integer; anything else is invalid option). With k = 0 nothing changes: positions are exactly those of Part 1. With k >= 1, the service rearranges the positions with the procedure below before building the bracket (single or double).

Two entrants *conflict* when they have the same region (after normalize_region; entrants without a region never conflict) and sit in the same block: positions p and q share a block when p >> k' == q >> k' with k' = min(k, R). Sharing a block means they could meet in one of the first k' rounds. (For k = 1 that is "paired in round 1".)

Procedure. Start from the Part 1 positions. The bye holders (the top S - N seeds) are pinned: they never move. Go through seeds s in ascending order, skipping pinned seeds. Let E be the entrant of seed s, at position p. Only entrants with a lower seed number than s count when looking for conflicts (their positions are final).

1. If E has no region, or no lower-seeded entrant of its region shares E's block, move on.
2. Otherwise try the candidates G in ascending seed order, over seeds s + 1 .. N (pinned seeds are never candidates). G is at position q. The swap is accepted for the first G for which both hold: no lower-seeded (than s) entrant of E's region shares the block of q, and no lower-seeded entrant of G's region (if G has a region) shares the block of p.
3. On accepting, E and G exchange positions. If no candidate qualifies, E stays where it is (the conflict is unavoidable) and the procedure moves on.

Positions of seeds s + 1 .. are not final until they are processed themselves, so a swapped-in G can move again when its turn comes. Bye holders keep their byes and their positions, and the bracket model (byes, round 2 placement, double elimination) is then built from the final positions. Seed numbers do not change, simulate still compares seeds, and create returns the same sizes. Part 3 only moves entrants; all rules of Parts 1 and 2 apply to the result.

The service must stay fast: events of up to 1,024 entrants with many regions are created repeatedly.

Example (8 entrants, regions given, separation 1 and 2):

[["create", [["Ash", "EU"], ["Bo", "NA"], ["Cy", "EU"], ["Dee", "NA"], ["Eli", "EU"], ["Fay", "KR"], ["Gus", "NA"], ["Hal", "KR"]], {"separation": 1}],
 ["pairings"]]

Without separation round 1 is Ash-Hal, Dee-Eli, Bo-Gus, Cy-Fay: Bo and Gus (both NA) are paired. Gus (seed 7) is the first conflict; Hal (seed 8) is the first candidate who fits, so they swap:

[{"size": 8, "rounds": 3, "byes": 0},
 [["Ash", "Gus"], ["Dee", "Eli"], ["Bo", "Hal"], ["Cy", "Fay"]]]

With "separation": 2 (blocks of four positions) the arrangement stays the Part 1 one: Eli (EU) shares a block with Ash and no worse seed fits, so the conflict is unavoidable.

Notes

• Part 1's behavior must keep working after Parts 2 and 3; hidden tests re-check it.
• Run tests/ however you like (they only use assert); hidden tests call run with operation lists.
• Python 3 standard library only.