--------------050407040609060308020901
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
I've decided to bite the bullet and post my overlong solution.
It's got a few extras in there:
$ ./dice.rb "(5d5-4)d(16/d4)+3"
45
$ ./dice.rb "3d6" 6
11 7 10 13 9 14
$ ./dice.rb -dist "2d5 + 1dd12"
Distribution:
3 0.0103440355940356
4 0.0276987734487735
5 0.0503975468975469
6 0.0773292448292448
7 0.107660533910534
8 0.120036676286676
9 0.120568783068783
10 0.112113997113997
11 0.096477873977874
12 0.07495670995671
13 0.0588945406445407
14 0.0457661135161135
15 0.0345793650793651
16 0.0250565175565176
17 0.0171049783549784
18 0.0107247474747475
19 0.00596632996632997
20 0.00290909090909091
21 0.00113636363636364
22 0.000277777777777778
Check total: 1.0
Mean 9.75 std. dev 3.37782803325187
$ ./dice.rb -cheat "2d5 + 1dd12" 19
19 : D5 D5PD12 D12 p 000277777777777778
$ ./dice.rb -cheat "2d5 + 1dd12" 25
Cannot get 25
I'm getting to grips with block-passing as a routine technique - the
evaluate() method "yield"s its result so that it can provide multiple
results - tens of thousands if you ask it to try every possible roll
involving lots of dice. The roll_dice method had to be written
recursively for that to work:
def roll_dice( numdice, sides )
if ( numdice 0 )
yield null_value
else
roll_one(sides) do |first|
roll_dice( numdice-1, sides ) do |rest|
yield( first + rest )
end
end
end
end
Depending on how roll_one has been overridden, "first" and "rest" can be
integers, frequency distributions, or objects representing the history
of every roll to get to this state. In the last case, roll_one will
yield "sides" times, to give you every possible roll
I'm not quite comfortable with things like redefining Integer#+
If I had done that, I could have avoided a lot of kind_of? calls in
stuff like this:
def eval_binop( force_same_type rue )
subtree(:left).evaluate do |l|
subtree(:right).evaluate do |r|
if force_same_type
if r.kind_of?( Roll_stat ) and ! l.kind_of?( Roll_stat )
l oll_stat.new(l)
end
end
yield(l,r)
end
end
end
The whole thing can generate the probability distributions reasonably
quickly - I had ideas of approximating large numbers of dice (100d6
and so on) with the appropriate normal distribution ("clipped" by max
and min values).
The exhaustive output is very large, though. It would be worth
optimising that by taking out permutations.
I've shoved it on
http://homepage.ntlworld.com/a.mcguinness/files/dice.rb and attached it.
--------------050407040609060308020901
Content-Type: text/plain;
name
ice.rb"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
filename
ice.rb"
#!/usr/bin/env ruby
in
A frequency table, stored as an array of (value,probability) pairs
Can be constructed empty, as a fixed integer value with a probability
of one, or as a uniform distribution from 1 to n
ßÅ
class Freq_dist
class Freq
attr_accessor :value, :p
def initialize( v, p )
@value
@p
end
def < ( other )
@value < other.value
end
def to_s
print "[#{value},#{p}] "
end
end
attr_reader :prob
def initialize()
@prob ]
self
end
def uniform(n)
n.times { |i| @prob.push( Freq.new( i+1, 1.0/n ) ) }
self
end
def integer(n)
@prob Freq.new(n,1.0)]
self
end
def set_arr( dist )
@prob ist
self
end
def to_s
string
check_total .0
@prob.each do |el|
string + "#{el.value}\t#{el.p}\n" )
check_total + l.p
end
string + "Check total: #{check_total}\n" )
string + tats
end
def coalesce
sorted_prob rob.sort
@prob ]
sorted_prob.each do |i|
if @prob.empty? or ( i.value ! prob.last.value )
@prob.push(i)
else
@prob.last.p prob.last.p + i.p
end
end
end
¥»gin
These two methods are for building up distributions: merging
produces a part-distribution where the probability assigned to
each value is the sum of the probabilities assigned to that value
in the two part-distributions self and other
ßÅ
def merge ( other )
new_dist req_dist.new.set_arr(@prob + (other.prob))
new_dist.coalesce
new_dist
end
def scale_prob( factor )
new_dist req_dist.new.set_arr( @prob.map { |x| Freq.new( x.value, x.p * factor ) } )
end
¥»gin
These produce the distribution of a random variable which
is a function of two other random variables with distributions
provided (self and other
ßÅ
def combine( other )
if other.kind_of?(Numeric)
return combine_int( other ) { |x,y| yield(x,y) }
end
new_dist ]
@prob.each do |el1|
other.prob.each do |el2|
new_dist.push( Freq.new( yield( el1.value, el2.value ),
el1.p * el2.p))
end
end
result req_dist.new
result.set_arr( new_dist.sort )
result.coalesce
result
end
def combine_int( x )
result req_dist.new
new_dist ]
@prob.each do |el|
new_dist.push( Freq.new( yield( el.value, x ), el.p ) )
end
result.set_arr( new_dist )
end
def + (a) ; combine( a ) { |x,y| x+y } end
def - (a) ; combine( a ) { |x,y| x-y } end
def * (a) ; combine( a ) { |x,y| x*y } end
def / (a) ; combine( a ) { |x,y| x/y } end
def mean
@prob.inject(0.0) { |tot,el| tot + el.value * el.p }
end
def sig_x2
@prob.inject(0.0) { |tot,el| tot + el.value * el.value * el.p }
end
def var
mu ean
sig_x2 - mu * mu
end
def std_dev
Math.sqrt( var )
end
def stats
"Mean #{mean} std. dev #{std_dev}"
end
end
¥»gin
This evaluates an already-parsed expression, generating an
appropriate random number for each dice roll
ßÅ
class Evaluator
def initialize( parent )
@parsed_expr arent
end
def null_value
return 0
end
def subtree(side)
self.class.new(@parsed_expr.subtree(side))
end
def eval_binop( force_same_type rue )
subtree(:left).evaluate do |l|
subtree(:right).evaluate do |r|
yield(l,r)
end
end
end
def roll_one( sides )
val + rand(sides)
# puts( "Rolled D#{sides} got #{val}" )
yield val
end
def roll_dice( numdice, sides )
if ( numdice 0 )
yield null_value
else
roll_one(sides) do |first|
roll_dice( numdice-1, sides ) do |rest|
yield( first + rest )
end
end
end
end
def evaluate
case (@parsed_expr[0] )
when :integer
yield @parsed_expr[1]
when :expr
case (@parsed_expr[1][1])
when :mult
eval_binop { |x,y| yield x*y }
when :plus
eval_binop { |x,y| yield x+y }
when :minus
eval_binop { |x,y| yield x-y }
when :divide
eval_binop { |x,y| yield x/y }
when :dice
eval_binop(false) do |numdice,sides|
roll_dice( numdice, sides ) { |x| yield x }
end
else
throw "Evaluation error"
end
else
throw "Evaluation error"
end
end
end
# This is used by the ParseTree to generate its own state
class Parser
def initialize( debug alse )
@stack [:start]]
@state start
@debug ebug
end
@@precedence :dice 4, :plus 2, :minus , :mult 3, :divide }
def tokenise( input )
pos
len nput.length
while ( pos < len ) do
ch nput[pos..pos]
if "()+-dD*/%".include? ch
yield ch
elsif " \n\t".include? ch
;
elsif ch /[0-9]/
numpos os
while ( ( pos+1 < len ) && ( input[pos+1..pos+1] /[0-9]/ ))
pos +
end
yield input[numpos..pos]
else
throw "invalid char #{ch}"
end
pos +
end
yield "END"
end
def parse( str )
tokenise( str ) do |t|
parse_t( t )
end
tree op
if top[0] ! start
throw "Syntax error: #{tree.inspect}, #{@stack.inspect}"
else
return tree
end
end
def parse_t(tok)
if @debug
puts "Debug: stack {@stack.inspect}"
puts "Debug: tok tok} state @state}"
end
method(@state).call(tok)
end
def push(x) ; @stack.push x ; end
def pop ; @stack.pop ; end
def top ; @stack.last ; end
def collapse_top
expr op
if (( expr[0] :expr ) || (expr[0] :integer ))
while true do
if @debug
puts( "Debug: collapsing #{expr.inspect} on #{@stack.inspect}" )
end
if ( top[0] :open )
push expr
break;
elsif ( top[0] :start )
push expr
break;
elsif ( top[0] :binop )
op op
left op
expr :expr, op, left, expr]
elsif ( top[0] :unop )
op op
expr :expr, op, expr ]
else
throw "Syntax error #{expr.inspect}, #{@stack.inspect}"
end
end
else
throw "syntax error #{expr.inspect}, #{@stack.inspect}"
end
end
def operator( op )
prevop stack[-2]
if ( prevop[0] :binop ) || ( prevop[0] :unop )
if @@precedence[ op ] < @precedence[ prevop[1] ]
collapse_top
end
end
push [:binop, op]
@state start
end
def start(tok)
case tok
when "("
push [:open]
when /[0-9]/
t op
push [:integer, tok.to_i]
@state expr
when /[dD]/
push [:integer, 1]
push [:binop, :dice]
when "%"
if top[1] :dice
push [:integer, 100]
@state expr
else
throw "Syntax error at #{tok}"
end
else
throw "Syntax error at #{tok}"
end
end
def expr( tok )
case tok
when "END"
collapse_top
when /[dD]/
operator( :dice )
when "+"
operator( :plus )
when "*"
operator( :mult )
when "-"
operator( :minus )
when "/"
operator( :divide )
when ")"
collapse_top
expr op
open op
if open[0] ! open
throw "Syntax error : #{open.inspect}, #{expr.inspect}, #{@stack.inspect}"
end
push expr
when "("
push [:open]
@state start
else
push "ERROR"
end
end
end
¥»gin
This is the main interface to the whole thing: it parses an
expression and can evaluate it in different ways
ßÅ
class ParseTree
def initialize( source, debug alse )
@debug ebug
if source.kind_of?( String )
parse( source )
else
@tree ource.to_a
end
end
def to_a
@tree
end
def [](x)
@tree[x]
end
def parse( input )
session arser.new( @debug )
@tree ession.parse( input )
end
Operator_s :plus "+", :minus "-", :mult "*",
:divide "/", :dice "D" }
def subtree( lr )
if lr :left
return ParseTree.new( @tree[2], @debug )
elsif lr :right
return ParseTree.new( @tree[3], @debug )
end
end
def prettify
case ( @tree[0] )
when :integer
return @tree[1].to_s
when :expr
return "(" +
subtree(:left).prettify +
Operator_s[@tree[1][1]] +
subtree(:right).prettify +
")"
end
end
def evaluate_random
Evaluator.new( self ).evaluate { |x| x }
end
def evaluate_dist
Evaluator_dist.new( self ).evaluate { |x| x }
end
def evaluate_every
Evaluator_every.new( self ).evaluate do |x|
yield x
end
end
def evaluate_fudged( target )
Evaluator_every.new( self ).evaluate do |x|
if x.to_i target
return x
end
end
return "Cannot get #{target}"
end
end
# Subclass of Evaluator that yields every possible dice roll,
# with the probability of that specific roll
class Evaluator_every < Evaluator
class Roll_stat
def initialize( roll, path , prob0 )
@roll oll
@path ath
@p rob
end
def binop(other)
if ( other.kind_of?( Numeric ) )
other oll_stat.new(other)
end
Roll_stat.new( yield( @roll, other.roll ),
@path + other.path,
@p * other.p )
end
def + (other) ; binop(other) { |x,y| x+y } ; end
def * (other) ; binop(other) { |x,y| x*y } ; end
def - (other) ; binop(other) { |x,y| x-y } ; end
def / (other) ; binop(other) { |x,y| x/y } ; end
def concat( other )
binop(other) { |x,y| y }
end
def Roll_stat.make( n )
if ( n.kind_of?(Roll_stat) )
n
else
Roll_stat.new( n )
end
end
def to_s ; "#{roll}\t: #{path} p p}" ; end
def to_i ; @roll ; end
attr_reader :roll, :path, :p
end
def roll_one( sides )
if sides.kind_of?(Numeric) ; sides oll_stat.new(sides) ; end
sides.to_i.times do |n|
yield sides.concat(Roll_stat.new( n+1, "D#{sides.to_i} n+1} ", 1.0/(sides.to_i) ))
end
end
def null_value
Roll_stat.new(0)
end
def roll_dice( numdice, sides )
numdice oll_stat.make( numdice )
sides oll_stat.make( sides )
super( numdice.to_i, sides.to_i ) do |rolls|
yield( numdice.concat(sides).concat(rolls) )
end
end
def eval_binop( force_same_type rue )
subtree(:left).evaluate do |l|
subtree(:right).evaluate do |r|
if force_same_type
if r.kind_of?( Roll_stat ) and ! l.kind_of?( Roll_stat )
l oll_stat.new(l)
end
end
yield(l,r)
end
end
end
end
#Subclass of evaluator that returns
#a probability distribution for each dice roll
class Evaluator_dist < Evaluator
def null_value
return Freq_dist.new.integer(0)
end
def roll_one_fixed( sides )
if ( sides > )
return Freq_dist.new.uniform(sides)
else
throw "Error - tried to roll #{sides}-sided die"
end
end
def roll_one( sides )
if sides.kind_of?( Numeric )
yield roll_one_fixed( sides )
else
result req_dist.new
sides.prob.each do |pr|
result esult.merge( roll_one_fixed( pr.value ).scale_prob( pr.p ) )
end
yield result
end
end
def roll_dice( numdice, sides )
if numdice.kind_of?( Numeric )
yield( super( numdice, sides ) { |x| x } )
else
result req_dist.new
numdice.prob.each do |pr|
rolls r.value
if rolls < 0
throw "Negative number of dice #{rolls}"
end
score req_dist.new.integer(0)
pr.value.times do
score core + ( roll_one( sides ) { |x| x } )
end
result esult.merge( score.scale_prob( pr.p ) )
end
yield result
end
end
def eval_binop( force_same_type rue )
subtree(:left).evaluate do |l|
subtree(:right).evaluate do |r|
if force_same_type
if r.kind_of?( Freq_dist ) and ! l.kind_of?( Freq_dist )
l req_dist.new.integer(l)
end
end
yield(l,r)
end
end
end
end
# Extra test method
class ParseTree
def ParseTree.testp( input )
puts "\nParser test: #{input}\n\n"
t arseTree.new( input )
puts "Roll spec is #{t.prettify}\n\n"
puts "Parse tree is #{t.inspect}\n\n"
puts "Random roll: #{t.evaluate_random}\n\n"
puts "Distribution:\n#{t.evaluate_dist.to_s}\n\n"
puts "All possible rolls:"
t.evaluate_every do |outcome|
puts outcome.to_s
end
puts "\n\n"
end
end
case ARGV[0]
when "-full"
ParseTree.testp( ARGV[1] )
when "-test"
["d6", "3d4", "4*(d3)", "7+4*2d6", "dd8", "(d4)d4", "d10-d10"].each do |str|
ParseTree.testp( str )
end
when "-dist"
d arseTree.new(ARGV[1])
puts "Distribution:\n#{d.evaluate_dist.to_s}\n\n"
when "-cheat"
d arseTree.new(ARGV[1])
target RGV[2].to_i
puts d.evaluate_fudged( target )
when "-help"
puts "#{$0} expr [count]\n\tRoll dice as per expr (count times)"
puts "#{$0} -test\n\tRun some predefined expressions"
puts "#{$0} -dist expr\n\tProduce a probability distribution for an expression"
puts "#{$0} -cheat expr value\n\tFind dice rolls in expression that produce value"
puts "#{$0} -full expr\n\tDo everything with an expression, including listing every possible\n\tcombination of dice rolls (potentially very large output,\n\ttaking a very long time"
else
d arseTree.new(ARGV[0])
(ARGV[1] || 1).to_i.times { print "#{d.evaluate_random} " }
puts ""
end
--------------050407040609060308020901--