Marquee changeover

The marquee over the cinema door spells tonight's title in letter tiles. Tomorrow it must spell a different one, and the usher on the ladder wants the shortest route there.

The problem

The marquee is one row of slots, one letter tile per slot, spelling tonight. It must end up spelling tomorrow. Three moves are available, each counting as one climb of the ladder:

• Swap — replace one tile with a different letter, in the same slot.
• Pull — take a tile out and close the gap; the row loses a slot.
• Slide — open a gap and put a new tile in; the row gains a slot.

Every letter is in stock, so a swap or a slide can produce any tile. Report the fewest moves that turn tonight's row into tomorrow's.

Input. tonight, tomorrow — two strings of lowercase letters.

Output. The smallest number of moves.

Example.

tonight = "matinee", tomorrow = "marquee"  ->  3

Both rows are seven tiles. The m, the a and the two es stay; t, i, n are swapped for r, q, u. Pulling and sliding cannot beat three, because the rows are already the same length.

Example, where the rows are different lengths:

tonight = "usher", tomorrow = "rush"   ->  3
tonight = "",      tomorrow = "reels"  ->  5

Slide an r in at the front to get rusher, then pull the e and the r off the end: three moves. Swaps alone cannot do it, because the rows differ in length. An empty marquee needs one slide per tile.

Constraints.

• 0 <= len(tonight) <= 1000
• 0 <= len(tomorrow) <= 1000
• lowercase letters only; every move costs 1

Hints

Approach

Brute force

Explore sequences of moves: every slot offers 25 swaps, a pull and a slide, so the branching runs to hundreds at a depth of a thousand. Even the reduced version — recurse on the three choices at the last tile — is 3^(n + m) paths, since the same pair of prefixes recurs through every order those moves could have come in.

The insight

Only the two prefix lengths matter: once you say what happens to the last tile, the rest of the job is the same problem on two shorter rows.

The cost still to pay depends on how much of each title is unhandled and on nothing else. Matching last tiles cost nothing and shrink both prefixes at once. Otherwise the answer is one plus the cheapest of three strictly smaller states — swap shrinks both, pull shrinks tonight, slide shrinks tomorrow. Every recursive call is smaller in one of the two indices, so the table fills bottom-up with no cycle.

Algorithm

1. Let cost[i][j] be the moves that turn the first i tiles of tonight into the first j tiles of tomorrow.
2. cost[i][0] = i — pull every tile. cost[0][j] = j — slide every tile.
3. For i, j >= 1: if the tiles match, cost[i][j] = cost[i - 1][j - 1].
4. Otherwise cost[i][j] = 1 + min(cost[i - 1][j - 1], cost[i - 1][j], cost[i][j - 1]), in the order swap, pull, slide.
5. The answer is cost[n][m].
6. Row i reads only row i - 1, so keep two rows rather than the full table.

Complexity

Time O(n · m) — one constant-time cell per pair of prefixes, a million cells at the limits. Space O(min(n, m)), by rolling the table down to two rows and keeping the shorter title along the row.

Solution

"""Marquee changeover — the two-sequence edit table, rolled down to one row."""


def solve(tonight, tomorrow):
    """Fewest tile moves (swap, pull out, slide in) to turn one title into the other."""
    # The table is symmetric in its two arguments, so keep the shorter title
    # along the row and the longer one down the scan.
    if len(tomorrow) > len(tonight):
        tonight, tomorrow = tomorrow, tonight

    # invariant: previous[j] = moves to turn the first i-1 tiles of `tonight`
    # into the first j tiles of `tomorrow`. Row 0 is pure insertion.
    previous = list(range(len(tomorrow) + 1))
    for i, tile in enumerate(tonight, 1):
        row = [i] + [0] * len(tomorrow)          # emptying i tiles costs i pulls
        for j, wanted in enumerate(tomorrow, 1):
            if tile == wanted:
                row[j] = previous[j - 1]         # the tile already reads right
            else:
                row[j] = 1 + min(previous[j - 1],  # swap this tile
                                 previous[j],      # pull this tile out
                                 row[j - 1])       # slide the wanted tile in
        previous = row
    return previous[-1]

TESTS = [
    (("matinee", "marquee"), 3),
    (("usher", "rush"), 3),
    (("popcorn", "unicorn"), 3),
    (("reels", "reels"), 0),
    (("", "reels"), 5),
    (("a", ""), 1),
    (("", ""), 0),
]

Pitfalls

• Charging a mismatch as a pull plus a slide. Dropping the diagonal term leaves a distance that never swaps, and "matinee" to "marquee" costs 6 instead of 3 — the usher replaces three tiles twice over.
• Rolling into one array without saving the diagonal. By the time you read row[j - 1], it already belongs to the current row, so the diagonal is gone. On "matinee" to "marquee" that reports 10, more moves than the marquee has slots.
• Starting the empty row at zero. cost[0][j] = 0 claims a bare marquee already spells anything, so "" to "reels" returns 0 rather than 5, and "usher" to "rush" returns 2.

Variants

• The bead strand mirror — the same match-or-branch table, on one sequence compared with itself and filled over intervals instead of prefix pairs.
• Two sequences — the lesson this table comes from, and the rest of the family that shares its shape.