The broken dial

An exchange numbers its extensions from 1 up to a known highest. The dial in the porter's lodge has lost buttons, and the porter wants to know how much of the building he can still reach.

The problem

Extensions run 1, 2, 3 and upward to highest, with no leading zeros. The dial has a list of buttons that still work, each a digit from 1 to 9; the 0 button rings the operator and never appears in an extension number. An extension can be dialled when every digit of its number sits on a working button. Buttons do not wear out, so a digit may be used as many times as it appears.

Count how many extensions from 1 to highest the porter can still dial.

Input. buttons — a list of distinct digits from 1 to 9. highest — the largest extension number in the building.

Output. How many integers from 1 to highest are written only with those digits.

Example.

buttons = [1, 3, 5], highest = 250   ->  21

Three extensions of one digit, nine of two digits — 11 through 55 — and nine of three digits. All nine of those begin with 1: an extension starting 3 or 5 is already above 250, and 2 is not on the dial at all.

Example, where the highest extension is itself dialable:

buttons = [2, 4, 7], highest = 4477   ->  84

Thirty-nine extensions below 1000, then 45 with four digits, the last of which is 4477 itself.

Constraints.

• 1 <= len(buttons) <= 9, distinct digits from 1 to 9
• 1 <= highest <= 10^9

Hints

Approach

Brute force

Write out each number from 1 to highest and check its digits against the buttons. With highest at 10^9 that is a billion strings of up to ten characters, roughly 10^10 character tests.

The insight

Every dialable extension is either shorter than highest, and free in all its positions, or the same length, and it drops below highest at exactly one position after matching the prefix.

That "exactly one" is what makes the count a sum with no double counting: the first position where the two numbers differ is unique, so classify each extension by it. After that position, every remaining position takes any of the k working buttons, which is k to the power of the positions left. The prefix can only be matched while each of its digits is on the dial — the moment highest uses a missing digit, no longer prefix exists.

Algorithm

1. Let k be the number of working buttons and n the digit count of highest.
2. Add k ** L for every length L from 1 to n - 1.
3. Walk the digits of highest from the left, at position i.
4. Count the buttons strictly below that digit and add that many times k ** (n - 1 - i).
5. If that digit is not on the dial, stop and return the running total.
6. If the walk reaches the end, add 1 for highest itself.

Complexity

Time O(n · k) where n is at most 10 digits and k at most 9 — about ninety steps, whatever the size of highest. Space O(k) for the sorted buttons.

Solution

"""The broken dial — extensions at most N spelled from the working buttons."""


def solve(buttons, highest):
    """How many of 1..highest use only digits that still have a button."""
    working = sorted(str(b) for b in set(buttons))
    k = len(working)
    bound = str(highest)
    n = len(bound)

    total = 0
    for length in range(1, n):
        total += k ** length              # shorter extensions: every position free

    for i, digit in enumerate(bound):
        lower = sum(1 for b in working if b < digit)
        # prefix matched so far, this position strictly below the bound,
        # every later position free: each extension counted at exactly one i
        total += lower * k ** (n - 1 - i)
        if digit not in working:
            return total                  # no extension can match the prefix any further
    return total + 1                      # the walk finished, so highest itself dials

TESTS = [
    (([1, 3, 5], 250), 21),
    (([2, 4, 7], 4477), 84),              # the bound itself is dialable: the +1 matters
    (([6], 1000000), 6),
    (([1, 2, 3, 4, 5, 6, 7, 8, 9], 999), 819),
    (([5], 4), 0),                        # every button is above the bound
    (([3], 3), 1),
]

Pitfalls

• Dropping the final +1. When the walk gets through every digit, highest itself is dialable and has been counted nowhere else: the second example returns 83 instead of 84.
• Carrying on past a digit that is not on the dial. With buttons [1, 3, 5] and highest = 250, continuing past the 2 counts extensions like 213 that begin with a digit the porter cannot press at all.
• Comparing an integer digit with a character. Keep the buttons and the digits of highest in one type; mixing them either raises an error or, worse, compares against a code point and returns a plausible wrong number.
• Starting the shorter-length sum at L = 0. The empty number is not extension 0, and the count begins at 1.

Variants

• Bays the reader flags — the same left-to-right walk of a bound, with a state that remembers which digits the prefix has already used.
• Tree, digit and bitmask DP — the constraints that announce a digit scan, and the shape it always takes.