Find the total number of ways W, in which a sum S can be reached in N throws of a dice

Question

I was solving this question:

Given there is a 6 sided dice. Find the total number of ways W, in which a sum S can be reached in N throws.

Example:

S = 1, N = 6 => W = 0

S = 6, N = 6 => W = 1

S = 7, N = 6 => W = 6

S = 3, N = 2 => W = 2

How to improve its complexity and make it more readable?

def get_sum_dp(n,s):
    t = [[0 for i in xrange(1,s+2)] for j in xrange(1,n+2)]
    for j in xrange(1,7):
        t[1][j] = 1
    for i in range(2, n+1):
        for j in range(1, s+1):
            for k in range(1,7):
                if k < j:
                    t[i][j] += t[i-1][j-k]
    print t[n][s]    

get_sum_dp(2,8) 

Answer 1

1. Review

1. The sum \$s=0\$ can be reached in \$n=0\$ throws in exactly one way, but:

   >>> get_sum_dp(0, 0)
   Traceback (most recent call last):
     File "<stdin>", line 1, in <module>
     File "cr161002.py", line 32, in get_sum_dp
       t[1][j] = 1
   IndexError: list index out of range
   

2. The name get_sum_dp could be clearer (what does "dp" mean? dynamic programming?). I would use a name like dice_rolls.

3. A docstring would be helpful in understanding what the function does.

4. It's usually more convenient to return a result instead of printing it. This would allow the result to be used in other computations if needed.

5. Instead of

   t = [[0 for i in xrange(1,s+2)] for j in xrange(1,n+2)]
   

   you could write:

   t = [[0] * (s + 1) for _ in xrange(n + 1)]
   

   (It's conventional to use _ for a loop variable whose value is not used.)

6. The initial condition is:

   for j in xrange(1,7):
       t[1][j] = 1
   

   but it would be simpler to use the following initial condition:

   t[0][0] = 1
   

   and change:

   for i in range(2, n+1):
       for j in range(1, s+1):
           if k < j:
   

   to:

   for i in range(1, n+1):
       for j in range(1, s+1):
           if k <= j:
   

   (This also fixes the bug I noted in point 1 above.)

7. In the nested loops:

   for i in range(2, n+1):
       for j in range(1, s+1):
   

   the loop over j goes all the way from 1 to s. But some of this may be wasted, because the sum of i dice must be between i and i * 6. So you could reduce the amount of work by writing:

   for i in range(2, n+1):
       for j in range(i, min(s, i * 6) + 1):
   

8. Similarly, instead of checking k on every loop iteration:

   for k in range(1,7):
       if k < j:
           t[i][j] += t[i-1][j-k]
   

   you could compute the loop bounds in advance:

   for k in xrange(1, min(6, j) + 1):
        t[i][j] += t[i - 1][j - k]
   

2. Revised code

def dice_rolls(n, s):
    """Return the number of ways in which a sum s can be reached in n
    throws of a 6-sided die.
    """
    t = [[0] * (s + 1) for _ in xrange(n + 1)]
    t[0][0] = 1
    for i in xrange(1, n + 1):
        for j in xrange(i, min(s, i * 6) + 1):
            for k in xrange(1, min(6, j) + 1):
                t[i][j] += t[i - 1][j - k]
    return t[n][s]

3. Alternative approach

Dynamic programming builds up a table of solutions to sub-problems from the bottom up (starting with small problems and using those to solve larger problems). But an alternative approach works from the top down, using recursion to compute the sub-problems, and memoization to avoid duplicated work. This often results in clearer code and it is easier to compute only the table entries that you need.

In Python 3.2 or later, you can easily memoize a function using the @functools.lru_cache decorator, like this:

import functools

@functools.lru_cache(maxsize=None)
def dice_rolls(n, s):
    """Return the number of ways in which a sum s can be reached in n
    throws of a 6-sided die.
    """
    if s < n or s > n * 6:
        return 0
    elif n == s == 0:
        return 1
    else:
        return sum(dice_rolls(n - 1, s - i) for i in range(1, 7))

(Python 2.7 lacks functools.lru_cache, but there's a backport package.)

Answer 2

Although t is a matrix, notice that you use only two rows at a time. You could save some space by storing only those two rows.

Working on top of Gareth's optimized solution:

prev = [1] + [0] * s

for i in xrange(1, n + 1):
    current = [0] * (s + 1)
    for j in xrange(i, min(s, i * 6) + 1):
        for k in xrange(1, min(6, j) + 1):
            current[j] += prev[j - k]

    prev = current

return prev[s]

Also, it would be good to add some doctests, for example:

def dice_rolls(n, s):
    """
    >>> dice_rolls(2, 8)
    5

    >>> dice_rolls(6, 6)
    1

    >>> dice_rolls(6, 7)
    6

    >>> dice_rolls(2, 3)
    2

    >>> dice_rolls(6, 1)
    0

    >>> dice_rolls(2, 13)
    0

    >>> dice_rolls(2, 12)
    1

    """

Answer 3

Whenever you have the need for fancy iteration patterns, you should head to the itertools module to check if it can't simplify things.

Here you want to associate each number from 1 to 6 to each number from 1 to 6 to each number... N times. This is what itertools.product provides.

Then you want to sum those numbers and count them.

I would also separate the computation into 2 functions: one to compute the number of different sums when throwing N die (your t variable), and the other one to retrieve the desired result. This will allow you to implement better behaviour such as caching the table for N dice latter if you need to in a more clean manner.

from itertools import product
from collections import Counter


DIE = range(1, 7)


def sums_of_dice(n):
    return Counter(sum(roll) for roll in product(DIE, repeat=n))


def number_of_sums(dice_count, target):
    sums = sums_of_dice(dice_count)
    return sums[target]