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[0] == 1: return dp_table[args[:2]] result = 0 cant = 10 - args[1] if args[2]: result += args[2] * solve(args[0] - 1, args[1] + 1, args[2] - 1, args[3]) cant -= args[2] if args[3]: result += args[3] * solve(args[0] - 1, args[1], args[2] + 1, args[3] - 1) cant -= args[3] if cant: result += cant * solve(args[0] - 1, args[1], args[2], args[3] + 1) dp_table[args] = result return result if __name__ == '__main__': length = 17 result = 9 * solve(length, 0, 0, 1) print("The result is:", result)

The Python file is available for download here.