| |
BGonline.org Forums
Exact solution
Posted By: Jason Lee In Response To: Exact solution (Chuck Bower)
Date: Tuesday, 24 August 2010, at 7:23 p.m.
Chuck: Is this ("just") eighteen nested do loops and an array of size 216 (sum of nine double sixes) where you populate the array with the sum of the 18 dice as you loop through? That's 6^18 = 10^14 = 100 trillion iterations. Does that take too long? (Use double-long integer arithmetic to save time?)
There may be clever shortcuts since you're only tallying the smaller combinations. E.g. you never need to tally any sequence where 6-6 occurs since the smallest nine rolls where one of them is a double six is 24 + 8*3 = 48.
Funny, you're thinking nearly along the lines I was.
First, I made some improvements on what you suggested. First, I considered only the 13 "different" throws -- since we're only counting pips, there are only 13 different unique pipcounts (24, 20, 16, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3) for a single throw. So we're really talking 13^9, which is a bit over 10 billion. (Ha. A bit.) 10 billion iterations on something isn't so bad. Now, when doing it this way, you have to be careful to weight the throw appropriately, since there are, for example, five different ways to throw a pipcount of 8.
Next, I did indeed try to do some short-cutting on the loops, but I did it differently than what you suggested. First, I didn't notice that 66 was impossible, so that helps some... we can cut it down to 12^9, just over 5 billion. (Excellent, Chuck, you just doubled our performance.) But, I was also short-cutting on the inside whenever the pipcount got too high.
In the end, I did something wrong, and it spit out the wrong number -- I think the problem was almost certainly in the short circuiting of the loops. On the plus side, when I just did a Monte Carlo simulation, I was getting the "right" numbers.
I might take another stab at it, to include Chuck's performance enhancing 66 removal.
JLee
| |
BGonline.org Forums is maintained by Stick with WebBBS 5.12.