Sum of several dice

With many dice the sample space is too large to list, but the counts can be built up one die at a time.

What to build

A program that finds how many outcomes of N dice add up to S.

Requirements

  • Print ways W (outcomes of N fair dice with sum S), outcomes O (6 to the power N) and probability P as a reduced fraction (0 when it is impossible).
  • It must finish quickly for 8 dice.

Input

One line: N and S.

Output

Three lines.

Constraints

1 ≤ N ≤ 8; 0 ≤ S ≤ 60.

Example

Input:

2 7

Output:

ways 6
outcomes 36
probability 1/6

Why it works

The number of ways to reach a sum with one more die is the sum of the ways to reach the six smaller sums, so the table grows die by die without listing 1.7 million outcomes.

Examples

Example 1 · Input
2 7
Expected output
ways 6
outcomes 36
probability 1/6
Example 2 · Input
3 10
Expected output
ways 27
outcomes 216
probability 1/8

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Listing 6⁸ outcomes is too slow. Build the counts one die at a time: ways[s] for the dice so far.

Hint 2

Adding a die: new[s + f] += ways[s] for every face f from 1 to 6.

Solution

Show one correct solution (try it yourself first)
from fractions import Fraction

n, s = map(int, input().split())
ways = {0: 1}
for _ in range(n):
    nxt = {}
    for total, count in ways.items():
        for face in range(1, 7):
            nxt[total + face] = nxt.get(total + face, 0) + count
    ways = nxt
good = ways.get(s, 0)
print("ways", good)
print("outcomes", 6 ** n)
print("probability", Fraction(good, 6 ** n))

Lesson: Outcomes and probability →