Rehanging the mobile

A hotel atrium is being rebuilt across the lobby, and the mobile hanging in it has to read the same from the new balcony. That means hanging its mirror image.

The problem

A kinetic mobile hangs from the atrium ceiling. Every element of it — a balance rod or a single steel plate — carries a stamped catalogue tag, and every rod hangs at most two elements: one from its left arm, one from its right.

The new atrium is entered from the opposite side, so the piece has to be rebuilt as its mirror image: what hung on the left arm of a rod now hangs on its right, all the way down. Produce the hanging plan for the mirrored piece.

Plans are written in compact level-order form — the top element, then each layer left arm before right arm, None for an empty arm. An empty arm hangs nothing of its own, and trailing empties are trimmed. Your answer uses the same form.

Input. mobile — the hanging plan in compact level-order form.

Output. The hanging plan of the mirrored mobile, in the same form.

Example.

mobile = [3, 9, 20, None, None, 15, 7]   ->  [3, 20, 9, 7, 15]

Rod 3 hangs plate 9 on the left and rod 20 on the right, and rod 20 hangs plates 15 and 7. Mirrored, rod 20 moves to the left arm of 3 and its own plates change places, so 7 comes before 15.

A second example, a mobile that leans entirely one way:

mobile = [5, 4, None, 2]   ->  [5, None, 4, None, 2]

Every element hangs from a left arm, so in the mirror every one hangs from a right arm. The empty arms move to the other side and have to be written out, which is why the answer is longer than the input.

Constraints.

• 0 <= elements <= 10^4
• 1 <= catalogue tag <= 10^6, all distinct
• the mobile may be a single chain of rods, so it can be 10^4 elements deep
• an empty plan returns an empty plan

Hints

Approach

Brute force

Give every element an address — the sequence of left and right arms taken from the top, so plate 15 above is "right, left". Flip every letter of every address, then hang the elements one at a time by walking each flipped address down from a new top rod. Building and re-walking the addresses is O(n · h) twice over: 10^8 steps for a chain of 10^4 elements, plus a second structure to hang them in.

The insight

Mirroring the whole mobile is nothing more than swapping the two arms of every rod, once each — so one visit per element is enough.

The mirror of a rod is, by definition, a rod whose left arm carries the mirror of what hung on its right and whose right arm carries the mirror of the left. That mentions no depth and no addresses, so applying it once per rod finishes the job. It is sound because the mobile is a tree: each element hangs from exactly one arm, so the two sides of a rod share nothing and swapping one cannot disturb the other.

Algorithm

1. Rebuild the mobile, queueing only real elements so an empty arm claims no slots.
2. Push the top element on a stack.
3. Pop an element, swap its two arms in one simultaneous assignment, and push the arms that exist. Repeat until the stack is empty.
4. Write the plan back out with a level sweep: for each element emit its two arm slots, None for an empty one, then trim the trailing empties.

Complexity

Time O(n) — one swap per element, one emission per arm slot. Space O(n) for the rebuilt mobile; the stack holds at most the height, 14 entries for a balanced mobile of 10^4 elements and 10^4 for the chain above.

Solution

"""Rehanging the mobile — swap both arms of every rod in one iterative pass."""

from collections import deque


class Hanger:
    """One element of the mobile: a catalogue tag and two arm slots."""

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

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


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


def write_plan(root):
    """Write the mobile back out in compact level-order, trailing gaps trimmed."""
    if root is None:
        return []
    plan = [root.tag]
    queue = deque([root])
    while queue:
        node = queue.popleft()
        # invariant: a gap fills its own slot but is never queued, so it lists no arms
        for arm in (node.left, node.right):
            plan.append(None if arm is None else arm.tag)
            if arm is not None:
                queue.append(arm)
    while plan and plan[-1] is None:
        plan.pop()
    return plan


def solve(mobile):
    root = build(mobile)
    stack = [root] if root is not None else []
    while stack:
        node = stack.pop()
        # invariant: a rod is swapped exactly once, and the swap is simultaneous,
        # so neither arm is read after it has already been overwritten
        node.left, node.right = node.right, node.left
        if node.left is not None:
            stack.append(node.left)
        if node.right is not None:
            stack.append(node.right)
    return write_plan(root)

TESTS = [
    (([3, 9, 20, None, None, 15, 7],), [3, 20, 9, 7, 15]),
    (([5, 4, None, 2],), [5, None, 4, None, 2]),
    (([1, 2, 3, 4, 5, 6, 7],), [1, 3, 2, 7, 6, 5, 4]),
    (([],), []),
    (([7],), [7]),
    (([40, 25, 61, 18, 33, None, 77],), [40, 61, 25, 77, None, 33, 18]),
]

Pitfalls

• Swapping only the arms at the top. The mirror is not one exchange: the first example gives [3, 20, 9, 15, 7], where 20 has moved but its own plates are still in the old order.
• Assigning the arms one after the other. rod.left = mirror(rod.right) followed by rod.right = mirror(rod.left) reads the arm it has just overwritten, so the same subtree is hung twice and the other one is lost: the first example comes out [3, 20, 20, 7, 7, 7, 7]. Swap in one statement.
• Listing arm slots for an empty arm when writing the plan out. A None hangs nothing, so emitting two slots for it shifts every later tag under the wrong rod, and the plan no longer rebuilds into the mobile you mirrored.
• Recursing down a chain. A recursive mirror is fine on a balanced mobile, but the 10^4-element chain the constraints allow passes Python's default recursion limit of 1000 and raises RecursionError.

Variants

• Refiling the drawer cabinet — mirroring an ordered index turns every comparison around; that page checks whether the ordering rule survives.
• The pasted slips — reads a tree left to right instead of rewriting it, and the mirror reverses exactly that reading.