Project Euler Problem 172

# Statement

How many 18-digit numbers n (without leading zeros) are there such that no digit occurs more than three times in n?

# Solution

In this as in most combinatoric problems I decided to use a Dynamic Programming, top-down with memorization approach.

The base case is determined by the remaining length: If the remaining length is 1 then we just return the number of digits that appear less than 3 times.

If the length is > 1 then the result is the sum of:

• If there are digits that appear twice: The number of combinations of length - 1 where there is 1 more digit that has 3 appearances, 1 less digit that has 2 appearances and the same number of digits with 1 appearances, multiplied by the number of digits that appear twice.
• If there are digits that appear once: The number of combinations of length - 1 where there is number of digits with 3 appearances is the same, 1 more digit that has 2 appearances and 1 less digit that appears once, multiplied by the number of digits that appear once.
• (10 - (number of digits that appear 3 times + number of digits that appear twice + number of digits that appear once)) multiplied by the number of combinations of length - 1 where there is number of digits with 3 appearances is the same, the number of digits that appear twice is the same and 1 more digit that appears once.
```dp_table = {
(1, 5) : 5,
(1, 4) : 6,
(1, 3) : 7,
(1, 2) : 8,
(1, 1) : 9,
(1, 0) : 10,
}

def solve(*args):
if args in dp_table:
return dp_table[args]
if args == 1:
return dp_table[args[:2]]
result = 0
cant = 10 - args
if args:
result += args * solve(args - 1, args + 1, args - 1, args)
cant -= args
if args:
result += args * solve(args - 1, args, args + 1, args - 1)
cant -= args
if cant:
result += cant * solve(args - 1, args, args, args + 1)
dp_table[args] = result
return result

if __name__ == '__main__':
length = 17
result = 9 * solve(length, 0, 0, 1)
print("The result is:", result)
```