Parterre mirror

A parterre is meant to read the same from either side of the central walk. The plan on paper either folds onto itself or it does not, and the eye is bad at telling which.

The problem

The plan is drawn as a branching diagram. One bed sits on the central walk, and under every bed there may be a bed cut to its left and a bed cut to its right. Each bed carries a planting code — the number of the mix sown in it.

Fold the plan along the central walk. The garden is a mirror when every bed on the left comes down on a bed with the same planting code on the right, and every gap comes down on a gap.

Input. plan — the beds in level order starting at the central bed, with None where no bed is cut.

Output. True if the plan folds onto itself, False otherwise.

Example.

plan = [4, 9, 9, 3, 7, 7, 3]   ->  True

Left of the walk: bed 9 with 3 outside it and 7 inside. Right: bed 9 with 7 inside and 3 outside. Folding puts 3 on 3 and 7 on 7.

A second example, which has the same codes and the same count of beds:

plan = [4, 9, 9, None, 3, None, 3]   ->  False

Both 3s are cut on the inner side of their 9. Folding puts each 3 opposite the gap where the other half has no bed, so the plan is not symmetric — even though each row of the diagram reads 4, then 9 9, then 3 3. Moving one 3 to the outer side, [4, 9, 9, None, 3, 3, None], makes it True.

Constraints.

• 0 <= number of beds <= 10^4
• 1 <= planting code <= 10^3
• The plan may be one long chain of beds

Hints

Approach

Brute force

Copy the plan, swapping the left and right bed of every node in the copy, then compare the copy with the original node by node. That is correct, and it costs a second set of 10^4 beds plus two full walks for something one walk can settle.

The insight

Ask the question about a pair, not a bed: mirrors(a, b) holds when a and b carry the same code, a's left folds onto b's right, and a's right folds onto b's left.

The fold sends one side onto the other, so the two cursors must always cross: descending left on one means descending right on the other. That crossing is the whole algorithm. The base cases carry the rest — two gaps fold onto each other, and a bed folding onto a gap is exactly the failure the second example shows.

Start the pair at the two beds either side of the central walk. The central bed folds onto itself, so its code never matters.

Algorithm

1. Build the beds from the plan. An empty plan is a mirror.
2. Call mirrors(root.left, root.right).
3. In mirrors(a, b): if both are gaps, return True.
4. If exactly one is a gap, return False.
5. If the codes differ, return False.
6. Otherwise return mirrors(a.left, b.right) and mirrors(a.right, b.left).

Complexity

Time O(n) — each bed appears in exactly one pair, and each pair does constant work. Space O(h) for the recursion, which is O(log n) on a plan cut evenly and O(n) on a chain.

Solution

"""Parterre mirror — walk two cursors down the plan in opposite directions."""

import sys
from collections import deque

sys.setrecursionlimit(20000)   # a plan cut as one long chain is n frames deep


class Bed:
    __slots__ = ("code", "left", "right")

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


def build(plan):
    """Level-order planting plan, None where no bed is cut."""
    if not plan or plan[0] is None:
        return None
    root = Bed(plan[0])
    queue = deque([root])
    i = 1
    while queue and i < len(plan):
        node = queue.popleft()
        if i < len(plan):
            code = plan[i]
            i += 1
            if code is not None:
                node.left = Bed(code)
                queue.append(node.left)
        if i < len(plan):
            code = plan[i]
            i += 1
            if code is not None:
                node.right = Bed(code)
                queue.append(node.right)
    return root


def mirrors(a, b):
    """True when the plan under `a` folds exactly onto the plan under `b`."""
    if a is None and b is None:
        return True
    if a is None or b is None:      # one side has a bed where the other has grass
        return False
    # the fold sends a's left onto b's right: cross the sides on every step
    return a.code == b.code and mirrors(a.left, b.right) and mirrors(a.right, b.left)


def solve(plan):
    root = build(plan)
    if root is None:
        return True
    return mirrors(root.left, root.right)

TESTS = [
    (([4, 9, 9, 3, 7, 7, 3],), True),
    (([4, 9, 9, None, 3, None, 3],), False),
    (([4, 9, 9, None, 3, 3, None],), True),
    (([1, 2, 2, 3, 4, 3, 4],), False),
    (([4, 9, 9, 3, 7, 7, 4],), False),
    (([6],), True),
    (([],), True),
]

Pitfalls

• Comparing a.left with b.left. That tests whether the halves are copies rather than reflections. It returns True for [1, 2, 2, 3, 4, 3, 4], where the halves are identical and the plan plainly does not fold.
• Checking each row of the diagram reads the same backwards. Drop the gaps and the second example's rows are [4], [9, 9], [3, 3], all palindromes, and the answer is still False. The gaps are part of the shape.
• Handling only the both-gaps base case. With one cursor on a bed and the other on a gap, the code reads a planting code off nothing and fails.

Variants

• The bracket, first round first — where reading the plan a row at a time is the right answer rather than the trap.
• The same unit, already there — the same paired comparison, run at every node of a second, larger plan.