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

Harim

you should re-think the question. you have 20 slots, you need to fill them with numbers from 1-12 such that the 10 slots with the greatest numbers sum will add up to 70. already we can reduce this, you have 10 slots, 1-12 = 70. and then for each solution you have 10 more slots which can be arranged such that none of their values are greater than any value in the solution slots. remember, the question is how many ways can this be done - so each solution 10, has many other slots that can be arranged in MANY different ways. – Horrible

Inbar,.. Initially i tested this code for simialr puzzle where in it was asked for 5 dices and sum of top three should be 15 and how many such combintaions? this code instantly gave out the solution as 1111 which is exactly correct. Now that the complexity has increased to 20 dices and also 12 faced.. it takes so much time.. i need an alternative approach or way it could be solved without brute force. – Harim

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)

Clarance

@Gareth: i would need a little help on solving it via recursion...I tried hard to come up with a recursive way to find the combination of numbers to sum up to 70 for the said problem. I wasnt successful enuf... – Harim

how do u come up with the combination set which would sum to 70 without brute force method... – Harim

I just wrote a whole answer explaining exactly that! – Clarance

Answer 2

this solution should work - not sure how long it will take on your system.

from itertools import product

lg = (p for p in product(xrange(1,13,1),repeat=10) if sum(p) == 70)

results = {}
for l in lg:
    results[l] = [p for p in product(xrange(1,min(l),1),repeat=10)]

what it does is create the "top ten" first. then adds to each "top ten" a list of the possible "next ten" items where the max value is capped at the minimum item in the "top ten"

results is a dict where the key is the "top ten" and the value is a list of the possible "next ten"

the solution (amount of combinations that fit the requirements) would be to count the number of lists in all the result dict like this:

count = 0
for k, v in results.items():    
    count += len(v)

and then count will be the result.

update

okay, i have thought of a slightly better way of doing this.

from itertools import product
import math

def calc_ways(dice, sides, top, total):
    top_dice = (p for p in product(xrange(1,sides+1,1),repeat=top) if sum(p) == total)
    n_count = dict((n, math.pow(n, dice-top)) for n in xrange(1,sides+1,1))

    count = 0
    for l in top_dice:
        count += n_count[min(l)]

    return count

since im only counting the length of the "next ten" i figured i would just pre-calculate the amount of options for each 'lowest' number in "top ten" so i created a dictionary which does that. the above code will run much smoother, as it is comprised only of a small dictionary, a counter, and a generator. as you can imagine, it will probably still take much time.... but i ran it for the first 1 million results in under 1 minute. so i'm sure its within the feasible range.

good luck :)

update 2

after another comment by you, i understood what i was doing wrong and tried to correct it.

from itertools import product, combinations_with_replacement, permutations
import math

def calc_ways(dice, sides, top, total):
    top_dice = (p for p in product(xrange(1,sides+1,1),repeat=top) if sum(p) == total)
    n_dice = dice-top
    n_sets = len(set([p for p in permutations(range(n_dice)+['x']*top)]))
    n_count = dict((n, n_sets*len([p for p in combinations_with_replacement(range(1,n+1,1),n_dice)])) for n in xrange(1,sides+1,1))

    count = 0
    for l in top_dice:
        count += n_count[min(l)]

    return count

as you can imagine it is quite a disaster, and does not even give the right answer. i think i am going to leave this one for the mathematicians. since my way of solving this would simply be:

def calc_ways1(dice, sides, top, total):
    return len([p for p in product(xrange(1,sides+1,1),repeat=dice) if sum(sorted(p)[-top:]) == total])

which is an elegant 1 line solution, and provides the right answer for calc_ways1(5,6,3,15) but takes forever for the calc_ways1(20,12,10,70) problem.

anyway, math sure seems like the way to go on this, not my silly ideas.

Horrible

Thanks Inbar for a quick response but i tried this divide and conquer approach.. Still it takes a long time... – Harim

where u able to get the count in ur system? – Harim

I tried this and it gave the wrong answer (82) for the smaller example in the problem description. – Clarance

Gareth... can u try the code which i've put in the main description. It should give u 1111. import itertools def check(a,b): chk=1 for x in a: if x>b: chk=0 break return chk lst=[] count=0 for x in itertools.product(range(1,6),repeat=5): a=sorted([x[y] for y in range(5)]) if sum(a[-3:])==70 and check(a[:2],min(a[-10:])): count+=1 – Harim

@Inbar: your revised code still gives the wrong answer (82) for the number of ways to roll 5 6-sided dice such that the top 3 sum to 15. – Clarance

@GarethRees i made it into a function - and when i input print calc_ways(5, 6, 3, 15) i get 148 – Horrible

Sorry: yes, you're right: your revised code gives 148 in this case. But the correct answer is 1111. – Clarance

yea 148 is partially correct.. then when u permutate all those 148 and remove the duplicates via final_answer=list(set(answerset)) ==> len(final_answer)=1111 – Harim

@Dshank i'm not sure i quite follow the logic there, could you maybe enlighten me? we could start a chat to facilitate. – Horrible

sure Inbar... no probs.. i'm traveling now.. so will reach u by morning for sure.. the only cases u might 've missed is.. say for example.. one of the combination be [6,3,6,1,2] since u had computed the initial calculation for the computing the top value (15).. the other combinations [1,2,3,6,6] [2,3,6,1,6]...so on.. would 've missed it in the computation – Harim

@Inbar: U got it :) brilliant :) – Harim