The permit line

The permit form has one line for the fuse tree. Whatever that line does not say is lost, and what people forget to say is where the fuse stops.

The problem

A display is fired through a tree of fuses. Each splitter carries a delay stamped in tenths of a second and has two legs; a leg either runs to another splitter or ends at a shell. Delays repeat freely — a batch of fuse is cut to one length.

The bench sheet records the tree level by level: the head splitter, then the splitters on its two legs, then theirs, None where a leg ends at a shell, trailing None entries dropped.

The permit wants a line: one piece of text the inspector can rebuild the tree from. It is a walk from the head that writes a splitter's delay, then everything on its first leg, then everything on its second, and writes # for a leg ending at a shell. Single spaces between tokens; an empty permit reads #.

Input. bench — the bench sheet of the fuse tree.

Output. Two elements: the line, and the bench sheet of the rebuilt tree.

Example.

bench = [12, 5, 9, None, None, 7, 7]

        12
       /  \
      5    9
          / \
         7   7

  ->  ["12 5 # # 9 7 # # 7 # #", [12, 5, 9, None, None, 7, 7]]

The 5-tenth splitter runs to shells on both legs: the # # after it. Both 7s are written as 7, and the markers around them still say which leg each sits on.

A second example, where the bench sheet was padded:

bench = [4, 3, None, 2, None, None, None]
  ->  ["4 3 2 # # # #", [4, 3, None, 2]]

The trailing None entries describe legs below splitters that have no legs left, so they carry nothing and come back off the line dropped.

Constraints.

• 0 <= splitters <= 10^4
• 1 <= delay <= 10^4, and delays may repeat
• the rebuilt tree must be identical to the original, splitter for splitter

Hints

Approach

Brute force

Give every splitter a fixed slot: the head is slot 1, and slot i's two legs are slots 2i and 2i + 1. Write the delays out by slot with blanks between. It rebuilds perfectly and it is unusable — 10⁴ splitters strung down one leg put the last at slot 2¹⁰⁰⁰⁰, a number of 3011 digits.

The insight

Write the gaps down. A walk that emits a marker for every leg ending at a shell describes the tree completely, and a tree of n splitters has exactly n + 1 such legs.

Every splitter offers two legs and every splitter but the head occupies one, so the ending legs number 2n − (n − 1) = n + 1 and the line is exactly 2n + 1 tokens whatever the shape. That is why the markers are affordable, and why they suffice: reading left to right, a marker closes a leg on the spot, so the reader always knows whether the next token belongs to the leg it is on or the one above. Delays alone leave that undecidable — 12 5 9 7 7 fits several trees.

Algorithm

1. Build the tree from the bench sheet with a queue, two entries per splitter.
2. Write the line from the head: append the delay, walk the first leg, then the second, appending # where a leg ends. Join with single spaces.
3. Read it back with a forward-only cursor over the split tokens: # means the leg ends; otherwise make a splitter and read its first leg, then its second.
4. Write the rebuilt tree out level by level, trailing None entries dropped.

Complexity

Time O(n) each way — the line holds 2n + 1 tokens, each written once and read once. Space O(n) for the line, plus O(h) frames on both walks.

Solution

"""The permit line — a top-down encoding that writes a marker for every fuse leg
that ends in nothing, read back by the same walk."""

import sys
from collections import deque

sys.setrecursionlimit(30000)   # a fuse tree that splits one way only is n deep

BLANK = "#"


class Splitter:
    """One fuse junction, stamped with its delay in tenths of a second."""

    def __init__(self, delay):
        self.delay = delay
        self.leg_a = None
        self.leg_b = None


def lay(bench):
    """Bench sheet: level order, None where a leg carries no further splitter."""
    if not bench or bench[0] is None:
        return None
    head = Splitter(bench[0])
    queue, i = deque([head]), 1
    while queue and i < len(bench):
        node = queue.popleft()
        if i < len(bench) and bench[i] is not None:
            node.leg_a = Splitter(bench[i])
            queue.append(node.leg_a)
        i += 1
        if i < len(bench) and bench[i] is not None:
            node.leg_b = Splitter(bench[i])
            queue.append(node.leg_b)
        i += 1
    return head


def write_line(head):
    """Top down: one token per splitter, one BLANK per leg that ends in nothing."""
    tokens = []

    def walk(node):
        if node is None:
            tokens.append(BLANK)
            return
        tokens.append(str(node.delay))
        walk(node.leg_a)
        walk(node.leg_b)

    walk(head)
    return " ".join(tokens)


def read_line(text):
    tokens = text.split()
    if not tokens:
        return None
    cursor = 0

    def read():
        # invariant: cursor is the first token of the leg still to be laid,
        # and every token before it is already on the bench.
        nonlocal cursor
        token = tokens[cursor]
        cursor += 1
        if token == BLANK:
            return None
        node = Splitter(int(token))
        node.leg_a = read()
        node.leg_b = read()
        return node

    return read()


def measure(head):
    """Write a fuse tree back out level by level, trailing blanks dropped."""
    if head is None:
        return []
    bench, queue = [], deque([head])
    while queue:
        node = queue.popleft()
        if node is None:
            bench.append(None)
            continue
        bench.append(node.delay)
        queue.append(node.leg_a)
        queue.append(node.leg_b)
    while bench and bench[-1] is None:
        bench.pop()
    return bench


def solve(bench):
    text = write_line(lay(bench))
    return [text, measure(read_line(text))]

TESTS = [
    (([12, 5, 9, None, None, 7, 7],),
     ["12 5 # # 9 7 # # 7 # #", [12, 5, 9, None, None, 7, 7]]),
    (([4, 3, None, 2, None, None, None],), ["4 3 2 # # # #", [4, 3, None, 2]]),
    (([1, None, 2, None, 3],), ["1 # 2 # 3 # #", [1, None, 2, None, 3]]),
    (([4, 4, 4, None, None, 4, 4],),
     ["4 4 # # 4 4 # # 4 # #", [4, 4, 4, None, None, 4, 4]]),
    (([8],), ["8 # #", [8]]),
    (([],), ["#", []]),
]

Pitfalls

• Leaving the markers out. 12 5 9 7 7 also describes a tree where 5 runs to 9, and one where 9 carries both 7s on its first leg. The reader cannot choose, so the round trip silently returns a different tree.
• Sending two orders instead. A pair of traversals pins the shape only while the delays are distinct, and the example has two 7s.
• Writing the empty tree as the empty string. "".split() yields no tokens and the reader runs off the list. One marker, #, is the line for nothing.
• Reading the second leg before the first. Both calls share the cursor, so the tree comes back mirrored — and a symmetric test tree will not show it.

Variants

• Two pedigree cards — the same markers used to compare two records rather than to ship one.
• Sealing the wind chest — the two-record rebuild this line replaces, and the distinct-values rule it needs.