The bracket, first round first

A club stores its knockout draw the way it is drawn — final at the top, feeder ties hanging underneath. The programme has to print it the way it is played.

The problem

Each tie on the draw sheet carries a number printed on its fixture card. Under a tie sit the two ties whose winners meet in it. Where a place was filled by a bye there is no feeder tie on that side, so a tie may have two feeders, one, or none; a tie with no feeders is played in the first round.

Print the fixtures round by round in playing order: the round played first comes first, the final comes last. Within a round, keep the order the ties appear on the sheet, reading the draw from the top down.

Input. sheet — the draw as a level-order list starting at the final. After each tie come its two feeder places, None where the place was a bye.

Output. A list of rounds, earliest played first, each a list of tie numbers in draw order.

Example.

sheet = [8, 5, 12, None, None, 9, 21]   ->  [[9, 21], [5, 12], [8]]

Tie 8 is the final, fed by ties 5 and 12. Tie 5 was reached on two byes; tie 12 is fed by 9 and 21. The club plays 9 and 21 first, then 5 and 12, then the final.

A second example, where the rounds are not all the same size:

sheet = [3, None, 6, None, 11]   ->  [[11], [6], [3]]

Byes make a draw lean: 3 is fed only by 6, and 6 only by 11 — one fixture in each of three rounds. An empty sheet gives [], not [[]].

Constraints.

• 0 <= number of ties <= 10^4
• 1 <= tie number <= 10^4, all distinct
• A leaning draw can be 10^4 rounds deep, a flat one 5 x 10^3 ties wide

Hints

Approach

Brute force

Find the deepest round with one walk, then walk the whole sheet again once per round, keeping the ties at that depth: O(n x d) tie visits. A bye-heavy draw with 10^4 ties can be 10^4 rounds deep — 10^8 visits to read a sheet with 10^4 entries on it.

The insight

A queue that begins a pass holding exactly one round still holds exactly one round when the pass ends, provided you record its length before you drain it.

The queue is first-in-first-out, and the only ties pushed during a pass are feeders of ties popped in that pass — one round further down, every time. So the width ties you pop are the current round, and what is left behind is the next. Re-reading the length mid-pass breaks that, because by then the next round has already arrived.

Algorithm

1. Build the ties from the sheet; an empty sheet returns [].
2. Start a queue holding the final.
3. While the queue is not empty, read width = len(queue).
4. Pop exactly width ties, appending each number to the current round and pushing each feeder that exists.
5. Append the finished round to the rows.
6. Reverse the rows and return them.

Complexity

Time O(n) — every tie is pushed once and popped once, and the reversal touches each of at most n rows once. Space O(w) for the queue, where w is the widest round, plus the output.

Solution

"""The bracket, first round first — one level-order sweep, rounds written backwards."""

from collections import deque


class Tie:
    __slots__ = ("number", "upper", "lower")

    def __init__(self, number):
        self.number = number
        self.upper = None
        self.lower = None


def build(sheet):
    """Level-order draw sheet from the final down, None where a place was a bye."""
    if not sheet or sheet[0] is None:
        return None
    root = Tie(sheet[0])
    queue = deque([root])
    i = 1
    while queue and i < len(sheet):
        tie = queue.popleft()
        if i < len(sheet):
            number = sheet[i]
            i += 1
            if number is not None:
                tie.upper = Tie(number)
                queue.append(tie.upper)
        if i < len(sheet):
            number = sheet[i]
            i += 1
            if number is not None:
                tie.lower = Tie(number)
                queue.append(tie.lower)
    return root


def solve(sheet):
    root = build(sheet)
    if root is None:
        return []
    rounds = []
    queue = deque([root])
    while queue:
        # invariant: at the top of the loop the queue holds one whole round and
        # nothing else, so popping exactly this many ties empties that round.
        width = len(queue)
        this_round = []
        for _ in range(width):
            tie = queue.popleft()
            this_round.append(tie.number)
            if tie.upper is not None:
                queue.append(tie.upper)
            if tie.lower is not None:
                queue.append(tie.lower)
        rounds.append(this_round)
    rounds.reverse()          # the deepest round is the one played first
    return rounds

TESTS = [
    (([8, 5, 12, None, None, 9, 21],), [[9, 21], [5, 12], [8]]),
    (([3, None, 6, None, 11],), [[11], [6], [3]]),
    (([7, 2, None, 1],), [[1], [2], [7]]),
    (([4],), [[4]]),
    (([],), []),
    (([1, 2, 3, 4, 5, 6, 7],), [[4, 5, 6, 7], [2, 3], [1]]),
]

Pitfalls

• Reading len(queue) inside the drain loop rather than once before it. The loop keeps running as feeders arrive, and the first row swallows the whole draw: the first example returns [[8, 5, 12, 9, 21]].
• Building rows with rounds.insert(0, row) to dodge the reversal. Each insert shifts every row already stored: 5 x 10^7 element moves on a 10^4-round leaning draw, for what one reversal does in 10^4.
• Pushing a None place onto the queue. A bye is not a fixture; it lands in a round as a phantom entry, then fails on the next .number read.

Variants

• A run with exactly the vertical — one visit per node again, but depth-first with a number carried down instead of rows collected across.
• Parterre mirror — where a level sweep is the tempting wrong answer and walking pairs is the right one.