Stamping the key blanks

A locksmith stamps a serial on every blank that leaves the bench, and the head cannot press the same digit twice on one blank. How many serials does that leave?

The problem

Blanks are numbered from zero upwards in ledger order: 0, 1, 2, and so on. The stamping head has digits positions, so the ledger runs from 0 to 10**digits - 1 — with two positions, 0 through 99. Leading zeros are never pressed, so blank 7 carries one stamped digit, not 07.

The head holds one die per digit and each die can be loaded only once, so a serial that uses the same digit twice cannot be pressed and the blank is scrapped. 121 is scrapped. 120 is fine.

Count the serials in the ledger range that survive: how many of the numbers from 0 to 10**digits - 1 have no digit appearing more than once.

Input. digits — a non-negative integer, the number of positions on the head.

Output. How many numbers in 0 .. 10**digits - 1 use no digit twice.

Example.

digits = 2  ->  91

A hundred serials, 0 through 99. The nine that fail are 11, 22, and so on up to 99; every other serial has two different digits, or only one.

Example, adding a position and taking the head away entirely:

digits = 3  ->  739
digits = 0  ->  1

Three positions keeps all 91 of the shorter serials and adds 648 three-digit ones: 9 choices for the leading digit, then 9 (zero is available again), then 8. With no positions at all the ledger holds only the blank stamped 0.

Constraints.

• 0 <= digits <= 12
• the head carries ten dies, one per digit 0–9
• the answer never exceeds 8,877,691, so ordinary integers are enough

Hints

Approach

Brute force

Walk every number from 0 to 10**digits - 1, split it into its digits, and look for a repeat with a set. That is 10^digits numbers, each costing up to digits work — ten billion numbers at ten positions, and a hundred times worse at twelve.

The insight

The number of ways to finish a serial depends only on how many positions are already filled, never on which digits went into them.

Whatever three distinct digits you have pressed, exactly seven dies remain, so every partial serial of the same length has the same number of continuations. That is the precondition a counting DP needs: partial states collapse into classes, and one number per class replaces the enumeration. Lengths are independent because every serial has exactly one length.

Algorithm

1. Start the total at 1, for the serial 0.
2. Serials of exactly one digit: nine of them, 1 through 9.
3. For k from 2 to min(digits, 10), set exact[k] = exact[k - 1] * (11 - k) — one die fewer each time a position is added.
4. Add each exact[k] into the total.
5. Stop at k = 10. With eleven positions some digit must repeat, so a longer head adds nothing.

Complexity

Time O(min(digits, 10)), which is constant — at most ten multiplications, whatever digits is. Space O(1), because only the running total, the current group and the free-die count are kept.

Solution

"""Stamping the key blanks — counting distinct-digit codes one length at a time."""


def solve(digits):
    """How many of 0 .. 10**digits - 1 stamp with no digit used twice."""
    if digits == 0:
        return 1                       # the ledger holds only the blank stamped 0

    # total starts with the ten one-position codes: 0 itself plus 1..9.
    # exact = codes of the current length; free = digits still unused after the
    # positions already fixed, which is the same number for every such code.
    total, exact, free = 10, 9, 9
    for _ in range(2, min(digits, 10) + 1):
        exact *= free                  # invariant: exact counts codes of this exact length
        free -= 1
        total += exact
    return total

TESTS = [
    ((0,), 1),
    ((1,), 10),
    ((2,), 91),
    ((3,), 739),
    ((10,), 8877691),
    ((13,), 8877691),
]

Pitfalls

• Mishandling the serial 0. Seeding the total with 1 for it and then also counting ten one-digit serials returns 11 for digits = 1 instead of 10; and a loop that runs from k = 1 returns 0 for digits = 0, when the range 0 to 0 holds exactly one blank.
• Letting the leading position take a zero. 10 * 9 * 8 gives 720 three-digit serials instead of 648, and a total of 811. The first die comes from 1–9; zero rejoins from the second position onwards.
• Returning only the full-length serials. 648 answers a different question. The ledger starts at 0, so every shorter serial is in the range too.

Variants

• Reading the punch tape — the same collapse of every prefix of one length into a single value, except the value is a yes-or-no rather than a count.
• The knapsack family — where the class a partial state falls into is a running total rather than a length.