[QUIZ] Probable Iterations (#141)

[Ruby Quiz]

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion. Please reply to the original quiz message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

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

 

[Jesús Gabriel y Galán]

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.

Hi,

I wanted to look a little into parsing command line options and
arguments, so I took the opportunity to try Ara's "main" gem (gem
install main). I have a question about the usage of main at the end of
the post, if somebody can help me out, that'd be great.
In addition to the requirements I also added the possibility to pass
another option (--type or -t) with the type of comparison you want to
perform: at_least, exactly, no_more_than, less_than or more_than. It
defaults to at_least. Here it is:

# quiz141.rb
# 29 September 2007
#

require 'main'

$compare_types = {"at_least" => :>=, "exactly" => :==, "no_more_than" => :<=,
"more_than" => :>, "less_than" => :<}

main {
argument('dice') {
cast :int
description "number of dice to throw"
}
argument('num') {
cast :int
description "number of fives to count in each throw"
}
option('verbose', 'v') {
description "verbose mode: will show all combinations"
}
option('samples', 's') {
description "sample mode: will show 1 combination every 50000"
}
option('type', 't') {
argument :required
defaults "at_least"
validate {|type| $compare_types.keys.include?(type)}
description "Type of comparison. Possible values: " +
$compare_types.keys.join(",")
}

def run
verbose = params[:verbose].given?
samples = params[:samples].given?
dice = params[:dice].value
num = params[:num].value
type = params[:type].value
method = $compare_types[type]
puts "Checking #{type} #{num} fives throwing #{dice} dice"
puts "Verbose mode" if verbose
puts "Samples mode" if samples
current = Array.new(dice) {1}
current[0] = 0 # to start the loop incrementing the first element
total_matches = 0
total_iter = 0
begin
total_iter += 1
(0...dice).each do |i|
if (current < 6)
current += 1
break
else
current = 1
end
end
match = current.select {|x| x == 5}.size.send(method, num)
total_matches += 1 if match
if (verbose || (samples && total_iter%50000 == 1))
print total_iter, " ", current.inspect
puts "#{match ?'<==':''}"
end
end while current.any?{|x|x != 6}
puts "Number of desirable outcomes: #{total_matches}"
puts "Number of possible outcomes: #{total_iter}"
puts "Probabilty is #{total_matches.to_f/total_iter.to_f}"
end
}

Here's the output with 2 1 for each type of comparison.

$ ruby -rubygems quiz141.rb --type less_than 2 1
Checking less_than 1 fives throwing 2 dice
Number of desirable outcomes: 25
Number of possible outcomes: 36
Probabilty is 0.694444444444444

$ ruby -rubygems quiz141.rb --type at_least 2 1
Checking at_least 1 fives throwing 2 dice
Number of desirable outcomes: 11
Number of possible outcomes: 36
Probabilty is 0.305555555555556

$ ruby -rubygems quiz141.rb --type exactly 2 1
Checking exactly 1 fives throwing 2 dice
Number of desirable outcomes: 10
Number of possible outcomes: 36
Probabilty is 0.277777777777778

$ ruby -rubygems quiz141.rb --type no_more_than 2 1
Checking no_more_than 1 fives throwing 2 dice
Number of desirable outcomes: 35
Number of possible outcomes: 36
Probabilty is 0.972222222222222

$ ruby -rubygems quiz141.rb --type more_than 2 1
Checking more_than 1 fives throwing 2 dice
Number of desirable outcomes: 1
Number of possible outcomes: 36
Probabilty is 0.0277777777777778

My question about main is the following: if you check my code, I have
a variable ($compare_types) I need to use both in the validate block
for an option and in the run method. Is there a better way to achieve
this than a global variable?

Regards,

Jesus.

 

[Jesse Merriman]

--Boundary-00=_ei6/G7Mh/wSUl6w
Content-Type: Multipart/Mixed;
boundary="Boundary-00=_ei6/G7Mh/wSUl6w"

--Boundary-00=_ei6/G7Mh/wSUl6w
Content-Type: text/plain;
charset="utf-8"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

My solution isn't very fast, but gets the job done. To generate all possible
rolls, it runs through 0...6**num_dice, gets the string in base-6, and splits
it up.


--
Jesse Merriman
(e-mail address removed)
http://www.jessemerriman.com/

