Booth changeover run

The spray booth costs twenty minutes to purge between colours, and the shop has a chart saying which colour follows which. Today's queue arrived in the wrong order.

The problem

Each colour the booth sprays has a one-letter code. The changeover chart is a string of distinct codes giving the order the booth runs them in — lightest pigment first, so a purge is needed once per colour. The chart is not alphabetical; it is whatever the paint chemistry says.

Today's queue is a string of codes, one character per job, and codes repeat because several jobs want the same colour. Some jobs use a code that is not on the chart at all — a one-off custom mix.

Reorder the queue so that whenever two jobs both use charted colours, they run in the chart's order. Unlisted jobs run last, and among themselves keep the order they stood in the queue, because that is the order the paperwork was filed.

Input. chart — a string of distinct lowercase colour codes, the booth's running order. queue — a string of lowercase colour codes, one character per job.

Output. The reordered queue as a string.

Example.

chart = "kmr", queue = "rkkmwr"   ->  "kkmrrw"

The chart runs khaki, then maroon, then red. The queue holds two khaki, one maroon, two red and one unlisted white, so the run is kk, m, rr, then the white job at the end.

A second example, where the chart deliberately disagrees with the alphabet:

chart = "adnb", queue = "zabcdn"  ->  "adnbzc"

Blue (b) runs last of the charted colours, not second. The unlisted z and c follow, and z stays ahead of c because it stood ahead of it in the queue.

Constraints.

• 0 <= len(chart) <= 26, all codes distinct lowercase letters
• 0 <= len(queue) <= 2 * 10^5, lowercase letters, repeats allowed
• codes in queue need not appear in chart

Hints

Approach

Brute force

Sort the queue with a comparator that searches the chart on every comparison. A sort makes about n log2 n comparisons — 3.5 × 10⁶ for 2 × 10⁵ jobs — and each runs an interpreted function that scans up to 26 chart characters twice.

The insight

The chart is a function from code to position, so compute that position once per job and sort on the number.

A key runs n times, not once per comparison, and the number it returns carries the whole custom alphabet. Unlisted codes need a position too: give them len(chart), one past every charted code, and they land at the end. They all share that key, and a stable sort leaves equal keys in input order — exactly the tie-break the paperwork asks for.

Algorithm

1. Build rank, a dict from each chart code to its index.
2. Sort the queue's characters with key rank.get(code, len(chart)).
3. Join the sorted characters back into a string.

Complexity

Time O(n log n) for the sort over n jobs, plus O(26) to build the rank. Space O(n) for the sorted list before it is joined.

Solution

"""Booth changeover run — turn the changeover chart into a rank and sort by it."""


def solve(chart, queue):
    rank = {code: i for i, code in enumerate(chart)}
    # Every uncharted code gets the same rank, len(chart), which parks it behind
    # all charted work. Timsort is stable, so codes sharing that rank come out
    # in the order they stood in the queue.
    return ''.join(sorted(queue, key=lambda code: rank.get(code, len(chart))))

TESTS = [
    (('kmr', 'rkkmwr'), 'kkmrrw'),
    (('adnb', 'zabcdn'), 'adnbzc'),
    (('kmr', ''), ''),
    (('kmr', 'wwzz'), 'wwzz'),
    (('', 'brb'), 'brb'),
    (('bgp', 'pppp'), 'pppp'),
    (('qwerty', 'ytrewq'), 'qwerty'),
]

Pitfalls

• rank.get(code, -1) for unlisted codes puts the custom mixes first. The queue "zabcdn" would come out "zcadnb" — the booth purges before it has sprayed anything.
• Calling chart.index(code) inside a comparator raises ValueError the moment an unlisted code is compared, and re-scans the chart on every one of the ~3.5 × 10⁶ comparisons even when it does not.
• Sorting set(queue) silently drops duplicate jobs: "rkkmwr" becomes "kmrw" and three jobs never get sprayed.
• Sorting the unlisted codes among themselves breaks the filing order: they must all compare equal, and stability does the rest.

Variants

• Festival jury ballots — the same idea when one number per element is not enough and the key becomes a tuple.
• Order as a key — the lesson behind this, including why a key beats a comparator by a factor of twenty.