Sealing the wind chest

The sign-off sheet says nothing until you read it from the bottom. Read it that way and its last line names the block everything else hangs from.

The problem

An organ builder cuts a wind chest as a tree of channels. Each block of timber carries a stamped number, and a block may be split into two channels cut side by side across the bench: a low one and a high one.

The bench reading lists the stamps as an inspector reads across the chest from the low end to the high end; a block's stamp falls after every stamp in its low channel and before every stamp in its high channel. The sign-off sheet is the sealer's record, and a block may only be signed off once both channels beneath it are sealed, so every block is written after everything below it.

Stamps are distinct. Rebuild the chest from the two records.

Input. bench — the stamps low end to high end. sealed — the stamps in sign-off order.

Output. The chest level by level: outermost block first, then the channels either side of it, None where a block has no channel on that side, trailing None entries dropped.

Example.

bench  = [9, 22, 40, 55, 64, 71]
sealed = [9, 22, 55, 71, 64, 40]
  ->  [40, 22, 64, 9, None, 55, 71]

40 is signed off last, so it is the outermost block, and the bench reading puts 9 and 22 below it, 55, 64 and 71 above. Block 22 has 9 in its low channel and nothing high: the None.

A second example, one sheet and two different chests:

bench = [1, 4, 9], sealed = [1, 4, 9]   ->  [9, 4, None, 1]
bench = [9, 4, 1], sealed = [1, 4, 9]   ->  [9, None, 4, None, 1]

Sealing order is identical. Only the bench reading says whether each channel was cut on the low side or the high side.

Constraints.

• 0 <= len(bench) == len(sealed) <= 3000
• stamps are distinct integers, 1 <= stamp <= 10^6
• sealed is a permutation of bench

Hints

Approach

Brute force

Take the last stamp of the sheet, scan the bench reading for it, cut both records into slices and recurse. Each level scans and copies its whole run, so a chest split only one way does 3000 scans of up to 3000 stamps — about 4.5 million comparisons, and as many copied cells.

The insight

Read the sheet backwards and it becomes a top-down record: the last unread stamp is the outermost block of whichever run of the bench reading you are filling, and the stamp before it belongs to that block's high channel.

Sign-off order writes the low channel, then the high channel, then the block. Run it backwards and you get block, high, low — so a cursor stepping backwards lands on the right stamp every time, provided the high channel is built before the low one. That order is not a preference; getting it wrong makes the cursor read the wrong stamps. The precondition is distinct stamps, so each has one position in the bench reading.

Algorithm

1. Map each stamp to its index in bench, and set cursor = len(sealed) - 1.
2. build(lo, hi): if lo > hi there is no block here.
3. Otherwise take sealed[cursor], step the cursor back one, and look up split.
4. Build the high channel from split + 1 to hi, then the low channel from lo to split - 1.
5. Walk the finished chest level by level to write the chart.

Complexity

Time O(n) — one pass for the map, one block per stamp, a cursor that only moves backwards. Space O(n) for the map and the chart, plus O(h) frames.

Solution

"""Sealing the wind chest — rebuild a tree from an inorder bench reading and a
postorder sign-off sheet, consuming the sheet backwards."""

import sys
from collections import deque

sys.setrecursionlimit(20000)   # a chest that branches one way only is n frames deep


class Block:
    """One wind block. `low` and `high` are the two channels cut below it."""

    def __init__(self, stamp):
        self.stamp = stamp
        self.low = None
        self.high = None


def chart(root):
    """Write the chest out level by level, None where a channel is absent."""
    if root is None:
        return []
    plan, queue = [], deque([root])
    while queue:
        node = queue.popleft()
        if node is None:
            plan.append(None)
            continue
        plan.append(node.stamp)
        queue.append(node.low)
        queue.append(node.high)
    while plan and plan[-1] is None:
        plan.pop()
    return plan


def solve(bench, sealed):
    if not bench:
        return []
    seat = {stamp: i for i, stamp in enumerate(bench)}
    cursor = len(sealed) - 1

    def build(lo, hi):
        # invariant: sealed[cursor] is the top block of the run bench[lo..hi],
        # and every stamp after cursor is already placed in the chest.
        nonlocal cursor
        if lo > hi:
            return None
        node = Block(sealed[cursor])
        cursor -= 1
        split = seat[node.stamp]
        node.high = build(split + 1, hi)   # high first: reading the sheet backwards
        node.low = build(lo, split - 1)    # meets the high side before the low one
        return node

    return chart(build(0, len(bench) - 1))

TESTS = [
    (([9, 22, 40, 55, 64, 71], [9, 22, 55, 71, 64, 40]),
     [40, 22, 64, 9, None, 55, 71]),
    (([1, 4, 9], [1, 4, 9]), [9, 4, None, 1]),
    (([9, 4, 1], [1, 4, 9]), [9, None, 4, None, 1]),
    (([10, 20, 30, 50, 60, 80, 90], [10, 30, 20, 60, 90, 80, 50]),
     [50, 20, 80, 10, 30, 60, 90]),
    (([7], [7]), [7]),
    (([], []), []),
]

Pitfalls

• Building the low channel first. The calls share a cursor, so the low one consumes stamps belonging to the high side. The example above then rebuilds into a chest that is a valid tree and the wrong one, with no error raised.
• Stepping the cursor forwards. The sheet only names the outermost block from its end; starting at index 0 makes the first block a leaf and the rest nonsense.
• Slicing at every level, or calling bench.index(stamp). Either is a fresh linear pass per block and turns O(n) back into 4.5 million operations.
• A one-sided chest is 3000 frames deep, past CPython's default of 1000, so the second example is the shape that raises RecursionError.

Variants

• Walking the house — the same rebuild from a top-down record, cursor running forwards and the sides swapping back.
• The permit line — one record instead of two, with no need for the values to be distinct.