The sundial motto

A mason cuts mottoes around the rim of a sundial. The ones worth commissioning read the same whichever way you walk around the plinth.

The problem

The mason works from a typed line. What ends up in the stone is only the letters and the digits: spaces are left as gaps, punctuation is drawn as decoration above the rim rather than cut into it, and every letter is cut as a capital, so the case in the typed line means nothing.

A motto is reversible when the carved characters, read clockwise, are the same sequence as read anticlockwise. Given the typed line, say whether the carved rim will be reversible. A rim with nothing carved on it counts as reversible — there is nothing to disagree with.

Input. motto — a string of printable ASCII: letters, digits, spaces and punctuation.

Output. True if the carved characters form a reversible sequence, False otherwise.

Example.

motto = "Won't lovers revolt now?"   ->  True

Carved, that is WONTLOVERSREVOLTNOW, which is the same read from either end. The apostrophe and the question mark never reach the stone.

A second example, where the numerals do reach it:

motto = "Dial 3, laid."   ->  True

DIAL3LAID is reversible. Digits are cut like letters, so dropping them — or treating the 3 as decoration — would answer this one wrongly.

motto = "Sun and shade"   ->  False

Constraints.

• 0 <= len(motto) <= 2 * 10^5
• characters are printable ASCII
• comparison is case-insensitive; only letters and digits are carved

Hints

Approach

Brute force

Build a cleaned copy — keep the alphanumerics, lowercase them — then compare it with its reverse. That is correct and costs two extra strings of up to 2 × 10⁵ characters. Worse, comparing by repeated slicing, chopping a character off each end and recursing, copies the whole remainder every step: O(n²) characters touched.

The insight

A reversible sequence is defined pair by pair from the outside in, so two positions walking toward each other decide it without ever building the cleaned string.

The pairing is what makes this work: position i from the front must match position i from the back, and those two are reachable directly. Uncarved characters do not take part in the pairing at all, so each pointer simply steps over them before a comparison is made. The pointers only ever move inward, which is why the whole walk is one pass.

Algorithm

1. Put left at the first character and right at the last.
2. While left < right: advance left past anything not alphanumeric, and retreat right the same way.
3. If left < right still and the two characters differ once lowercased, answer False.
4. Otherwise step both inward and continue.
5. If the pointers meet, answer True.

Complexity

Time O(n) — each pointer moves inward only, so together they cross the line once. Space O(1) — two indices, no copy of the motto.

Solution

"""The sundial motto — two pointers walking inward, skipping uncarved characters."""


def solve(motto):
    left, right = 0, len(motto) - 1
    while left < right:
        # invariant: everything outside [left, right] has already been matched in pairs
        if not motto[left].isalnum():
            left += 1
        elif not motto[right].isalnum():
            right -= 1
        elif motto[left].lower() != motto[right].lower():
            return False
        else:
            left += 1
            right -= 1
    return True

TESTS = [
    (("Won't lovers revolt now?",), True),
    (("Dial 3, laid.",), True),
    (("Sun and shade",), False),
    (("",), True),
    ((".,-!",), True),
    (("aA",), True),
    (("No 12 on",), False),
    (("R",), True),
]

Pitfalls

• Skipping only one side per iteration leaves a pointer parked on a space and compares a gap against a letter, so "a, a" comes back False.
• Filtering to letters only carves DIALLAID out of Dial 3, laid. and still says True, but reads "No 12 on" as reversible, because the letters alone spell NOON. Digits are carved.
• Forgetting to lowercase makes "Aa" a mismatch, since A and a are different characters and the mason cuts only capitals.
• Skipping past right without re-checking left < right compares a character with itself or reads out of range on a line of pure punctuation.

Variants

• The leaded strip — the same symmetry test, applied to every window of a strip to find the longest one that passes.
• Mirrored fills — counts how many stretches pass the test instead of checking one.