Probability over many games
I'm working on Project Euler problem number 205 which states:
Peter has nine four-sided (pyramidal) dice, each with faces numbered 1, 2, 3, 4. Colin has six six-sided (cubic) dice, each with faces numbered 1, 2, 3, 4, 5, 6.
Peter and Colin roll their dice and compare totals: the highest total wins. The result is a draw if the totals are equal.
What is the probability that Pyramidal Pete beats Cubic Colin? Give your answer rounded to seven decimal places in the form 0.abcdefg
My initial attempt (below) involved having 1,000 "games", where each game had 1,000,000 turns. Then taking the average of all the games. I'm consistently getting results in the .559 area, but when the answer needs to be to 7 decimal places, that's not that close.
public class pe205 {
public static void main(String[] args) {
pe205 p = new pe205();
double sum = 0.0;
for(int i=0; i < 1000; i++){
sum += p.determineProbability();
}
System.out.println(sum/1000.0);
} // end main
public double determineProbability(){
int peterWins = 0;
int colinWins = 0;
for(int i=0; i < 1000000; i++){
int peterSum = 0;
for(int j=0; j < 4; j++){
Random r = new Random();
pete开发者_StackOverflowrSum += r.nextInt(9);
}
//System.out.println(peterSum);
int colinSum = 0;
for(int j=0; j < 6; j++){
Random r = new Random();
colinSum += r.nextInt(6);
}
//System.out.println(colinSum);
if(peterSum > colinSum){
peterWins++;
}
if(colinSum > peterSum){
colinWins++;
}
}
double peteBeatsColin = (double)peterWins/(double)(colinWins + peterWins);
return peteBeatsColin;
}
} // end class
I've read about the Monte Carlo method. Would this be a situation where that would be useful, and if so, could someone give me a brief walk through? Or is it that I'm missing some fairly obvious mathematical solution?
I would like to say that I enjoy the challenge of these problems, and I'm not looking for the answer, just a little push in the right direction.
Why not try to calculate the result combinatorially? Explicitly calculate the result by adding terms of the form
a_i = P(peter throws i, Colin throws < i)
Okay, I figured it out. An exact solution is possible. Here's a nudge.
Peter can roll 9 to 36.
Colin can roll 6 to 36.
Calculate the probability that Peter can roll r
where r
ranges from 9 to 36.
Do the same for Colin, r
ranging from 6 to 36.
From here you can calculate the probability that Peter beats Colin.
First, write a function that calculates the probability of N S-sided dice resulting in a given value C.
Once you have that, write a function to add up the probability that a given set of dice will roll less than a certain number.
Once you have that, write a function that loops over n->(n*s)
and calculates the probability that the other set of dice will be less than or equal to that.
Remember, the probability of A and B, if they are not entangled, is P(A) * P(B)
.
double colin(int n)
{
int t = 0;
for(int d1 = 1; d1<7; d1++)
for(int d2 = 1; d2<7; d2++)
for(int d3 = 1; d3<7; d3++)
for(int d4 = 1; d4<7; d4++)
for(int d5 = 1; d5<7; d5++)
for(int d6 = 1; d6<7; d6++)
if(d1+d2+d3+d4+d5+d6 == n)
t++;
return ((double)t)/(6*6*6*6*6*6);
}
-* This is if peter has only 4 dice not nine, i got lazy *
double peter(int n)
{
int t = 0;
for(int d1 = 1; d1<5; d1++)
for(int d2 = 1; d2<5; d2++)
for(int d3 = 1; d3<5; d3++)
for(int d4 = 1; d4<5; d4++)
if(d1+d2+d3+d4 == n)
t++;
return ((double)t)/(4*4*4*4);
}
main()
{
double r = 0.0;
for(int c = 4; c < 16; c++){
for(int p = 6; p < 36; p++){
if(c > p){
r += colin(c)*peter(p);
}
}
}
System.out.println(r);
}
Please excuse the extreme inefficiency, but you get the point.
精彩评论