Euler Problem 205 asks:
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
As a quick review, if we roll 2 of Colin’s dice, we expect 62 different outcomes. Rolling 6 dice will have 66 outcomes, or 46,656 different rolls.
Peter has 49 different outcomes, or 262,144 different rolls. Peter’s least roll (nine 1’s) will best the one way Colin can roll a 6 (six 1’s), the six ways he can roll a 7 (five 1’s and a 2 six times) and the twenty-one ways he can roll an 8 (a 3 and five 1’s six times, or two 2’s and four 1’s fifteen times). Peter’s meager 9 wins over 28 of Colin’s possible rolls. Peter’s 10, which he can roll 9 ways, bests 84 of Colin’s rolls.
VBA does not have a CEILING function, and I needed one for this problem. We could use Application.Worksheetfunction.Ceiling, but there is a quicker way execution-wise by a factor of 5. The INT function always rounds down. When the argument to INT is negative, INT rounds down or away from zero. INT(-3.14159) is -4, and -INT(-3.14159) is 4, rounding pi() up! Very useful when you need more area in your circles. It works this way in both the VBA and the spreadsheet implementations.
Easier than developing the usage for Problem 205, I’ll show it and explain how it works. The code we want to use for Colin is “-INT(-N/6^C) Mod 6” for C from zero to five, where N is the number of the roll (1 to 66), and when Mod 6 = zero, substitute 6. In a spreadsheet, this would be =IF(MOD(-INT(-N/6^C),6), MOD(-INT(-N/6^C),6), 6)
Remembering that 60 is 1, and 61 is 6, this is how the first four of Colin’s dice (C=0,1,2,3) look on Roll 66, N = 66, -N = -66.
- C = 0, Die 1:
- INT(-66/6^0) = INT(-66/1) = -66
- 66 = 66
- 66 Mod 6 = 0, Return 6
- C = 1, Die 2:
- INT(-66/6^1) = INT(-66/6) = -11
- 11 = 11
- 11 Mod 6 = 5, Return 5
- C = 2, Die 3:
- INT(-66/6^2) = INT(-66/36) = INT(-1.83333) = -2
- 2 = 2
- 2 Mod 6 = 2, Return 2
- C = 3, Die 4:
- INT(-66/6^3) = INT(-66/216) = INT(-0.30555) = -1
- 1 = 1
- 1 Mod 6 = 1, Return 1
Dice 5 and 6 (with C of 4 and 5) also return 1. Colin’s 66th roll is {6,5,2,1,1,1}. We do the same thing for Peter, where the code is “-INT(-N/4^P) Mod 4” for P from zero to eight, returning 4 when Mod 4 is zero. Peter’s 66th roll is {2,1,1,2,1,1,1,1,1}, summing 11. Peter gets 11 forty-five ways, on which he beats the 210 of Colin’s rolls (but not Colin’s #66) that sum 10 or below.
If we aggregate the number of times Colin sums from 6 to 36 in his 46,656 possible rolls, and the number of times Peter gets a particular sum from 9 to 36 in his 262,144 different rolls, we can then loop through Peter’s aggregation and see how many of Colin’s rolls lose to that number. If we then multiply that discovery by the number of ways Peter achives that aggregation, keep a grand sum of winners, and then divide by the product of (66)*(49),we will have our percentage of Peter’s winning. Format the answer to 7 decimals to the right. Format() will take care of the necessary rounding.
This is the code that does this. It runs in about 6ths of a second.
Sub Problem_205()
Dim N As Long, TEMP As Long, Sum As Long
Dim Answer As Double, T As Single, Count As Double
Dim PP(1 To 36) As Long, P As Long ‘Pyramidal Pete
Dim CC(1 To 36) As Long, C As Long ‘Cubic Colin
Dim LosersToPete As Long
T = Timer
For N = 1 To 6 ^ 6 ‘Cubic Colin
Sum = 0
For C = 0 To 5
TEMP = -Int(-N / 6 ^ C) Mod 6
If TEMP = 0 Then TEMP = 6
Sum = Sum + TEMP
Next C
CC(Sum) = CC(Sum) + 1 ‘Incrementing Colin’s ways this value can happen
Next N
For N = 1 To 4 ^ 9 ‘Pyramidal Pete
Sum = 0
For P = 0 To 8
TEMP = -Int(-N / 4 ^ P) Mod 4
If TEMP = 0 Then TEMP = 4
Sum = Sum + TEMP
Next P
PP(Sum) = PP(Sum) + 1 ‘Incrementing Pete’s ways this value can happen
Next N
For P = 9 To 36 ‘ Pete’s rolls
LosersToPete = 0
For C = 6 To P – 1
LosersToPete = LosersToPete + CC(C) ‘ Num Colin’s rolls (all losses) below Pete’s roll
Next C
Count = Count + (LosersToPete * PP(P))
‘Incrementing the winning Count by the # of ways Colin’s roll can lose to Pete
Next P
Answer = Count / (CDbl(4 ^ 9) * CDbl(6 ^ 6))
Debug.Print Format(Answer, “0.0000000”);” Time:”; Timer – T; Count
End Sub
If, instead of -INT, I use Application.Worksheetfunction.Ceiling as:
- TEMP = Application.WorksheetFunction.Ceiling(N / 6 ^ C, 1) Mod 6 and
- TEMP = Application.WorksheetFunction.Ceiling(N / 4 ^ P, 1) Mod 4
the runtime is 3.5 seconds! Using ROUNDUP() is even slower. The really wrong way to do this problem is to match each of Peter’s rolls with each of Colin’s, or something like this, where larger PP() and CC() now hold each roll and not the occurrances of each sum.
For P = 1 to 4^9
For C = 1 to 6^6
If PP(P) > CC(C) then Count = Count + 1
Next C
Next P
That’s 12,230,590,464 loops. Been there, did that. Takes 6 and a half minutes. No tee shirt.
…mrt
