Project Euler 240: number of ways to roll dice

Question

I 'm trying to solve Project Euler problem 240:

In how many ways can twenty 12-sided dice (sides numbered 1 to 12) be rolled so that the top ten sum to 70?

I've come up with code to solve this. But it really takes a lot of time to compute. I know this approach is pretty bad. Can someone suggest me how I can fix this code to perform better?

import itertools
def check(a,b):   # check all the elements in a list a, are lesser than or equal to value b
    chk=0
    for x in a:
        if x<=b:
            chk=1
    return chk

lst=[]
count=0
for x in itertools.product(range(1,13),repeat=20):
    a=sorted([x[y] for y in range(20)])
    if sum(a[-10:])==70 and check(a[:10],min(a[-10:])):
        count+=1

Below code is for the problem defined in the description of the problem. It works perfectly and gives the exact solution....

import itertools
def check(a,b):
     chk=1
     for x in a:
         if x>b:
             chk=0
             break
     return chk


count=0
for x in itertools.product(range(1,7),repeat=5):
    a=sorted([x[y] for y in range(5)])
    if sum(a[-3:])==15 and check(a[:2],min(a[-3:])):
        count+=1

Answer 1

It's no good iterating over all possibilities, because there are 12²⁰ = 3833759992447475122176 ways to roll 20 twelve-sided dice, and at, say, a million rolls per second, that would take millions of years to complete.

The way to solve this kind of problem is to use dynamic programming. Find some way to split up your problem into the sum of several smaller problems, and build up a table of the answers to these sub-problems until you can compute the result you need.

For example, let T(n, d, k, t) be the number of ways to roll n d-sided dice so that the top k of them sum to t. How can we split this up into sub-problems? Well, we could consider the number of dice, i, that roll d exactly. There are ⁿC_i ways to choose these i dice, and T(n − i, d − 1, ...) ways to choose the n − i remaining dice which must roll at most d − 1. (For some suitable choice of parameters for k and t which I've elided.)

Take the product of these, and sum it up for all suitable values of i and you're done. (Well, not quite done: you have to specify the base cases, but that should be easy.)

The number of sub-problems that you need to compute will be at most (n + 1)(d + 1)(k + 1)(t + 1), which in the Project Euler case (n = 20, d = 12, k = 10, t = 70) is at most 213213. (In practice, it's much less than this, because many branches of the tree reach base cases quickly: in my implementation it turns out that the answers to just 791 sub-problems are sufficient to compute the answer.)

To write a dynamic program, it's usually easiest to express it recursively and use memoization to avoid re-computing the answer to sub-problems. In Python you could use the @functools.lru_cache decorator.

So the skeleton of your program could look like this. I've replaced the crucial details by ??? so as not to deprive you of the pleasure of working it out for yourself. Work with small examples (e.g. "two 6-sided dice, the top 1 of which sums to 6") to check that your logic is correct, before trying bigger cases.

def combinations(n, k):
    """Return C(n, k), the number of combinations of k out of n."""
    c = 1
    k = min(k, n - k)
    for i in range(1, k + 1):
        c *= (n - k + i)
        c //= i
    return c

@lru_cache(maxsize=None)
def T(n, d, k, t):
    """Return the number of ways n distinguishable d-sided dice can be
    rolled so that the top k dice sum to t.

    """
    # Base cases
    if ???: return 1
    if ???: return 0

    # Divide and conquer. Let N be the maximum number of dice that
    # can roll exactly d.
    N = ???
    return sum(combinations(n, i)
               * T(n - i, d - 1, ???)
               for i in range(N + 1))

With appropriate choices for all the ???, this answers the Project Euler problem in a few milliseconds:

>>> from timeit import timeit
>>> timeit(lambda:T(20, 12, 10, 70), number=1)
0.008017531014047563
>>> T.cache_info()
CacheInfo(hits=1844, misses=791, maxsize=None, currsize=791)