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) andprobability Pas a reduced fraction (0when 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))