Mirror panels

A double-glazed panel that reads differently from behind is scrap. Every legal way to cut the rail has to be on paper before the saw starts.

The problem

A sign shop lays a word out in letter tiles, one letter each, left to right along a rail. Before shipping the rail is cut into panels: a panel is a run of consecutive tiles, and every tile ends up in exactly one panel.

The panels are glazed on both faces, so a panel is usable only when its letters read the same forwards and backwards: oo and nun are fine, on is not. A one-tile panel always passes, so every rail has at least one legal plan.

List every legal cut plan. A plan is its panels in rail order.

Input. strip — lowercase letters, the tiles in rail order.

Output. Every legal plan, a list of panel strings in rail order. The plans may come in any order.

Example.

strip = "aab"   ->  [["a", "a", "b"], ["aa", "b"]]

Two plans. Neither ab nor aab reads the same both ways, so the b is always alone.

A second example, where the whole rail survives as one panel:

strip = "noon"  ->  [["n","o","o","n"], ["n","oo","n"], ["noon"]]
strip = "abc"   ->  [["a","b","c"]]

no, noo and oon all fail, which kills every other cut of noon. A rail with no repeated letters has one plan, the all-singles one.

Constraints.

• 1 <= len(strip) <= 16
• lowercase letters only
• sixteen identical tiles give 2¹⁵ = 32,768 plans, the most possible

Hints

Approach

Brute force

Each of the n − 1 gaps is cut or not, so build all 2ⁿ⁻¹ plans and check every panel of each. For sixteen tiles that is 32,768 plans of up to sixteen panels, around 260,000 mirror tests. On abcdefghijklmnop all but one plan is rejected, most of them doomed by their first panel — which the check reaches only after building the rest.

The insight

Test the first panel before cutting the rest: if the prefix does not read the same both ways, no plan that starts with it can be legal, so the whole subtree under it is skipped.

The prune is sound because the panels tile the rail without overlapping: whether strip[start:end] is a mirror does not depend on where the later cuts fall. That independence is the precondition, and it is what lets one failed test delete a branch rather than a plan. The enumeration is the brute force's, minus the dead branches.

Algorithm

1. cut_from(start) — record every legal plan for strip[start:], given the panels already in the buffer.
2. If start is past the last tile, append a copy of the buffer and return.
3. For end from start + 1 to len(strip) inclusive, take piece = strip[start:end].
4. If piece is not a mirror, move to the next end.
5. Otherwise append it, call cut_from(end), then pop it.

Complexity

Time O(n · 2ⁿ) — at most 2ⁿ⁻¹ plans, each panel tested in O(n) and each plan copied in O(n). Space O(n) for the stack and the panel buffer, ignoring the output.

Solution

"""Mirror panels — every cut of a tile rail into panels that read both ways."""


def is_mirror(strip, start, end):
    """True when strip[start:end] reads the same in both directions."""
    left, right = start, end - 1
    while left < right:
        if strip[left] != strip[right]:
            return False
        left += 1
        right -= 1
    return True


def solve(strip):
    plans = []
    panels = []

    def cut_from(start):
        # invariant: `panels` tiles strip[:start] exactly, with no overlap and
        # no gap, and every panel already in it is a mirror.
        if start == len(strip):
            plans.append(list(panels))
            return
        for end in range(start + 1, len(strip) + 1):
            if not is_mirror(strip, start, end):
                continue            # dead prefix: every plan starting here fails
            panels.append(strip[start:end])
            cut_from(end)           # end, not start + 1: panels must not overlap
            panels.pop()

    cut_from(0)
    return plans

TESTS = [
    (("aab",), [["a", "a", "b"], ["aa", "b"]]),
    (("noon",), [["n", "o", "o", "n"], ["n", "oo", "n"], ["noon"]]),
    (("abc",), [["a", "b", "c"]]),          # no repeats: one plan, all singles
    (("a",), [["a"]]),                       # a single tile is its own panel
    (("aaa",), [["a", "a", "a"], ["a", "aa"], ["aa", "a"], ["aaa"]]),
]

Pitfalls

• Recursing from start + 1 instead of end. The next panel starts inside the one just taken, so panels overlap and no longer spell the rail: "noon" gives four plans, among them ["noon", "o", "o", "n"] — seven tiles from a rail of four.
• Looping end over range(start + 1, len(strip)). The last tile is never the end of a panel, so no plan reaches the base case and every input answers with [].
• Appending the live buffer rather than a copy. Every plan aliases one list, which the pops empty on the way out, so the answer is a stack of empty plans.

Variants

• Tasting flight — yes-or-no decisions too, but with nothing to reject and so nothing to prune.
• Pruning — the lesson on what a feasibility test is worth.