Project Euler Problem 164

Statement

How many 20 digit numbers n (without any leading zero) exist such that no three consecutive digits of n have a sum greater than 9?

Solution

Typical DP problem, the base cases are when length is 1, and the possibilities is 10 minus the sum of the last 2 digits.

from itertools import product
 
d = {}
 
for i in range(0, 10):
    for j in range(0, 10):
        d[(1, i, j)] = 10 - i
 
def solve(*args):
    if args in d:
        return d[args]
    l, sum_last, last_dig = args
    result = 0
    for i in range(0, 10 - sum_last):
        result += solve(l - 1, last_dig + i, i)
    d[args] = result
    return result
 
if __name__ == '__main__':
    result = 0
    for t in filter(lambda x: x[0] < 10, 
                    map(lambda t: (sum(t), t[1]), 
                        product(range(1, 10), range(0, 10))
                        )
                    ):
        tmp = solve(18, *t)
        result += tmp
    print("The result is:", result)

The Python file is available for download here.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License