Matching the moisture log

A field probe writes one letter an hour. The maintenance rules are written as templates, and the whole log has to fit the template — not merely start with it.

The problem

Each hour the probe records one of three states: d for dry, m for moist, w for wet, so a day's readings are a string of those letters. Rules are written as templates over the same alphabet, plus two markers:

• ? stands for exactly one reading, whatever it is;
• * follows a single symbol — a letter or a ? — and means that symbol repeated zero or more times.

The template must account for the entire log, from the first reading to the last. A template that describes only a prefix does not match.

Input. log — a string over d, m, w, possibly empty. template — a string over the same letters plus ? and *.

Output. True if the template describes the whole log, False otherwise.

Example.

log = "ddw", template = "d*w"   ->  True
log = "dmw", template = "d*w"   ->  False

In the first, d* covers the two dry hours and w covers the last. In the second, nothing in the template can account for the m.

A second example, where the run marker has to give a reading back:

log = "wwd", template = "w*wd"   ->  True

Greedily letting w* swallow both wet hours leaves wd with only d to match, which fails. Taking one hour with w* and one with the literal w works. Also note log = "", template = "d*" is True: zero repetitions is a legal reading of d*.

Constraints.

• 0 <= len(log) <= 1000
• 0 <= len(template) <= 200
• * never appears first in the template and never directly follows another *

Hints

Approach

Brute force

Expand every * into all the repetition counts it could take and compare each literal string to the log. Four run markers over a 1000-hour log admit on the order of 1000^4 expansions, most of them the wrong length before a single letter is compared.

The insight

A run marker is a two-way branch, not a greedy rule: x* either matches nothing and the template moves on two symbols, or it matches this reading and the template stays put — and the whole state is the pair of positions (i, j).

The second half is what makes it fast. Whether log[i:] fits template[j:] does not depend on how the search reached (i, j), so a table of at most (n+1) · (m+1) answers covers every subproblem and the branching collapses to one evaluation per pair.

Algorithm

1. Define matches(i, j): does log[i:] fit template[j:]?
2. If j is past the template, answer True only when i is past the log.
3. Let here be true when i is in range and template[j] is ? or equals log[i].
4. If template[j+1] is *, answer matches(i, j+2) — zero repetitions — or, if here, matches(i+1, j) — one more repetition.
5. Otherwise answer here and matches(i+1, j+1).
6. Cache each (i, j) and return matches(0, 0).

Complexity

Time O(n · m) — one evaluation per position pair, each doing constant work once its two children are known. Space O(n · m) for the cache, plus O(n + m) of recursion depth.

Solution

"""Matching the moisture log — recursive template match, memoised at each split point."""

from functools import lru_cache


def solve(log, template):
    @lru_cache(maxsize=None)
    def matches(i, j):
        # invariant: matches(i, j) is True when log[i:] is exactly what template[j:] describes
        if j == len(template):
            return i == len(log)
        here = i < len(log) and template[j] in (log[i], "?")
        if j + 1 < len(template) and template[j + 1] == "*":
            # two branches: the starred symbol covers no readings at all,
            # or it covers this one and stays available for the next
            return matches(i, j + 2) or (here and matches(i + 1, j))
        return here and matches(i + 1, j + 1)

    answer = matches(0, 0)
    matches.cache_clear()
    return answer

TESTS = [
    (("ddw", "d*w"), True),
    (("dmw", "d*w"), False),
    (("mw", "?w"), True),
    (("wwd", "w*wd"), True),
    (("", "d*"), True),
    (("dddd", "?*"), True),
    (("dmw", "dm"), False),
    (("", ""), True),
    (("d", ""), False),
    (("mmd", "m*?d"), True),
]

Pitfalls

• Consuming the run greedily — matching as many readings as x* can, then moving on — gets "wwd" against "w*wd" wrong, because the last w in the template needs a reading back.
• Reading template[j+1] without the bounds check raises an IndexError on the final symbol of every template.
• Returning True as soon as the template runs out accepts "dmw" against "dm". The log has to be exhausted too.
• Requiring * to match at least one reading rejects log = "" against template = "d*" — the day the field was never dry.

Variants

• Tracing the mosaic — recursion over two coordinates as well, but the state is a path, so it cannot be cached.
• Spending the voucher — branching with a running amount, where the pruning comes from an ordering rather than a cache.