by Kenneth Kin Lum
You just did some probability calculations, and don't know if the answers are correct. So you write a program to verify the results. If you have eight dice, and throw them all at once, what is the probability that there are AT LEAST three fives? Try to write a program that find out the "number of desirable outcomes" / "number of possible outcomes" by iterating through all the possible outcomes of the dice throw. It has a verbose mode to see that the program is running correctly (for the case 2 dice, at least 1 five):
C:\rails\depot>ruby dice.rb -v 2 1
1 [1,1]
2 [2,1]
3 [3,1]
4 [4,1]
5 [5,1] <==
6 [6,1]
7 [1,2]
8 [2,2]
9 [3,2]
10 [4,2]
11 [5,2] <==
12 [6,2]
13 [1,3]
14 [2,3]
15 [3,3]
16 [4,3]
17 [5,3] <==
18 [6,3]
19 [1,4]
20 [2,4]
21 [3,4]
22 [4,4]
23 [5,4] <==
24 [6,4]
25 [1,5] <==
26 [2,5] <==
27 [3,5] <==
28 [4,5] <==
29 [5,5] <==
30 [6,5] <==
31 [1,6]
32 [2,6]
33 [3,6]
34 [4,6]
35 [5,6] <==
36 [6,6]
Number of desirable outcomes is 11
Number of possible outcomes is 36
Probability is 0.3055555555555556
C:\rails\depot>ruby dice.rb 8 3
Number of desirable outcomes is 226491
Number of possible outcomes is 1679616
Probability is 0.1348468935756745
It also has a "sample mode" to print out the samples every 50,000 times in the loop:
C:\rails\depot>ruby dice.rb -s 8 3
1 [1,1,1,1,1,1,1,1]
50001 [3,6,3,4,3,1,2,1]
100001 [5,5,6,1,6,1,3,1]
150001 [1,5,3,5,2,2,4,1]
200001 [3,4,6,2,5,2,5,1]
250001 [5,3,3,6,1,3,6,1]
300001 [1,3,6,3,4,3,1,2]
350001 [3,2,3,1,1,4,2,2]
400001 [5,1,6,4,3,4,3,2]
450001 [1,1,3,2,6,4,4,2]
500001 [3,6,5,5,2,5,5,2] <==
550001 [5,5,2,3,5,5,6,2] <==
600001 [1,5,5,6,1,6,1,3]
650001 [3,4,2,4,4,6,2,3]
700001 [5,3,5,1,1,1,4,3]
750001 [1,3,2,5,3,1,5,3]
800001 [3,2,5,2,6,1,6,3]
850001 [5,1,2,6,2,2,1,4]
900001 [1,1,5,3,5,2,2,4]
950001 [3,6,1,1,2,3,3,4]
1000001 [5,5,4,4,4,3,4,4]
1050001 [1,5,1,2,1,4,5,4]
1100001 [3,4,4,5,3,4,6,4]
1150001 [5,3,1,3,6,4,1,5]
1200001 [1,3,4,6,2,5,2,5]
1250001 [3,2,1,4,5,5,3,5] <==
1300001 [5,1,4,1,2,6,4,5]
1350001 [1,1,1,5,4,6,5,5] <==
1400001 [3,6,3,2,1,1,1,6]
1450001 [5,5,6,5,3,1,2,6] <==
1500001 [1,5,3,3,6,1,3,6]
1550001 [3,4,6,6,2,2,4,6]
1600001 [5,3,3,4,5,2,5,6] <==
1650001 [1,3,6,1,2,3,6,6]
Number of desirable outcomes is 226491
Number of possible outcomes is 1679616
Probability is 0.1348468935756745
Quiz Summary
As a couple of solvers noted, this is an easy problem that's really just about counting. In fact, you can solve the entire problem without ever rolling a die.
The trick is really in how you think about the problem. Basically we want to enumerate all of the possible rolls from:
to:
Let me show you that one more time though, minus some Ruby syntax characters:
111111 to 666666
Now it starts to look like counting, right? It almost is. If we counted straight between those two numbers though, we would pick up some digits that aren't on our dice. But if we drop the digits on both sides by one:
000000 to 555555
Now that is counting, in base six, and it's just a quick transliteration to adjust the digits up. We're going to look at a solution that does just that.
While I put the code together that I'm going to show you, it's heavily inspired from many of the submissions I liked. Let's just say that this week's showcased solution belongs to everyone.
Here's the argument processing code:
MODE = if ARGV.first =~ /-([sv])/
ARGV.shift
$1
end
unless ARGV.size == 2
abort "Usage: #{File.basename($PROGRAM_NAME)} [-s|-v] NUM_DICE MIN_FIVES"
end
NUM_DICE, MIN_FIVES = ARGV.map { |n| Integer(n) }
# ...
This code should be pretty easy to break down. We check to see if the first argument looks like a switch and store it in the MODE constant when it does. Note that the code doesn't provide an else branch for this check, but Ruby will default the constant to nil for us when the if condition fails to match.
The next bit of code just ensures that we have the two required arguments, converts them or throws an error if they are not what we expected, and stores them in constants for future use.
We're now ready for the counting code:
desirable_outcomes = 0
POSSIBLE_OUTCOMES = 6 ** NUM_DICE
POSSIBLE_OUTCOMES.times do |i|
outcome = i.to_s(6).rjust(NUM_DICE, "0")
if desirable = outcome.count("4") >= MIN_FIVES
desirable_outcomes += 1
end
if MODE == "v" or (MODE == "s" and (i % 50_000).zero?)
puts "%#{NUM_DICE}d [%s]#{' <==' if desirable}" %
[i + 1, outcome.tr("0-5", "1-6").gsub(/(\d)(\d)/, '\1,\2')]
end
end
# ...
This is the heart of the code and, as you can see, still quite simple. We begin by defining the range we will iterate over, from zero to the maximum count on the requested number of dice.
The times() iterator does the actual count. Remember that we really want these numbers in base six. The first line of the iterator does the conversion, padding with zeros to ensure we have the right number of "dice."
The first if branch is our test for the minimum number of fives. When found, we bump a global counter that can later be used to generate results.
The final if statement handles printing for either of the inspection modes. If we're in verbose mode, or sample mode and on a 50,000th iteration, the code prints the result index, the dice values, and an indicator arrow for rolls that were flagged as desirable. This is where you see the code to bump all of the digits so they will match pips on a die.
The final bit of code, just prints the results:
puts if MODE
puts "Number of desirable outcomes is #{desirable_outcomes}"
puts "Number of possible outcomes is #{POSSIBLE_OUTCOMES}"
puts
puts "Probability is #{desirable_outcomes / POSSIBLE_OUTCOMES.to_f}"
This is as easy as it gets. We show the desirable, the possible, and calculate the odds from the two of them. The first line just sneaks in a line of padding between any sampling and the end results.
Again, this code combined things I liked from many of the solutions, so they are definitely worth a look. Especially don't miss Alex LeDonne's second solution which uses some math to skip counting at all, when it can get away with it.
As always, my thanks to all who took the time to solve this quiz. I feel like we always get creative results for the simple problems.
Tomorrow we will tackle one of the all time famous tough problems, and see if we just can't solve it reasonably well with minimal knowledge of the domain...
