The pier ticker

An LED ticker on the pier scrolls one message on a loop. A visitor has a handful of photographs of it, each catching a few letters, and wants the shortest message they could all have come from.

The problem

Each photograph caught a run of consecutive characters from the board, so every photograph is a contiguous piece of the message. The photographs are all different, and none of them appears inside another. Nothing records the order they were taken in, or where on the board each one sat.

Rebuild the shortest message that contains every photographed fragment as a contiguous run. If several messages are equally short, return the alphabetically first of them.

Input. photos — a list of uppercase strings, the fragments.

Output. The shortest string containing every fragment; ties broken alphabetically.

Example.

photos = ["QUAY", "AYSIDE", "SIDESHOW"]   ->  "QUAYSIDESHOW"

QUAY and AYSIDE share the AY; AYSIDE and SIDESHOW share the SIDE. Laid end to end the three would run to 18 characters; overlapped, 12.

A second example, where the answer's order is not the order the photos arrived in:

photos = ["ATNINE", "LASTRIDE", "RIDEAT"]   ->  "LASTRIDEATNINE"

Splicing them as given produces ATNINELASTRIDEAT, 16 characters, because ATNINE shares nothing with LASTRIDE. Rearranged, LASTRIDE gives up RIDE to the next fragment and RIDEAT gives up AT, for 14.

Constraints.

• 1 <= len(photos) <= 12
• 1 <= len(photos[i]) <= 20
• Fragments are uppercase A–Z, all distinct, and no fragment is contained in another

Hints

Approach

Brute force

Try every ordering and splice each with maximum overlaps. Twelve fragments give 12! = 479,001,600 orderings, each costing eleven splices over strings up to 240 characters long — some 10^10 character copies.

The insight

What the next splice saves depends only on the fragment you just placed, never on the order of the ones before it — so the state is (set placed, last placed), and 479 million orderings collapse to 2^12 · 12 = 49,152 states.

The overlap between two fragments is a property of that pair alone. Everything the past contributes to the future is therefore two things: which fragments are still owed, and which one the message currently ends with. Two partial messages with the same pair accept identical continuations, so keeping only the better one is safe. "Better" is shorter first, then alphabetically first — and that second rule survives, because the continuation appends the same characters to both, and two equal-length strings keep their order when the same tail is added.

The ordering argument is what makes the whole thing legal: because no fragment lies inside another, ranking the fragments by their position in the true message gives a strict order in which each one only overlaps its neighbour, so the shortest message really is some permutation spliced together.

Algorithm

1. Precompute saving[i][j], the longest suffix of fragment i that is also a prefix of fragment j.
2. Seed the table: the message for the one-fragment set i ending at i is fragment i itself.
3. Sweep masks in increasing numeric order — adding a fragment only ever raises the mask, so every state is finished before it is read.
4. For each filled state and each fragment j not yet placed, append photos[j] minus its shared head, and keep it if it beats what is stored for the larger set ending at j: shorter, or the same length and alphabetically earlier.
5. Answer: the best entry over the full mask.

Complexity

Time O(2^n · n² · L) — 49,152 states, twelve extensions each, every splice copying up to n·L = 240 characters. Space O(2^n · n · L) for the stored messages, a few megabytes at these bounds.

Solution

"""The pier ticker — bitmask DP over the set of photographed fragments already spliced."""


def shared(head, tail):
    """Longest suffix of head that is also a prefix of tail."""
    for k in range(min(len(head), len(tail)), 0, -1):
        if head.endswith(tail[:k]):
            return k
    return 0


def solve(photos):
    n = len(photos)
    if n == 0:
        return ""

    saving = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if i != j:
                saving[i][j] = shared(photos[i], photos[j])

    full = (1 << n) - 1
    # best[mask][i] = the shortest, then alphabetically first message that shows
    # every fragment in mask and ends with fragment i. Whatever gets appended
    # later depends only on i, so a message that wins here wins for good:
    # equal-length prefixes keep their order once the same tail is added.
    best = [[None] * n for _ in range(full + 1)]
    for i in range(n):
        best[1 << i][i] = photos[i]

    # A mask only ever grows, so plain increasing order visits every state
    # after the states it was built from.
    for mask in range(full + 1):
        row = best[mask]
        for i in range(n):
            so_far = row[i]
            if so_far is None:
                continue
            for j in range(n):
                bit = 1 << j
                if mask & bit:
                    continue
                grown = so_far + photos[j][saving[i][j]:]
                slot = best[mask | bit]
                if slot[j] is None or (len(grown), grown) < (len(slot[j]), slot[j]):
                    slot[j] = grown

    return min((msg for msg in best[full] if msg is not None), key=lambda m: (len(m), m))

TESTS = [
    ((["QUAY", "AYSIDE", "SIDESHOW"],), "QUAYSIDESHOW"),
    ((["ATNINE", "LASTRIDE", "RIDEAT"],), "LASTRIDEATNINE"),
    ((["HALT"],), "HALT"),                              # one photo is the message
    ((["FOG", "PIER"],), "FOGPIER"),                    # nothing overlaps: tie on length
    ((["ICES", "ESTAND", "CEST"],), "ICESTAND"),        # CEST lands between the other two
    ((["AABAA", "BAAB", "BABBA"],), "BABBAABAA"),       # biggest overlap first loses
]

Pitfalls

• Computing the overlap the wrong way round. The saving when j follows i is a suffix of i matching a prefix of j; swapping the two gives LASTRIDEATNINE a different length and the wrong winner.
• Splicing greedily by the biggest overlap. With ["AABAA", "BAAB", "BABBA"] that merges the first two on their three shared characters and finishes at ten, while "BABBAABAA" does it in nine.
• Storing lengths only. The table then knows the answer is 14 characters long but cannot print it; either keep the strings, or record which fragment each state came from so the message can be walked back.
• Assuming every fragment shows up at a splice point. In ["ICES", "ESTAND", "CEST"] the answer is "ICESTAND", and CEST sits entirely inside the join between the other two.

Variants

• Paying by the tray — the order is fixed there, which is exactly what drops the state from a set to a prefix.
• The espalier weave — another state that remembers the last step taken, but with no set to carry.