Fly-rail cue sheet

Above the stage, three kinds of line hang scenery from the grid. Fly one in under another and release it first, and the two foul each other.

The problem

The fly rail runs three sorts of line: hemp lines, written ( when a piece flies in and ) when it flies out; counterweight lines, [ and ]; and motor lines, { and }. The deputy stage manager types the night's calls as one string in the order they will be called.

A sheet is safe when two rules hold. Every fly-out matches a fly-in of the same sort — a counterweight piece cannot be released on a hemp cue. And a piece may only be flown out when nothing has been flown in on top of it: the line released is always the one most recently brought in and not yet taken out. Anything else crosses two lines over the stage.

Decide whether the sheet is safe. A sheet that ends with a piece still in the air is not safe, and neither is one that calls a release with nothing hanging.

Input. cues — a string over the six characters ()[]{}.

Output. True if the sheet is safe, False otherwise.

Example.

cues = "([]{})"   ->  True

The hemp line flies in, a counterweight piece comes in and goes out, a motor piece comes in and goes out, then the hemp line is released last.

A second example, where the two rules disagree with a simple count:

cues = "([)]"     ->  False

Six characters in, three of each: the totals balance and the depth never goes negative, yet the hemp line is released while the counterweight is hanging beneath it.

Constraints.

• 0 <= len(cues) <= 10^4
• every character is one of (, ), [, ], {, }
• an empty sheet is safe

Hints

Approach

Brute force

Scan for an adjacent matched pair, delete it, and start again; the sheet is safe if this empties it. Each sweep costs O(n) and removes one pair, so a 10⁴-cue sheet does up to 5 × 10³ sweeps — about 5 × 10⁷ character moves, and every deletion rebuilds the string.

The insight

The only line that may be released is the one most recently flown in, so the pieces in the air behave exactly like a stack and one pass over the sheet decides it.

Nesting is what the rail rule describes: a piece hung later sits below one hung earlier, and must come out first. A stack keeps precisely that order, and it keeps the sort of each line as well, which is why it catches ([)] where a depth counter does not. Depth alone knows how many lines hang, never which.

Algorithm

1. Start with an empty stack.
2. For each cue: if it is a fly-in, push it.
3. If it is a fly-out, fail when the stack is empty, and fail when the top is not the matching fly-in for this sort. Otherwise pop.
4. After the last cue, the sheet is safe exactly when the stack is empty.

Complexity

Time O(n) — each character is pushed at most once and popped at most once. Space O(n) — a sheet of nothing but fly-ins holds every one of them.

Solution

"""Fly-rail cue sheet — match every fly-out against the top of a stack."""

PARTNER = {")": "(", "]": "[", "}": "{"}


def solve(cues):
    hanging = []
    for cue in cues:
        if cue in PARTNER:
            # invariant: hanging holds the pieces still in the air, oldest first,
            # so only its last entry may legally be released now
            if not hanging or hanging.pop() != PARTNER[cue]:
                return False
        else:
            hanging.append(cue)
    return not hanging

TESTS = [
    (("([]{})",), True),
    (("([)]",), False),
    (("",), True),
    (("(((",), False),
    (("][",), False),
    (("{[()]}[]",), True),
    ((")",), False),
    (("(]",), False),
]

Pitfalls

• Counting fly-ins and fly-outs passes ([)] and )(. Balance is necessary and not sufficient; the order and the sort both matter.
• Returning True when the loop ends ignores "(((", where three pieces are still in the air. Check that the stack is empty.
• Popping without checking first raises IndexError on "][", a sheet that should quietly answer False.
• Matching sort-blind — popping any fly-in on any fly-out — accepts a motor piece released on a hemp cue.

Variants

• The sundial motto — the other one-pass validity check here, symmetric rather than nested, and needing no stack at all.