Walking the house

A new usher is trained by walking the auditorium; a plan of it hangs by the door. Neither record draws the aisles. Together they do.

The problem

The Palliser auditorium is divided by aisles. Every block of seats carries a stamped code, and an aisle splits a block into two smaller blocks, one on house left and one on house right.

The walk is what the head usher calls out while training: standing in a block they call its code, then walk the whole house-left block before coming back for the house-right block. The plan by the door reads left wall to right wall, and a block's code is painted on its own aisle, so it falls after every code to its house left and before every one to its house right.

Codes are distinct. Rebuild the house from the two records.

Input. walk — the codes as the usher calls them. plan — the same codes left to right.

Output. The house level by level: outermost block first, then the blocks either side of its aisle, None where a block has nothing on that side, trailing None entries dropped.

Example.

walk = [18, 11, 5, 14, 27, 31]
plan = [5, 11, 14, 18, 27, 31]
  ->  [18, 11, 27, 5, 14, None, 31]

18 is called first, so it is the outermost block, and the plan puts 5, 11, 14 to its left and 27, 31 to its right. Block 27 has nothing to its house left: the None.

A second example, one walk and two different houses:

walk = [9, 4, 1], plan = [1, 4, 9]   ->  [9, 4, None, 1]
walk = [9, 4, 1], plan = [9, 4, 1]   ->  [9, None, 4, None, 1]

Three blocks nested to house left, then three nested to house right. The walk cannot tell them apart.

Constraints.

• 0 <= len(walk) == len(plan) <= 3000
• codes are distinct integers, 1 <= code <= 10^6
• plan is a permutation of walk

Hints

Approach

Brute force

Take the first code of the walk, scan the plan for it, cut both records into slices and recurse. Each level scans and copies its whole stretch, so a one-sided house does 3000 scans of up to 3000 codes — about 4.5 million comparisons, and as many copied cells.

The insight

The walk is consumed strictly front to back: the first unread code is always the outermost block of whichever stretch of the plan you are filling.

The walk names a block before anything inside it and finishes house left before starting house right, so each side's codes sit in one unbroken run. A forward-only cursor therefore lands on the right code every time, and the recursion only has to say which stretch of the plan it fills. The precondition is distinct codes: each needs one position in the plan for the lookup to mean anything.

Algorithm

1. Map each code to its index in plan, and set cursor = 0.
2. build(lo, hi): if lo > hi there is no block here.
3. Otherwise take walk[cursor], advance the cursor, and look up its index split.
4. Build house left from lo to split - 1, then house right from split + 1 to hi.
5. Walk the finished house level by level to write the chart.

Complexity

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

Solution

"""Walking the house — rebuild a tree from a preorder walk and a left-to-right plan."""

import sys
from collections import deque

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


class Section:
    """One block of seats. An aisle splits it into two smaller blocks."""

    def __init__(self, code):
        self.code = code
        self.house_left = None
        self.house_right = None


def draw(root):
    """Write the house out row of aisles by row, None where a block does not split."""
    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.code)
        queue.append(node.house_left)
        queue.append(node.house_right)
    while plan and plan[-1] is None:   # a trailing gap says nothing
        plan.pop()
    return plan


def solve(walk, plan):
    if not walk:
        return []
    seat = {code: i for i, code in enumerate(plan)}
    cursor = 0

    def build(lo, hi):
        # invariant: walk[cursor] is the outermost block of the stretch plan[lo..hi],
        # and every code before cursor is already placed in the house.
        nonlocal cursor
        if lo > hi:
            return None
        node = Section(walk[cursor])
        cursor += 1
        split = seat[node.code]
        node.house_left = build(lo, split - 1)    # left first: it consumes the codes
        node.house_right = build(split + 1, hi)   # the right call would otherwise take
        return node

    return draw(build(0, len(plan) - 1))

TESTS = [
    (([18, 11, 5, 14, 27, 31], [5, 11, 14, 18, 27, 31]),
     [18, 11, 27, 5, 14, None, 31]),
    (([9, 4, 1], [1, 4, 9]), [9, 4, None, 1]),
    (([9, 4, 1], [9, 4, 1]), [9, None, 4, None, 1]),
    (([50, 20, 10, 30, 80, 60, 90], [10, 20, 30, 50, 60, 80, 90]),
     [50, 20, 80, 10, 30, 60, 90]),
    (([42], [42]), [42]),
    (([], []), []),
]

Pitfalls

• Building house right first. The calls share a cursor, so the right one eats codes belonging to the left and you get a different, plausible house with no error raised. A symmetric example hides it; the second one above does not.
• Calling plan.index(code) in the recursion, or slicing the records. Either is a fresh linear pass per block, turning O(n) back into 4.5 million operations.
• A one-sided house is 3000 frames deep, past CPython's default of 1000, so the second example is the shape that raises RecursionError.

Variants

• Sealing the wind chest — the same rebuild from the other pair of records, cursor running backwards.
• The permit line — one record that pins the shape alone, even when values repeat.