Canopy walkway check

A guide checks a rope walkway one height band at a time, never crossing a band in the direction they have just come from. The plan is not stored in that order.

The problem

A canopy walkway hangs between trees in a forest reserve. It starts at one platform, and every platform sends at most two rope bridges onward — one left, one right — each dropping the same distance. Platforms therefore sit in height bands: the start platform is the top band, the platforms one bridge below it the next, and so on. Each platform has a deck number stencilled on it.

The check runs band by band from the top down. Inside a band the guide clips onto a traverse line and works straight across, and since they finish at the far end there is no sense walking back: the top band is read left to right, the next right to left, the next left to right again. Report the deck numbers band by band, in the order the guide reaches them.

The walkway arrives in compact level-order form — the start platform, then each band left to right, None for a missing bridge. A gap sends no bridges of its own, and trailing gaps are trimmed.

Input. walkway — the walkway in compact level-order form.

Output. A list of lists: one per band, top band first, each in the order the guide reaches its platforms.

Example.

walkway = [4, 9, 2, None, 5, 7, 1]   ->  [[4], [2, 9], [5, 7, 1]]

The next band holds 9 then 2 left to right, and the guide crosses it the other way, so 2 comes first. The bottom band — 5 under 9, then 7 and 1 under 2 — is read left to right again.

A second example, where a band is four platforms wide:

walkway = [4, 9, 2, 6, 5, 7, 1, 3, 8, 11, 12]
   ->  [[4], [2, 9], [6, 5, 7, 1], [12, 11, 8, 3]]

The bottom band is 3 and 8 under platform 6, then 11 and 12 under platform 5; reversed, that is 12, 11, 8, 3. Turning each platform's own pair around instead would give 8, 3, 12, 11 — the reversal runs across the band, not inside a platform.

Constraints.

• 0 <= platforms <= 10^4
• 1 <= deck number <= 10^6, all distinct
• the walkway may be one chain of bridges, so it can be 10^4 bands deep
• an empty walkway returns an empty list

Hints

Approach

Brute force

Find every platform's depth with one walk, then sweep the whole walkway again per band, keeping only the platforms at that depth and reversing alternate results. A chain of 10^4 platforms has 10^4 bands of one platform each: 10^8 visits for 10^4 answers.

The insight

Direction belongs to the band, not to the walk — collect every band left to right with one queue, then reverse the finished band on every second one.

A queue drained one band at a time already emits that band left to right: it pops parents in that order and appends their bridges behind them in the same order. Reversing a band of w entries costs O(w), and the bands partition the platforms, so all the reversals together cost O(n). The precondition is that a band is complete before you reverse it — which is why the width must be read before the first pop.

Algorithm

1. Rebuild the walkway, queueing only real platforms so a gap claims no bridge slots.
2. If there is no start platform, return an empty list.
3. Put the start platform in a queue and set flip to false.
4. Record the queue's length — the whole band — and pop that many platforms, appending each bridge behind them.
5. Reverse the band if flip is set, add it to the answer, and flip flip.
6. Repeat from step 4 while the queue holds anything.

Complexity

Time O(n) — each platform is queued once, popped once, reversed at most once. Space O(w) for the widest band: about 5000 for a balanced walkway of 10^4 platforms, 1 for a chain.

Solution

"""Canopy walkway check — level sweep with the reading direction flipped per band."""

from collections import deque


class Platform:
    """One platform: a stencilled deck number and two bridge slots."""

    __slots__ = ("deck", "left", "right")

    def __init__(self, deck):
        self.deck = deck
        self.left = None
        self.right = None


def build(level_order):
    """Rebuild the walkway from its compact level-order form."""
    if not level_order or level_order[0] is None:
        return None
    root = Platform(level_order[0])
    queue = deque([root])
    i = 1
    while queue and i < len(level_order):
        # invariant: only real platforms are queued, so a gap never claims bridge slots
        node = queue.popleft()
        if i < len(level_order):
            value = level_order[i]
            i += 1
            if value is not None:
                node.left = Platform(value)
                queue.append(node.left)
        if i < len(level_order):
            value = level_order[i]
            i += 1
            if value is not None:
                node.right = Platform(value)
                queue.append(node.right)
    return root


def solve(walkway):
    root = build(walkway)
    if root is None:
        return []
    bands = []
    queue = deque([root])
    flip = False
    while queue:
        # invariant: the queue holds exactly one band, in left-to-right order
        width = len(queue)          # fixed before any bridge of this band is appended
        band = []
        for _ in range(width):
            node = queue.popleft()
            band.append(node.deck)
            if node.left is not None:
                queue.append(node.left)
            if node.right is not None:
                queue.append(node.right)
        bands.append(band[::-1] if flip else band)
        flip = not flip             # direction belongs to the band, not to the walk
    return bands

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

Pitfalls

• Reversing the list of bands rather than the platforms inside one. bands[::-1] on the first example gives [[5, 7, 1], [2, 9], [4]] — the bottom band first, which is not a route anyone can walk.
• Flipping the order bridges are queued instead of reversing the band. Appending the right bridge first on alternate bands only turns each platform's own pair around: the four-wide band comes out 8, 3, 12, 11.
• Reading len(queue) after popping has started. Take the width before the first pop; a length that grows as bridges are appended swallows the next band into the current one and returns one flat band. On [4, 9, 2, None, 5, 7, 1, 3, 8] that collapses four bands into two.

Variants

• Call-out rounds — the same band sweep, counting the bands instead of keeping what is in them.
• Traversal families — where the walk orders come from, and when a queue beats a stack.