--Boundary-00=_ei6/G7Mh/wSUl6w
Content-Type: application/x-ruby;
name="dice.rb"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="dice.rb"

#!/usr/bin/env ruby
# Ruby Quiz 141: Probable Iterations

require 'getoptlong'

module Enumerable
def count obj
c = 0
each { |x| c += 1 if x == obj }
c
end
end

def each_roll num_dice, sides
(0...sides**num_dice).each do |x|
x = x.to_s sides
x = '0' * (num_dice - x.length) + x
yield x.split(//).map { |n| n.to_i + 1 }
end
end

def make_test n, min
end

if __FILE__ == $0
Opts = GetoptLong.new(
[ '--verbose', '-v', GetoptLong::NO_ARGUMENT ],
[ '--sample', '-s', GetoptLong::NO_ARGUMENT ] )

# defaults
verbose = false
sample = false
sample_rate = 50_000
sides = 6

Opts.each do |opt, arg|
case opt
when '--verbose'; verbose = true
when '--sample'; sample = true
end
end

num_dice = ARGV.shift.to_i
min_5s = ARGV.shift.to_i

i, hits = 0, 0
roll, passed = nil, nil

test = lambda { |roll| roll.count(5) >= min_5s }

printer = lambda do
print "#{i} #{roll.inspect}"
print ' <==' if passed
puts
end

each_roll num_dice, sides do |roll|
i += 1
passed = test[roll]
hits += 1 if passed
printer[] if verbose or (sample and (i % sample_rate) == 1 )
end

puts "\nNumber of desirable outcomes is #{hits}"
puts "Number of possible outcomes is #{i}"
puts "\nProbability is #{hits.to_f / i}"
end

--Boundary-00=_ei6/G7Mh/wSUl6w--
--Boundary-00=_ei6/G7Mh/wSUl6w--

 

[Ilmari Heikkinen]

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.

Iterates in base-6 and uses String#count for counting fives.

verbose = ARGV.delete("-v")
sample = ARGV.delete("-s")
dice, amt_of_fives = ARGV[0,2].map{|i| i.to_i }

num_outcomes = 6**dice
des_outcomes = 0
idx = 1
(0...num_outcomes).each{|oc|
s = oc.to_s(6)
hits = s.count("4")
hit = hits >= amt_of_fives
des_outcomes += 1 if hit
if verbose or (sample and idx % 50000 == 1)
# HA ha fhgh (justify, add one, reverse and
# make into an array string to match kenneth's output)
puts "#{idx} [#{s.rjust(dice,"0").tr!("012345","123456").reverse!.
split(//).join(",")}]#{hit ? " <==" : nil}"
end
idx += 1
}

puts
puts "Number of desirable outcomes is #{des_outcomes}"
puts "Number of possible outcomes is #{num_outcomes}"
puts
puts "Probability is #{des_outcomes.to_f / num_outcomes}"

 

[Morton Goldberg]

$compare_types =3D {"at_least" =3D> :>=3D, "exactly" =3D> :=3D=3D, =20
"no_more_than" =3D> :<=3D,
"more_than" =3D> :>, "less_than" =3D> :<}

My question about main is the following: if you check my code, I have
a variable ($compare_types) I need to use both in the validate block
for an option and in the run method. Is there a better way to achieve
this than a global variable?

I suggest making it a constant.

COMPARE_TYPES =3D { "at_least" =3D> :>=3D, "exactly" =3D> :=3D=3D, =
"no_more_than" =20
=3D> :<=3D,
"more_than" =3D> :>, "less_than" =3D> :< }

Regards, Morton

 

[Eugene Kalenkovich]

My solution. No match counting, + handles 'ruby dice.rb 1000 1'

---------------------------------------------------

require 'bigdecimal'
require 'bigdecimal/util'

def f(n) (1..n).inject(1){|a,i|a*=i} end
def perm(m,n) f(m)/(f(n)*f(m-n)) end
def fives(m,n) (0..m-n).inject(0) {|s,i| s+=5**i * perm(m,i)} end

case ARGV[0]
when '-v'
step=1
ARGV.shift
when '-s'
step=50_000
ARGV.shift
end
num=ARGV[0].to_i
min=ARGV[1].to_i

all=6**num
good=fives(num,min)

if (step)
zipper=Array.new(num,1)
0.step(all-1,step) do |i|
s=i.to_s(6).tr('012345','123456').rjust(num,'1').gsub(/(\d)(?=\d)/,'\1,').reverse
flag = (s.count('5')>=min) ? '<==' : ''
puts "%10s [%#{num*2-1}s] %4s" % [i+1,s,flag]
end
end

if all > Float::MAX.to_d
prob=good.to_s.to_d/all
else
prob=good.to_f/all
end

puts
puts "Number of desirable outcomes is #{good}"
puts "Number of possible outcomes is #{all}"
puts
puts "Probability is #{prob}"

 

[Stephen Kyle]

Hi,
I doubt my method of finding the iterations is particularly efficient:

I just have a function, nextLogicalRoll, which returns the next
"logical" set of dice, when you give it a set of dice, so it'll return
[1,2,1], if given [1,1,3]. I give it the first logical set, an array
of as-many-dice-as-we're-using 1s, and then watch for when it returns
as-many-dice-as-we're-using 6s.

The function has a "seek" pointer that points at the end of the array,
and if the number at that index isn't 6, it increases it by one, and
returns that array. Else it changes the 6 to a 1, and the pointer
moves one position towards the start of the array, this is repeated
until a number that isn't 6 is found at the array, this number is
increased by one, and the array is returned.

I quite like the way I do array finding, and although it's no doubt a
computational nightmare, on the order of O(n^10000) or something, it's
quite pretty. It just creates a string representing what we're looking
for; for instance, if we're looking for two fives, it'll be "55", and
then we sort the array representing the dice roll, convert it to a
string, and see if our "desired" string is a subset of the string.

That's all from me, this is my first time, be kind.

- Steve

Code:

$desired_count = 0
$possible_count = 0

# argument "parsing" fun, delicate
verbose = true if ARGV[0] == "-v"
sample = true if ARGV[0] == "-s"
if sample or verbose
dice = ARGV[1] if ARGV[1] =~ /\d+/
desired = ARGV[2] if ARGV[2] =~ /\d+/
hunted = ARGV[3] if ARGV[3] =~ /\d+/
else
dice = ARGV[0] if ARGV[0] =~ /\d+/
desired = ARGV[1] if ARGV[1] =~ /\d+/
hunted = ARGV[2] if ARGV[2] =~ /\d+/
end
dice = dice.to_i
desired = desired.to_i

def nextLogicalRoll(array) # find the next "logical" set of dice
seek = (array.length-1)
if array[seek] != 6
array[seek] += 1
else
while array[seek] == 6 do
array[seek] = 1
seek -= 1
end
array[seek] += 1
end
return array
end

def printArray(array) # reinventing the wheel, no doubt.
print "["
values = array * ","
print values
print "]"
end

def check(array,desired,hunted)
match = hunted.to_s * desired
return array.sort.to_s.include?(match)
end

set = Array.new(dice).fill(1)
finale = Array.new(dice).fill(6)
loop do
$possible_count += 1
print "#{$possible_count}. " if verbose or (sample and
$possible_count % 50000 == 1)
printArray(set) if verbose or (sample and $possible_count % 50000 == 1)
if check(set,desired,hunted)
$desired_count += 1
print " <==" if verbose or (sample and $possible_count
% 50000 == 1)
end
puts if verbose or (sample and $possible_count % 50000 == 1)
break unless set != finale
nextLogicalRoll(set)
end

puts
puts "Number of desirable outcomes is #{$desired_count}"
puts "Number of possible outcomes is #{$possible_count}"
puts
probability = $desired_count.to_f / $possible_count.to_f
puts "Probability is #{probability}"

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion. Please reply to the original quiz message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

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

 

[Jesús Gabriel y Galán]

I suggest making it a constant.

COMPARE_TYPES =3D { "at_least" =3D> :>=3D, "exactly" =3D> :=3D=3D, "no_mo= re_than"
=3D> :<=3D,
"more_than" =3D> :>, "less_than" =3D> :< }

Regards, Morton

Thanks for the tip. Didn't realize the scope of constants
This looks much better to me.

Jesus.

 

[Carl Porth]

Nothing too shocking:

http://pastie.caboo.se/102267

Carl

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion. Please reply to the original quiz message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- =-=-=

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

 

[come]

Hi,

Here is my quick solution :

dice.rb :

dice, n = ARGV.grep(/\d+/)
verbose = true if ARGV.include?("-v")
sample = true if ARGV.include?("-s")

max=("5"*dice.to_i).to_i(6)
n=n.to_i
resultat= (0..max).inject(0) do |sum,i|
output = verbose || (sample && i % 50_000 == 0)
print i+1,"\t",("%#{dice}s" % i.to_s(6)).split(//).map{|e| e.to_i
+1}.inspect if output
if i.to_s(6).scan(/4/).size > n-1
puts "<=" if output
sum+1
else
puts "" if output
sum
end
end

puts "Number of desirable outcomes is #{resultat}"
puts "Number of possible outcomes is #{max+1}"
puts Float(resultat) / Float(max+1)

 

[Eric DUMINIL]

Hi,

my solution came a bit too late and had nothing to offer in comparison
to the previous answers, so here is my slightly modified cheating
solution (I do not check anything, I actually use counting
calculations....)

##################################################################
n=8 #Dice number
d=3 #At least d fives
f=50000 #Display step (0: never, 1:always, f:every f lines)

class Fixnum
def fact
return 1 if self<2
self*(self-1).fact
end

def cnp(p)
self.fact/(p.fact*(self-p).fact)
end
end

@desirable=(d..n).inject(0){|mem,p| mem+n.cnp(p)*5**(n-p)}

N=6**n
(0...N).step(f){|outcome_id|
outcome=outcome_id.to_s(6).rjust(n,'0').split('').collect{|dice| dice.to_i+1}
print "\n#{(outcome_id+1).to_s.rjust(n)} : #{outcome.inspect}"
print " <==" unless outcome.select{|dice| dice==5}.size<d
} unless f==0

puts "\nNumber of desirable outcomes is #{@desirable}"
puts "Number of possible outcomes is #{N}"
puts "Probability is #{@desirable.to_f/N}"
##################################################################



time ruby dice.rb

1 : [1, 1, 1, 1, 1, 1, 1, 1]
50001 : [1, 2, 1, 3, 4, 3, 6, 3]
100001 : [1, 3, 1, 6, 1, 6, 5, 5]
150001 : [1, 4, 2, 2, 5, 3, 5, 1]
200001 : [1, 5, 2, 5, 2, 6, 4, 3]
250001 : [1, 6, 3, 1, 6, 3, 3, 5]
300001 : [2, 1, 3, 4, 3, 6, 3, 1]
350001 : [2, 2, 4, 1, 1, 3, 2, 3]
400001 : [2, 3, 4, 3, 4, 6, 1, 5]
450001 : [2, 4, 4, 6, 2, 3, 1, 1]
500001 : [2, 5, 5, 2, 5, 5, 6, 3] <==
550001 : [2, 6, 5, 5, 3, 2, 5, 5] <==
600001 : [3, 1, 6, 1, 6, 5, 5, 1]
650001 : [3, 2, 6, 4, 4, 2, 4, 3]
700001 : [3, 4, 1, 1, 1, 5, 3, 5]
750001 : [3, 5, 1, 3, 5, 2, 3, 1]
800001 : [3, 6, 1, 6, 2, 5, 2, 3]
850001 : [4, 1, 2, 2, 6, 2, 1, 5]
900001 : [4, 2, 2, 5, 3, 5, 1, 1]
950001 : [4, 3, 3, 2, 1, 1, 6, 3]
1000001 : [4, 4, 3, 4, 4, 4, 5, 5]
1050001 : [4, 5, 4, 1, 2, 1, 5, 1]
1100001 : [4, 6, 4, 3, 5, 4, 4, 3]
1150001 : [5, 1, 4, 6, 3, 1, 3, 5]
1200001 : [5, 2, 5, 2, 6, 4, 3, 1]
1250001 : [5, 3, 5, 5, 4, 1, 2, 3] <==
1300001 : [5, 4, 6, 2, 1, 4, 1, 5]
1350001 : [5, 5, 6, 4, 5, 1, 1, 1] <==
1400001 : [6, 1, 1, 1, 2, 3, 6, 3]
1450001 : [6, 2, 1, 3, 5, 6, 5, 5] <==
1500001 : [6, 3, 1, 6, 3, 3, 5, 1]
1550001 : [6, 4, 2, 2, 6, 6, 4, 3]
1600001 : [6, 5, 2, 5, 4, 3, 3, 5] <==
1650001 : [6, 6, 3, 2, 1, 6, 3, 1]
Number of desirable outcomes is 226491
Number of possible outcomes is 1679616
Probability is 0.134846893575674

real 0m0.010s
user 0m0.000s
sys 0m0.008s




Thanks for the quiz!

 

[Alex LeDonne]

Just for fun, I implemented two solutions: one actually does and
counts the iterations. The other fakes it for the no-option and option
-s cases (but produces EXACTLY the same output) and only does the
iterations for the -v (for which it is slower).

Both coded with lots of hard-coded magic numbers, like 6-sided dice,
looking for 5s, etc, but easily modified.

---------------------------------

Straight iterative:

require 'optparse'
options = {}
OptionParser.new do |opts|
opts.banner = "Usage: example.rb [options]"

opts.on("-v", "--[no-]verbose", "Run verbosely") do |v|
options[:v] = 1
end
opts.on("-s", "--sample", "Run in sample mode") do |s|
options[:s] = 1
end
end.parse!

total_dice, at_least_5 = Integer(ARGV[0]), Integer(ARGV[1])
des=0
tot=6**total_dice
roll = Array.new(total_dice){1}
roll[0] = 0

(0..tot-1).each { |serial|
marker = ""
roll[0]+=1
(0..total_dice-1).each do |idx|
if roll[idx]==7
roll[idx]=1
roll[idx+1]+=1
else
break
end
end
if roll.select{|die| die==5}.length >= at_least_5
marker = " <=="
des += 1
end
if options[:v] || (options[:s] && (serial % 50000)==0 )
puts "#{serial+1} #{roll.inspect} #{marker}"
end
}

puts "\nNumber of desirable outcomes is #{des}"
puts "Number of possible outcomes is #{tot}"
puts "\nProbability is %16.16f" %(des.to_f/tot)

-----------------
Fake it when possible using closed-form calculation:


# Math.nCr(n,r) borrowed from Brian Candler's
# post in ruby_talk

def Math.nCr(n,r)
a, b = r, n-r
a, b = b, a if a < b # a is the larger
numer = (a+1..n).inject(1) { |t,v| t*v } # n!/r!
denom = (2..b).inject(1) { |t,v| t*v } # (n-r)!
numer/denom
end

class DiceAtLeastFive
def self.int_to_roll( serial, numdice )
# good for reality, too slow for a quiz - #pow is expensive.
# raise if serial >= 6**numdice
serial.to_s(6).rjust(numdice,"0").split(//).map!{|ele|
ele.to_i + 1 }.reverse
end

def self.total_rolls(numdice)
6**numdice
end

def self.desirable(numdice, min_fives)
(min_fives..numdice).inject(0) { |tot, val| tot +
(Math.nCr(numdice,val) * 5**(numdice-val)) }
end

end


require 'optparse'
options = {}
OptionParser.new do |opts|
opts.banner = "Usage: example.rb [options]"

opts.on("-v", "--[no-]verbose", "Run verbosely") do |v|
options[:iter_step] = 1
end
opts.on("-s", "--sample", "Run in sample mode") do |s|
options[:iter_step] = 50000
end
end.parse!

total_dice, at_least_5 = Integer(ARGV[0]), Integer(ARGV[1])
des=DiceAtLeastFive.desirable(total_dice,at_least_5)
tot=DiceAtLeastFive.total_rolls(total_dice)

if options[:iter_step]
(0..tot-1).step(options[:iter_step]) { |serial|
marker = ""
roll = DiceAtLeastFive.int_to_roll(serial, total_dice)
if roll.select{|die| die==5}.length >= at_least_5
marker = " <=="
end
puts "#{serial+1} #{roll.inspect} #{marker}"
}
end

puts "\nNumber of desirable outcomes is #{des}"
puts "Number of possible outcomes is #{tot}"
puts "\nProbability is %16.16f" %(des.to_f/tot)

 

[Yossef Mendelssohn]

The three rules of RubyQuiz:

1. Please do not post any solutions or spoiler discussion for thisquizuntil
48 hours have passed from the time on this message.

2. Support RubyQuizby submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion. Please reply to the originalquizmessage,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

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

My thrown-together solution:

#!/usr/bin/env ruby

require 'optparse'

verbose = false
check = false

dice = 1
wanted = 1

SIDES = 6
CHECK_FREQUENCY = 50000

OptionParser.new do |opts|
opts.on('-d', '--dice [DICE]', Integer, 'The number of dice to
roll') do |dice_opt|
dice = dice_opt.to_i
end
opts.on('-w', '--wanted [WANTED]', Integer, 'The number of 5s to
check for') do |wanted_opt|
wanted = wanted_opt.to_i
end
opts.on('-c', '--check', 'Turn on check mode') do |check_opt|
check = check_opt
verbose = false
end
opts.on('-v', '--verbose', 'Turn on verbose mode') do |verbose_opt|
verbose = verbose_opt
check = false
end
opts.parse!(ARGV)
end

CONFIG = {
:dice => dice,
:wanted => wanted,
:verbose => verbose,
:check => check
}

if CONFIG[:verbose] or CONFIG[:check]
puts 'Outcomes:'
puts
end

@wanted = 0
@outcomes = SIDES ** dice
@number = 0

def generate_outcomes(num_dice, *previous_rolls)
if num_dice == 0
num_wanted = previous_rolls.select { |x| x == 5 }.length
wanted = num_wanted >= CONFIG[:wanted]
if wanted
@wanted += 1
end
display = CONFIG[:verbose] || (CONFIG[:check] && (@number %
CHECK_FREQUENCY).zero?)
if display
print " %#{@outcomes.to_s.length}d" % (@number + 1)
print ' '
print previous_rolls.inspect
print ' <=' if wanted
puts
end
@number += 1
elsif num_dice > 0
1.upto(SIDES) do |x|
generate_outcomes(num_dice - 1, *(previous_rolls + [x]))
end
end
end


generate_outcomes(dice)

puts if CONFIG[:verbose] or CONFIG[:check]
puts "Possible outcomes: #{@outcomes}"
puts "Desired outcomes: #{@wanted}"
puts "Probability: #{@wanted.to_f/@outcomes.to_f}"

 

[Werner]

Il Fri, 28 Sep 2007 22:21:34 +0900, Ruby Quiz ha scritto:

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.

Hallo everybody. Complete newb in Ruby (but not really new to programming),
decided to try my hand at a simple problem, after completing the old no.14
test (the "Seven segment display").

This is the best I could manage: http://pastie.caboo.se/103086
No, it doesn't work, sorry. But since I can't understand the error message
I'm getting (everything refers to external code in the "main" library, not
in my program), and I have no other place to ask for advice about Ruby
anyway, I decided to post it anyway. Any advice will be much appreciated

 

[Eugene Kalenkovich]

My solution. No match counting, + handles 'ruby dice.rb 1000 1'


require 'bigdecimal'
require 'bigdecimal/util'

def f(n) (1..n).inject(1){|a,i|a*=i} end
def perm(m,n) f(m)/(f(n)*f(m-n)) end

I'd better use google instead of worn memory - though I've managed to do a
correct formula, name for it was absolutely wrong (perm, for permutations,
instead of something for combinations). As a compensation for my
sloppiness, here is a version of combinations that is almost 3 times faster:

require 'benchmark'

def f(n) (2..n).inject(1){|s,n| s*n } end
def perm(m,n) f(m)/(f(n)*f(m-n)) end # not pern[utations] at all,
combinations

def comb(m,n)
num,denum=m,1;
(2..n).each{|i| num*=(m-i+1); denum*=i}
num/denum
end

n=5000;
choices=500;
tests=[]
n.times { a=rand(choices+1); tests<<[a,rand(a)]}

Benchmark.bm do |x|
x.report("pern") { tests.each{|a| perm(a[0],a[1])} }
x.report("comb") { tests.each{|a| comb(a[0],a[1])} }
end

__END__

ruby comb_test.rb
user system total real
perm 6.210000 0.000000 6.210000 ( 8.315633)
comb 2.430000 0.000000 2.430000 ( 0.332727)

def fives(m,n) (0..m-n).inject(0) {|s,i| s+=5**i * perm(m,i)} end

Should read

def fives(m,n) (0..m-n).inject(0) {|s,i| s+=5**i * comb(m,i)} end

[...]