Setting the folios

A letterpress shop sets each page number by hand out of a type case, one figure at a time. The foreman wants the count before the run starts, not after.

The problem

A compositor sets the folio — the page number — at the foot of every page. The figures come from a type case with a compartment per figure, 0 to 9, and every figure lifted is one more use of that compartment. Folios are set the way they are written, with no leading zeros: page 5 is one figure, not 005.

The shop is about to print a book whose pages run from first_page to last_page inclusive. For one figure the foreman names, count how many times it is lifted from the case across the whole run.

Input. first_page and last_page — the ends of the run, inclusive. digit — the figure being counted, 0 to 9.

Output. How many times that figure appears across all folios in the run.

Example.

first_page = 1, last_page = 20, digit = 2   ->  3

Pages 2, 12 and 20 each take one 2, and no other folio in the run uses one.

A second example, on the figure with the extra rule:

first_page = 95, last_page = 105, digit = 0   ->  7

Page 100 takes two zeros and pages 101 to 105 one each. Pages 95 to 99 take none — a zero that is only a leading zero is never set in type.

Constraints.

• 1 <= first_page <= last_page <= 10^12
• 0 <= digit <= 9

Hints

Approach

Brute force

Spell out every page in the run and count the figure in each — up to 10^12 spellings, one pass per page.

The insight

Write the bound's figures left to right, and the only thing separating one half-built folio from another is whether it is still level with the bound — below it, every completion is the same free block of numbers.

Two half-built folios agreeing on the position reached, on whether they are still level with the bound, and on whether a nonzero figure has been set yet have exactly the same legal completions, so they share one answer. That is 12 positions times 2 times 2 states, each settled by trying ten figures. The started flag exists only because of leading zeros: it changes the count for the figure 0 and nothing else.

Algorithm

1. Write count(page) for the uses of digit across folios 1 to page. The answer is count(last_page) - count(first_page - 1).
2. Break page into its figures.
3. Define scan(pos, level, started) returning a pair: how many folios finish from here, and how many of digit they use between them.
4. At pos try each figure up to the bound's figure while still level, up to 9 once below it. Recurse and add both halves of the pair.
5. When the chosen figure is digit and the folio has started, add the number of completions — that one position costs a piece of type per folio beneath it.
6. Memoise on (pos, level, started); at the end of the figures return one folio and zero uses.

Complexity

Time O(len x 10) — twelve positions, four state combinations, ten figures each: under 500 steps per bound. Space O(len) — four memo entries per position, and a recursion as deep as the number is long.

Solution

"""Setting the folios — digit DP across the positions of a page number."""

from functools import lru_cache


def sorts_up_to(page, digit):
    """How many pieces of `digit` type the folios 1..page consume."""
    if page <= 0:
        return 0
    figures = [int(c) for c in str(page)]

    @lru_cache(maxsize=None)
    def scan(pos, tight, printing):
        # returns (how many folios finish from this state, how many `digit`s they use)
        if pos == len(figures):
            return 1, 0
        top = figures[pos] if tight else 9
        folios = uses = 0
        for figure in range(top + 1):
            # a leading zero is not set in type, so it is not a use of digit 0
            inked = printing or figure > 0
            below, spent = scan(pos + 1, tight and figure == top, inked)
            folios += below
            uses += spent
            if inked and figure == digit:
                uses += below      # this position costs one piece per folio below it
        return folios, uses

    return scan(0, True, False)[1]


def solve(first_page, last_page, digit):
    # invariant: a prefix count is exact, so a range is the difference of two.
    return sorts_up_to(last_page, digit) - sorts_up_to(first_page - 1, digit)

TESTS = [
    ((1, 20, 2), 3),
    ((1, 20, 0), 2),
    ((1, 100, 1), 21),
    ((1, 100, 0), 11),
    ((95, 105, 0), 7),
    ((7, 7, 7), 1),
    ((1000, 1000, 0), 3),
    ((1, 999999, 7), 600000),
    ((1, 10**12, 9), 1200000000000),
]

Pitfalls

• Counting leading zeros as set figures. Drop the started flag and pages 1 to 9 behave like 000000000001, so the figure 0 over pages 1 to 20 comes back in the hundreds instead of 2, which is pages 10 and 20.
• Subtracting count(first_page) rather than count(first_page - 1). That throws away the first page's own figures: page 7 to page 7 on the figure 7 reports 0 instead of 1.
• Sharing one memo across the two bounds. The table is keyed on positions of one specific number, so reusing it mixes two lengths of folio. Build a fresh memo per bound, and return 0 outright when the bound falls below 1.

Variants

• The clean round bonus — another count carried through a small state, a flag and a run length instead of positions.
• Tree, digit and bitmask DP — the shape this belongs to, and the constraints that announce it.