The blurred count card

A warden walks the wetland reserve and writes each bird down by its number in the reserve's field guide, straight onto a card, with nothing between the numbers. Then it rains.

The problem

The field guide numbers the reserve's species 1 to 26. A count card is a sequence of those numbers written left to right with no separators, so the card reads as one run of digits. Rain has smudged some marks past reading; a smudged mark is written ?.

A smudged mark is known to be a digit from 1 to 9. The guide's zero is drawn with a stroke through it, and the stroke survives the rain, so every 0 still on the card is certainly a zero and no ? hides one.

Count how many species lists the card could be. A list is any sequence of numbers, each between 1 and 26 inclusive, whose digits written end to end match the card once each ? is replaced by some digit 1 to 9. Give the count modulo 1000000007.

Input. card — a string, each character a digit 0 to 9 or the mark ?.

Output. The number of species lists the card could be, modulo 1000000007.

Example.

card = "1?"   ->  18

Nine lists split the card in two — 1 followed by any of 1 to 9 — and nine keep it whole, as one species from 11 to 19.

A second example, where a blurred mark sits on both sides of a digit:

card = "?2?"   ->  153

Lists whose last species is the final mark alone: 9 × (the 11 readings of ?2). Lists whose last species is a two-digit 2?, which must be 21 to 26: 6 × (the 9 readings of ?). That is 99 + 54.

A third example, where a zero has to be carried:

card = "?0"   ->  2

The zero is not a species and cannot stand alone, so the mark before it must be 1 or 2, giving species 10 or 20.

Constraints.

• 1 <= len(card) <= 10^5
• Every character is a digit 0 to 9 or ?
• The answer is taken modulo 1000000007

Hints

Approach

Brute force

Replace the k smudges with digits in every way and run the ordinary counter on each filled-in card: 9^k · n. With ten smudges that is already 3·10^9 characters of work, and the constraint puts no limit on how many marks the rain takes.

The insight

A blurred mark does not fork the problem, it scales it: each step contributes a fixed number of legal species, so the same two-term recurrence works with counts in place of the yes-or-no test.

Every reading of the first i characters ends with a species covering one character or two, and those two families are disjoint. The one-character family counts single(c) choices for the last mark times the readings of the first i - 1; the two-character family counts pair(b, c) choices times the readings of the first i - 2. Choices at the end are independent of everything to the left, which is exactly what lets the counts multiply.

single(?) = 9    single(0) = 0    single(other digit) = 1

pair(?, ?) = 15        11-19 and 21-26
pair(1, ?) = 9         11-19
pair(2, ?) = 6         21-26
pair(?, d) = 2 if d <= 6 else 1
pair(1, d) = 1
pair(2, d) = 1 if d <= 6 else 0
everything else = 0

Algorithm

1. Set two_back = 1 for the empty prefix and one_back = single(card[0]).
2. For each later position i, compute here = single(card[i]) · one_back + pair(card[i-1], card[i]) · two_back, reduced modulo 1000000007.
3. Shift the pair along: two_back, one_back = one_back, here.
4. Return one_back.

Complexity

Time O(n) — a table lookup, two multiplications and one remainder per mark. Space O(1); two integers, since the recurrence never looks back further than two characters.

Solution

"""The blurred count card — counting DP where a blurred mark multiplies the ways."""

MOD = 1000000007


def single(c):
    """Legal one-character species this mark could be."""
    if c == "?":
        return 9
    return 0 if c == "0" else 1


def pair(b, c):
    """Legal two-character species (10 to 26) this pair of marks could be."""
    if b == "?" and c == "?":
        return 15                       # 11-19 and 21-26
    if b == "?":
        return 2 if c <= "6" else 1     # 1c always, 2c only up to 26
    if c == "?":
        return 9 if b == "1" else (6 if b == "2" else 0)
    if b == "1":
        return 1
    if b == "2":
        return 1 if c <= "6" else 0
    return 0


def solve(card):
    # two_back: readings of the prefix ending two marks ago (empty prefix = 1).
    # one_back: readings of the prefix ending one mark ago.
    two_back, one_back = 1, single(card[0])
    for i in range(1, len(card)):
        # The last species covers one mark or two; the families are disjoint.
        here = single(card[i]) * one_back + pair(card[i - 1], card[i]) * two_back
        two_back, one_back = one_back, here % MOD
    return one_back % MOD

TESTS = [
    (("1?",), 18),
    (("?2?",), 153),
    (("?0",), 2),
    (("??",), 96),
    (("?7",), 10),
    (("30",), 0),
    (("2?6",), 17),
    (("7",), 1),
    (("?" * 20,), 104671669),
]

Pitfalls

• Letting ? stand for a zero as well. single(?) becomes 10 and pair(?, ?) becomes 17, so "??" returns 117 instead of 96. The stroked zero is exactly why the blurred digit runs 1 to 9.
• Giving ? after a digit a flat count. In "?7" the pair can only be 17, because 27 is past the end of the guide, so pair(?, 7) is 1 and the card has 10 readings. Using 2 there returns 11.
• Reducing only at the end. The count for a card of 10^5 marks has tens of thousands of digits; taking the remainder once at the end multiplies numbers thousands of words long. Reduce at every step.

Variants

• The jukebox slip — the same recurrence with every character readable, and the counts collapsed to 0 or 1.
• Tree, digit and bitmask DP — the wider family of scans that walk a number one position at a time.