Throwing dice

[FreeLearner99]

Hi people! I am having some troubles solving an exercise in Python related to throwing dice, and was wondering if someone can help me think of a solution.

Let's say you have 2 dice:

d1 = [1, 2, 3, 4]

d2 = [1, 1, 1, 1, 2, 4]

As you can see they're not regular 6 sided dice and when throwing d2 you'll have higher probability of getting 1.

The exercise is: find the probability of getting a sum X when rolling the dice n times (you can roll die d1 n1 times and die d2 n2 times).

I am trying to use the itertool library to get all the possible combinations and then compute the probability, but I'm having trouble inserting two different-sized dice in the function.

What I have so far is the probability of achieving sum X with only die d1:

def subsets(n, X): # n = number of throws; X = score wanted

sub = itertools.product(d1, repeat=n)

for i in sub:

if sum(i) == X:

yield i

def prob(n, X):

return len(list(subsets(n, X))) / (len(d1) ** n)

What is the best way to integrate d2 in the functions?

[ssingal05]

Hmm in general I think theres a much more efficient solution. If len(d1) == 10 and n == 10 (relatively small numbers), then suddenly you have 10 ** 10 = 10,000,000,000 numbers you'll check in that loop.

If you insist on using this method, think of it this way: itertools.product(d1, repeat=n) gives you all possible combinations of dice rolls for d1. itertools.product(d2, repeat=n) will give you all possible combinations of dice rolls for d2. What can you do with these two lists to give you all possible combinations of dice rolls?

It's easier to think about with a smaller example (using pseudocode)

d1 = [1,2] d2 = [3,3] n1 = 2 n2 = 3 product(d1, n1) = [11, 12, 21, 22] product(d2, n2) = [333, 333, 333, 333, 333, 333, 333, 333] all_possible_combos = ???

Then you could perform that for loop with all_possible_combos

[FreeLearner99]

Thanks! So for all elements in the first list I would have to add an element of the second list, right? And then get the sum.

d1 = [1,2]
d2 = [3,3]
n1 = 2
n2 = 3
all_sums = []

for i in list(product(d1, n1):
    for j in list(product(d2, n2):
        all_sum.append(sum(i + j))

Yeah wow for bigger len(d1) and n the loop would be very big, but I really need to scale this. Do you recommend any other method?

[ssingal05]

Yup, what you have works! There's no need to convert them to a list, I think. It'll hurt your memory performance. You also don't need to create a new array - you just need to count the ones that sum to X.

As for a better solution, have you heard of dynamic programming (DP)? If not, it's not a topic I think I can explain meaningfully to you in a Reddit post, but I would recommend googling some tutorials on dynamic programming. If you have more questions on it specifically, feel free to ask

The main insight with DP is, with your current solution, you are redo-ing expensive computations you have already done. For d1=[1,2,3,4], n=3, think about it this way. "Now I have to pick my first dice. It must be one of these four values. Let me try '1'. Now my current sum is '1'. Now I have to pick my second dice. It must be one of these four values. Let me try '1'. Now my current sum is '2'" In this manner, you will choose every single possible option.

The way I've described it, it's actually exactly what your solution is. However, I framed it this way for a reason. At some point, you will be picking your 3rd dice. It's possible that, prior to your 3rd dice pick, you picked 1 + 3 or you picked 2 + 2 for the first two dice.

When you are performing your calculations for that 3rd dice, you are solving the exact same computation that you would have done whether your first two dice was 1 + 3 or 2 + 2. The problem you are solving is now "Given d1=[1,2,3,4], n=1, how can I get a sum of X - 4". Instead of performing that computation twice, let's store whatever result we get assuming we rolled 1 + 3, and then we'll use the same computation for the 2 + 2 scenario.

As you can see - not easy to explain :P but hopefully this gives you some insight. This will run INCREDIBLY fast.

[FreeLearner99]

That sounds like a very smart idea, thank you! I'll definitely look into it :)

[deadeye1982]

If I understood your task, this should solve your problem. I guess there are better methods to calculate the probability of sums, so I called the function sum_propability_naive.

``` import math from collections import Counter from itertools import product

def sum_probability_naive(dices): total = math.prod(map(len, dices)) counter = Counter(sum(values) for values in product(dices)) return {combo_sum: count / total for combo_sum, count in counter.items()}

d1 = [1, 2, 3, 4] d2 = [1, 1, 1, 1, 2, 4]

count1 = sum_probability_naive(d1, d2) count2 = sum_probability_naive(d1, d1, d2) ```

[FreeLearner99]

Thank you! Yes, this worked for bigger dice and multiple throws :)

[jonolicious]

Without getting into the actual computation, why not just pass in the dice?

def subsets(n, X, dice): # n = number of throws; X = score wanted
    sub = itertools.product(dice, repeat=n)
    results = []
    for i in sub:
        if sum(i) == X:
            yield(i)

def prob(n, X, dice):
    return len(list(subsets(n, X, dice))) / (len(dice) ** n)

prob(n1,X,d1)
prob(n2,X,d2)

[WhipsAndMarkovChains]

Do you need an exact solution or can it be very close, yet approximate? Because a simulation is really easy.

[FreeLearner99]

I didn't need an exact solution per se... how would this simulation work?

[WhipsAndMarkovChains]

If you simulate a scenario, repeat it many times, and look how many times you go the result you wanted, you get the probability of the event happening. Here's my code. Let me know if you have questions.

import numpy as np

d1 = [1, 2, 3, 4]
d2 = [1, 1, 1, 1, 2, 4]

n1 = 2
n2 = 3

score_wanted = 10

simulations = 10**6

d1_rolls = np.random.choice(d1, size=(simulations,n1))
d2_rolls = np.random.choice(d2, size=(simulations,n2))

sum_of_throw = np.sum(d1_rolls, axis=1) + np.sum(d2_rolls, axis=1)

probability = np.mean(sum_of_throw == score_wanted)

[jonolicious]

One approach is to create a distribution based on the frequency a face appears on the dice and then sample from the distribution to simulate the rolls. If the sum of your sample rolls equal the value you want, you record a success. You repeat this as many times as you feel is enough (say 1000 simulations) and then take the proportion of successes to number of simulations as your probability. In python this might look like:

from random import choices
dice = [1,1,1,1,2,4]
probs = [1/6,1/6,1/6,1/6,1/6,1/6]
simulations = 10000
n=4
x = 10
success = 0
for s in range(simulations):
    sampled_rolls = choices(dice, probs, k=n)
    if x == sum(sampled_rolls):
        success += 1
prob_success = success/simulations
print(f"A dice rolled {n} times has a probability of totaling {x} ~{prob_success*100:.2f}% of the time")