Readings of the frieze

A stonemason cut a frieze with no spaces between the words. The archive holds the glossary of words the workshop used, and the curator wants every reading the stone admits — not just one.

The problem

The frieze is a single run of lowercase letters, frieze, carved without gaps. The workshop's glossary is a list of distinct lowercase words. A reading is a way of cutting the frieze into a sequence of glossary words, in order, with nothing left over and nothing inserted. A word may be used as often as it appears in the reading — the glossary is a vocabulary, not a stock of tiles.

Return every reading, each written as its words joined by single spaces. Return them sorted alphabetically, so the answer is fixed even when the stone is ambiguous. If the frieze admits no reading, return an empty list.

Input. frieze — a string of lowercase letters. glossary — a list of distinct lowercase words.

Output. A list of strings, every reading of the frieze, sorted alphabetically.

Example.

frieze = "themillrace"
glossary = ["the", "them", "ill", "mill", "race", "millrace"]
->  ["the mill race", "the millrace", "them ill race"]

Three cuts survive. The stone is genuinely ambiguous: nothing in the letters says whether the mason meant the mill and the race, the millrace, or a sentence that starts with them.

A second example, where the tail defeats every start:

frieze = "quarryfloor"
glossary = ["quarry", "floors"]
->  []

The frieze begins with a glossary word, which tempts a greedy cut, but floor is not in the glossary and there is no other way to divide the letters.

Constraints.

• 1 <= len(frieze) <= 20
• 1 <= len(glossary) <= 1000
• 1 <= len(word) <= 10 for every glossary word, all distinct
• Readings are returned sorted alphabetically

Hints

Approach

Brute force

Try every set of cut positions: there are len(frieze) - 1 gaps, so 2 to that power arrangements — 524288 at 20 letters — and check each one word by word. Worse, the recursive version re-derives the readings of the tail once for every route that reaches it, so the same suffix is expanded again and again.

The insight

The set of readings of a suffix depends only on where that suffix starts, so compute it once per position and paste the finished lists together.

Write readings(i) for the readings of the letters from i onward. Any reading of readings(i) is a glossary word covering frieze[i:j] followed by some member of readings(j), and every pairing of those is legal and distinct, because the first word fixes j. That independence is what memoisation needs: the answer for j is the same no matter how the mason reached j.

The base case carries the argument. At the end of the frieze there is exactly one reading — the empty one — so readings(n) is a list holding one empty string. Returning an empty list there would say "no reading", and the emptiness would propagate back to the front and wipe out the answer.

Algorithm

1. Put the glossary in a set and record its longest word.
2. Define readings(i), memoised on i.
3. If i is the end of the frieze, return a list holding the empty string.
4. For each j from i + 1 to i + longest, if frieze[i:j] is in the set, take every reading of j and put the word in front of it.
5. Return readings(0), sorted.

Complexity

Time O(n * L^2) to fill the table — n positions, L candidate words at each, and L characters to cut and hash a word — plus the cost of writing the answer, which can be exponential, because a frieze can genuinely have thousands of readings. Space O(n) memo entries, each holding its own readings.

Solution

"""Readings of the frieze — memoised segmentation returning every reconstruction."""


def solve(frieze, glossary):
    words = set(glossary)
    longest = max(len(w) for w in words) if words else 0
    n = len(frieze)
    memo = {}

    def readings(i):
        # Invariant: readings(i) is every way to read frieze[i:], and it depends
        # on i alone — never on the words already cut off in front of it.
        if i in memo:
            return memo[i]
        if i == n:
            return [""]                    # the empty suffix has one reading
        found = []
        for j in range(i + 1, min(n, i + longest) + 1):
            head = frieze[i:j]
            if head in words:              # the glossary is a vocabulary, not a stock
                for tail in readings(j):
                    found.append(head if tail == "" else head + " " + tail)
        memo[i] = found                    # cached list is never mutated by callers
        return found

    return sorted(readings(0))

TESTS = [
    (("themillrace", ["the", "them", "ill", "mill", "race", "millrace"]),
     ["the mill race", "the millrace", "them ill race"]),
    (("quarryfloor", ["quarry", "floors"]), []),
    (("racerace", ["race"]), ["race race"]),      # one word used twice
    (("stone", ["stone", "ston", "e"]), ["ston e", "stone"]),
    (("a", ["a"]), ["a"]),                        # shortest frieze
    (("chisel", ["hammer"]), []),                 # nothing matches at all
]

Pitfalls

• Returning an empty list at the end of the frieze. The empty suffix has one reading, not none. Return a list containing the empty string, or every reading collapses and a perfectly readable frieze reports [].
• Removing a word once it has been used. Words repeat: "racerace" against ["race"] has the reading "race race". Treat the glossary as a membership test, never as a stock that runs out.
• Joining with a space unconditionally. Prefixing a word to the empty base reading with word + " " + rest leaves "race " with a trailing space, and no reading matches. Join the words, or special-case the empty tail.
• Mutating the memoised list. Appending to the list stored for position j corrupts it for the next caller, and readings start appearing under the wrong prefix.

Variants

• Motif in the weave — the same "consume a prefix, recurse on the rest" table, counting the ways instead of listing them.
• Sluice doses — one number per position rather than a list, which is what you keep when only the best answer matters.