[QUIZ] Dice Roller (#61)

[Ross Bamford]

Hi,

This is my quiz entry for Ruby Quiz 61 (Dice Roller). It's actually the
second idea I had, after starting out with Antlr (I still finished that
one, because I wanted to get to grips with Antlr anyway - I happened to
be playing with it when this quiz came out ). I've bundled both this
entry and that one at:

http://roscopeco.co.uk/code/ruby-quiz-entries/quiz61-dice-roller.tar.gz

Anyway, back to my real entry. I guess I took the short-cut route to
the dice-roller, and instead of parsing out the expressions I instead
decided to 'coerce' them to Ruby code, by just implementing the 'd'
operator with a 'rolls' method on Fixnum, and using gsub to convert
the input expression.

d3*2 => 1.rolls(3)*2
(5d5-4)d(16/d4)+3 => (5.rolls(5)-4).rolls(16/1.rolls(4))+3
d%*7 => 1.rolls(100)*7

This is implemented in the DiceRoller.parse method, which returns the
string. You can just 'eval' this of course, or use the 'roll' method
(also provided as a more convenient class method that wraps the whole
thing up for you) to do it. Ruby runs the expression, and gives back
the result. I almost feel like I cheated...?

As well as the main 'roll.rb' I also included a separate utility that
uses loaded dice to find min/max achievable. All three files can be
executed, and if you enable --verbose mode on Ruby you'll see the
dice rolls and parsed expressions.

----------[MAIN (roll.rb)]-----------
#!/usr/local/bin/ruby
#
# Ruby Quiz 61, the quick way
# by Ross Bamford

# Just a debugging helper
module Kernel
def dbg(*s)
puts(*s) if $VERBOSE|| @dice_debug
end
attr_writer :dice_debug
def dice_debug?; @dice_debug; end
end

# Need to implement the 'rolls' method. Wish it didn't have to
# be on Fixnum but for this it makes the parsing *lots* easier.
class Fixnum
def self.roll_proc=(blk)
@roll_proc = blk
end

def self.roll_proc
@roll_proc ||= methodrand).to_proc
end

def rolls(sides)
(1..self).inject(0) { |s,v| s + Fixnum.roll_proc[sides] }
end
end

# Here's the roller.
class DiceRoller
class << self
# Completely wrap up a roll
def roll(expr, count = 1, debug = false)
new(expr,debug).roll(count)
end

# The main 'parse' method. Just really coerces the code to Ruby
# and then compiles to a block that returns the result.
def parse(expr)
# very general check here. Will pass lots of invalid syntax,
# but hopefully that won't compile later. This removes the
# possibility of using variables and the like, but that wasn't
# required anyway. The regexps would be a bit more difficult
# if we wanted to do that.
raise SyntaxError, "'#{expr}' is not a valid dice expression", [] if
expr =~ /[^d\d\(\)\+\-\*\/\%]|[^d]%|d-|\*\*/

# Rubify!
s = expr.gsub( /([^\d\)])d|^d/, '\11d') # fix e.g. 'd5'
and '33+d3' to '1.d5' and '33+1d3'
s.gsub!( /d%/, 'd(100)' ) # fix e.g. 'd%'
to 'd(100)'
s.gsub!( /d([\+\-]?\d+)/, '.rolls(\1)') # fix e.g. '3d8'
to '3.rolls(8) (*)
s.gsub!( /d\(/, '.rolls(') # fix e.g.
'2d(5+5)' to '2.rolls(5+5)'

# (*) This line treats + or - straight after 'd' as a unary sign,
# so you can have '3d-8*7' => '3.rolls(+8)-7'
# This would throw a runtime error from rolls, though.

# Make a block. Doing it this way gets Ruby to compile it now
# so we'll reliably get fail fast on bad syntax.
dbg "PARS: #{expr} => #{s}"
begin
eval("lambda { #{s} }")
rescue Exception => ex
raise SyntaxError, "#{expr} is not a valid dice expression", []
end
end
end

# Create a new roller that rolls the specified dice expression
def initialize(expr, debug = false)
dbg "NEW : #{to_s}: #{expr} => #{expr_code}"
@expr_code, @expr, @debug = expr, DiceRoller.parse(expr), debug
end

# Get hold of the original expression and compiled block, respectively
attr_reader :expr_code, :expr

# Roll this roller count times
def roll(count = 1)
dbg " ROLL: #{to_s}: #{count} times"
r = (1..count).inject([]) do |totals,v|
this_r = begin
expr.call
rescue Exception => ex
raise RuntimeError, "'#{expr_code}' raised: #{ex}", []
end

dbg " r#{v}: rolled #{this_r}"
totals << this_r
end

r.length < 2 ? r[0] : r
end
end

# Library usage:
#
# require 'roll'
#
# # is the default:
# # Fixnum.roll_proc = lambda { |sides| rand(sides) + 1 }
#
# DiceRoller.roll('1+2*d6')
#
# d = DiceRoller.new('((3d%)+8*(d(5*5)))')
# d.roll(5)
#
# d = DiceRoller.new('45*10d3') # debug
#
# # ... or
# one_roll = d.expr.call
#

# command-line usage
if $0 == __FILE__
unless expr = ARGV[0]
puts "Usage: ruby [--verbose] roll.rb expr [count]"
else
(ARGV[1] || 1).to_i.times { print "#{DiceRoller.roll(expr)} " }
print "\n"
end
end
=====================================




-----------[UTIL: minmax.rb]----------
#!/usr/local/bin/ruby

require 'roll'

LOW_DICE = lambda { |sides| 1 }
HIGH_DICE = lambda { |sides| sides }

# Adds a 'minmax' method that uses loaded dice to find
# min/max achievable for a given expression.
#
# Obviously not thread safe, but then neither is the
# whole thing ;D
class DiceRoller
def self.minmax(expr)
old_proc = Fixnum.roll_proc
Fixnum.roll_proc = LOW_DICE
low = DiceRoller.roll(expr)

Fixnum.roll_proc = HIGH_DICE
high = DiceRoller.roll(expr)
Fixnum.roll_proc = old_proc

[low,high]
end
end

if $0 == __FILE__
if expr = ARGV[0]
min, max = DiceRoller.minmax(expr)
puts "Expression: #{expr} ; min / max = #{min} / #{max}"
else
puts "Usage: minmax.rb <expr>"
end
end
=====================================





-----------[TEST: test.rb]----------
#!/usr/local/bin/ruby
#
# Ruby Quiz, number 61 - Dice roller
# This entry by Ross Bamford (rosco<at>roscopeco.co.uk)

require 'test/unit'
require 'roll'

ASSERTS = {
'1' => 1,
'1+2' => 3,
'1+3*4' => 13,
'1*2+4/8-1' => 1,
'd1' => 1,
'1d1' => 1,
'd10' => 10,
'1d10' => 10,
'10d10' => 100,
'd3*2' => 6,
'5d6d7' => 210, # left assoc
'2d3+8' => 14, # not 22
'(2d(3+8))' => 22, # not 14
'd3+d3' => 6,
'33+d3+10' => 46,
'd2*2d4' => 16,
'd(2*2)+d4' => 8,
'd%' => 100,
'2d%' => 200,
'd%*7' => 700,
'14+3*10d2' => 74,
'(5d5-4)d(16/d4)+3' => 87, #25d4 + 3
'3d+8/8' => 3 #3d(+8)/8
}

ERRORS = {

# Bad input, all should raise exception
'd' => SyntaxError,
'3d' => SyntaxError,
'3d-8' => SyntaxError, # - # of sides
'3ddd6' => SyntaxError,
'3%2' => SyntaxError,
'%d' => SyntaxError,
'+' => SyntaxError,
'4**3' => SyntaxError
}

# bit messy, but can't get class methods on Fixnum
Fixnum.roll_proc = lambda { |sides| sides }

class TestDiceRoller < Test::Unit::TestCase
def initialize(*args)
super
end

ASSERTS.each do |expr, expect|
eval <<-EOC
def test_good_#{expr.hash.abs}
expr, expect = #{expr.inspect}, #{expect.inspect}
puts "\n-----------------------\n\#{expr} => \#{expect}" if
$VERBOSE
res = DiceRoller.roll(expr)
puts "Returned \#{res}\n-----------------------" if $VERBOSE
assert_equal expect, res
end
EOC
end

ERRORS.each do |expr, expect|
eval <<-EOC
def test_error_#{expr.hash.abs}
expr, expect = #{expr.inspect}, #{expect.inspect}
assert_raise(#{expect}) do
puts "\n-----------------------\n\#{expr} => \#{expect}" if
$VERBOSE
res = DiceRoller.roll(expr)
puts "Returned \#{res}\n-----------------------" if $VERBOSE
end
end
EOC
end
end
=====================================

 

[Ross Bamford]

This is implemented in the DiceRoller.parse method, which returns the
string.

Sorry, I changed that. It gives a block now.

 

[Christer Nilsson]

Very interesting, and different solutions, this time!

Here's my recursive descent solution with histogram:

=begin
Ruby Quiz #61
by Matthew D Moss

Solution by Christer Nilsson

"3d6" gives 3..18 randomly

"(5d5-4)d(16/d4)+3"

Backus Naur Form:

expr: term ['+' expr | '-' expr]
term: fact ['*' term | '/' term]
fact: [unit] 'd' dice
unit: '(' expr ')' | integer
dice: '%' | term
integer: digit [integer]
digit: /[0-9]/

* Integers are positive
* The "d" (dice) expression XdY rolls a Y-sided die (numbered
from 1 to Y) X times, accumulating the results. X is optional
and defaults to 1.
* All binary operators are left-associative.
* Operator precedence:
( ) highest
d
* /
+ - lowest

Some game systems use d100 quite often, and may abbreviate it as "d%"
(but note that '%' is only allowed immediately after a 'd').
=end
class String
def behead
return ['',''] if self == ''
[self[0..0], self[1...self.size]]
end
end

class Array
def sum
inject(0) {|sum,e| sum += e}
end

def histogram(header="")
width = 100
each_index {|i| self=0 if self.nil?}
sum = self.sum
max = self.max if max.nil?
s = " " + header + "\n"
each_with_index do |x,i|
label = " " + format("%2.1f",100.0*x/sum)+"%"
s += format("%2d",i) + " " + "*" * ((x-min) * width / (max-min)) +
label + "\n"
end
s += "\n"
end
end

class Dice

def statistics(expr, n=1000)
prob = []
n.times do
value = evaluate(expr)
prob[value]=0 if prob[value].nil?
prob[value] += 1
end
prob
end

def evaluate s
@sym, @s = s.behead
@stack = []
expr
pop
end

def drop (pattern)
raise 'syntax error: expected ' + pattern unless pattern === @sym
@sym, @s = @s.behead
end

def push(x) @stack.push x end
def top2() @stack[-2] end
def top() @stack[-1] end
def pop() @stack.pop end

def calc value
pop
push value
end

def try symbol
return nil unless @sym == symbol
drop symbol
case symbol
when '+' then expr; calc top2 + pop
when '-' then expr; calc top2 - pop
when '*' then term; calc top2 * pop
when '/' then term; calc top2 / pop
when '%' then push 100
when '(' then expr; drop ')'
#when 'd' then dice; calc top2 * pop # debug mode
when 'd' # release mode
dice
sum = 0
sides = pop
count = pop
count.times {sum += rand(sides) + 1}
push sum
end
end

def expr
term
try('+') or try('-')
end

def term
fact
try('*') or try('/')
end

def fact
@sym == 'd' ? push(1) : unit # implicit 1
try('d')
end

def dice
#unit unless try('%')# if 5d6d7 is not accepted
term unless try('%') # if 5d6d7 is accepted
end

def unit
integer @sym.to_i unless try('(')
end

def integer(i)
return if @sym == ''
digit = /[0-9]/
drop(digit)
digit === @sym ? integer( 10 * i + @sym.to_i ) : push(i)
end
end

require 'test/unit'
class TestDice < Test::Unit::TestCase
def t (actual, expect)
assert_equal expect, actual
end
def test_all

t(/[0-9]/==="0", true)
t(/[0-9]/==="a", false)
t "abc".behead, ["a","bc"]
t "a".behead, ["a",""]
t "".behead, ["",""]

dice = Dice.new()
print dice.statistics("d6").histogram("d6")
print dice.statistics("2d6").histogram("2d6")
print dice.statistics("(d6)d6",10000).histogram("(d6)d6")

#t dice.evaluate("(6)"), 6
#t dice.evaluate("12+34"), 46
#t dice.evaluate("3*4+2"), 14
#t dice.evaluate("5+6+7"), 18
#t dice.evaluate("5+6-7"), 4
#t dice.evaluate("(5+6)+7"), 18
#t dice.evaluate("5"), 5
#t dice.evaluate("5+(6+7)"), 18
#t dice.evaluate("(5+6+7)"), 18
#t dice.evaluate("5*6*7"), 210
#t dice.evaluate("2+3*4"), 14
#t dice.evaluate("12+13*14"), 194
#t dice.evaluate("(2+3)*4"), 20
#t dice.evaluate("(5d5-4)d(16/1d4)+3"), 45
#t dice.evaluate("(5d5-4)d(400/1d%)+3"), 87
#t dice.evaluate("1"), 1
#t dice.evaluate("1+2"),3
#t dice.evaluate("1+3*4"),13
#t dice.evaluate("1*2+4/8-1"), 1
#t dice.evaluate("d1"),1
#t dice.evaluate("1d1"),1
#t dice.evaluate("1d10"), 10
#t dice.evaluate("10d10"),100
#t dice.evaluate("d3*2"), 6
#t dice.evaluate("2d3+8"), 14
#t dice.evaluate("(2*(3+8))"),22
#t dice.evaluate("d3+d3"),6
#t dice.evaluate("d2*2d4"),16
#t dice.evaluate("2d%"),200
#t dice.evaluate("14+3*10d2"), 74
#t dice.evaluate("(5d5-4)d(16/d4)+3"),87
#t dice.evaluate("d10"), 10
#t dice.evaluate("d%"),100
#t dice.evaluate("d(2*2)+d4"),8
#t dice.evaluate("(5d6)d7"), 210
#t dice.evaluate("5d(6d7)"), 210
#t dice.evaluate("5d6d7)"), 210
#t dice.evaluate("12d13d14)"), 2184
#t dice.evaluate("12*d13)"), 156
#t dice.evaluate("12+d13)"), 25
end
end

 

[Pierre Barbier de Reuille]

Well, here is my first solution to a quizz ^^
I tried to use racc for that ... so you need to generate the ruby script
using :

$ racc roll.y -o roll.rb

Otherwise, it is pretty simple ...

A small explanation is included within the file. If needed, I will post
the generated file.

Pierre

# -*- ruby -*-
# How to get the ruby program :
# racc roll.y -o roll.rb
#
# Design :
# The class Dice correspond to a very general dice. In my programme, "d6" is
# dice, but so are "3d6" and "(2d6-3)d(3d4)". A dice simply holds Proc which,
# when evaluated, return a random integer corresponding to a (simple or
# multiple) dice roll. The dices may be combined using standard arithmetic
# operators (+,-,*,/). These operator simply create Proc that roll the two
# argument dices. In the design, an integer is considered a d1. However the
# Proc for d1 don't use random ... (hopefully
#
# The tokenize method is pretty simple and the "%" is handled here, replaced
# by 100 automatically. Basically, it skips spaces (which flushes the char
# buffer however, so that "10 10" is invalid), gather consecutive figures
# into numbers and each char is considered an independant token.
#
# Every grammar aspect is taken care by Racc ...
class DiceParser

prechigh
nonassoc UMINUS
nonassoc SHORTD
left 'd'
left '*' '/'
left '+' '-'
preclow

rule
target: exp
| /* none */ { result = Dice.new 0 }

exp: exp '+' exp { result += val[2] }
| exp '-' exp { result -= val[2] }
| exp '*' exp { result *= val[2] }
| exp '/' exp { result /= val[2] }
| '(' exp ')' { result = val[1] }
| '-' NUMBER = UMINUS { result = Dice.new(-val[1]) }
| NUMBER { result = Dice.new val[0] }
| exp 'd' exp { result = Dice.new val[0], val[2] }
| 'd' exp = SHORTD { result = Dice.new 1, val[1] }

---- header

$debug_dice = false
$debug_token = false

class Dice

attr_reader :size, :act

def initialize(number, size = 1)
@size = size
if number.respond_to? :to_proc
puts "Initialize with proc" if $debug_dice
@act = number.to_proc
@size = 0
elsif size == 1 then
puts "Initialize with 1-sided dice(s)" if $debug_dice
@act = lambda { number }
else
puts "Initialize with full dice(s)" if $debug_dice
number = Dice.new number unless number.respond_to? :roll # at that point, number must be a Dice
@act = lambda do
result = 0
s = size.roll
n = number.roll
result = (1..n.to_i).inject(0) { |sum,ii| sum + random(s) }
puts "Rolling #{n}d#{s} = #{result}" if $debug_dice
result
end
end
end

def random(sides)
rand(sides)+1
end

def roll
act[]
end

def self.define_op(op)
module_eval <<-EOF
def #{op}(other)
if (size == 1) && (other.size == 1) then
Dice.new(self.roll #{op} other.roll)
else
Dice.new(lambda { self.roll #{op} other.roll })
end
end
EOF
end

define_op :+
define_op :*
define_op :-
define_op :/

end

---- inner

attr_accessor :string, :result

def parse( str )
@result = []
#@yydebug = true
@string = str
yyparse( self, :tokens )
end

def tokens
buffer = ""
string.each_byte do |b|
print "b=#{b}/#{b.chr}, buffer = '#{buffer}'\n" if $debug_token
case b
when ?0..?9
buffer << b.chr
print "Added #{b.chr} to buffer => #{buffer}\n" if $debug_token
when [?\ ,?\t,?\n]
yield :NUMBER, buffer.to_i unless buffer.empty?
print "Pushing : #{buffer}\n" unless buffer.empty? if $debug_token
buffer = ""
when ?%
yield :NUMBER, buffer.to_i unless buffer.empty?
print "Pushing : #{buffer}\n" unless buffer.empty? if $debug_token
yield :NUMBER, 100
else
yield :NUMBER, buffer.to_i unless buffer.empty?
print "Pushing : #{buffer}\n" unless buffer.empty? if $debug_token
buffer = ""
yield b.chr, b.chr
print "Pushing : #{b.chr}\n" if $debug_token
end
end
yield :NUMBER, buffer.to_i unless buffer.empty?
print "Pushing : #{buffer}\n" unless buffer.empty? if $debug_token
yield false, '$end'
end

---- footer

string = ARGV[0]

# puts "Parsing : '#{string}'"
value = DiceParser.new.parse( string )

num = ARGV[1] || 1

num.to_i.times do
print "#{value.roll} "
end
print "\n"

 

[Austin Ziegler]

------=_Part_81463_5176244.1136752140088
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

Here is my submission. Yes, this is my first completed Ruby Quiz
Thanks to Eric Mahurin's syntax.rb for making this work. I've attached
it as well, because it's not easily accessible otherwise

-austin

------=_Part_81463_5176244.1136752140088
Content-Type: application/octet-stream; name=roll.rb
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment; filename="roll.rb"

#! /usr/bin/env ruby

require 'syntax'

# Ruby Quiz #61 by Matthew D Moss
# Submission by Austin Ziegler
#
# > roll.rb "3d6" 6
# 12 7 13 16 11 17
#
# Or, for something more complicated:
#
# > roll.rb "(5d5-4)d(16/d4)+3"
# 31
#
# The main code of roll.rb should look something like this:
#
# d = Dice.new(ARGV[0])
# (ARGV[1] || 1).to_i.times { print "#{d.roll} " }
#
# I've implemented it with a modified BNF and Eric Mahurin's syntax.rb.
#
# integer : "1" - "9" [ "0" - "9" ]*
# white : [ " " | "\t" | "\n" ]*
# unit : "(" expr ")" | integer
# dice : "%" | unit
# term : unit? [ "d" dice ]*
# fact : term [ "*" | "/" term ]*
# expr : fact [ "+" | "-" fact ]*
#
# I have also modified the core function as:
#
# e = ARGV[0]
# c = (ARGV[1] || 1).to_i
# d = Dice.new(e)
# puts d.roll(c).join(" ")

NULL = Syntax::NULL
INF = +1.0 / 0.0
LOOP0 = (0 .. INF)
LOOP1 = (1 .. INF)

class Dice
def initialize(dice)
@dice = dice
@dice_n = "#{@dice}\n"

integer = ((("1" .. "9") * 1) + ("0" .. "9") * LOOP0).qualify do |m|
m.to_s.to_i
end
white = ((" " | "\t" | "\n") * LOOP0).qualify { TRUE }

expr = Syntax:ass.new

unit = ("(" + expr + ")").qualify { |m| m[1] } |
integer.qualify { |m| m }

dice = "%".qualify { |m| 100 } | unit.qualify { |m| m }

term = ((unit | NULL) + (white + "d" + white + dice) * LOOP0).qualify do |m|
sum = 0

if m[1].nil?
rep = 1
xpr = m[0]
elsif m[1].empty?
sum = m[0]
xpr = m[1]
else
rep = m[0]
xpr = m[1]
end

xpr.each do |mm|
case mm[0]
when "d": sum = (1..rep).inject(sum) { |s, i| s + (rand(mm[1]) + 1) }
else
sum += rep
end
end
sum
end

fact = (term + (white + ("*" | "/") + white + term) * LOOP0).qualify do |m|
prod = m[0]

m[1].each do |mm|
case mm[0]
when "*": prod *= mm[1]
when "/": prod /= mm[1]
end
end

prod
end

expr << (white + fact + (white + ("+" | "-") + white + fact) * LOOP0).qualify do |m|
sum = m[0]
m[1].each do |mm|
case mm[0]
when "+": sum += mm[1]
when "-": sum -= mm[1]
end
end
sum
end

@die_expr = expr
end

def roll(times = 1)
(1 .. times).map { @die_expr === RandomAccessStream.new(@dice_n) }
end

def inspect
@dice
end
end

expr = ARGV[0]
count = (ARGV[1] || 1).to_i

if expr
d = Dice.new(expr)

puts d.roll(count).join(' ')
else
require 'test/unit'

class TestDice < Test::Unit::TestCase
def test_simple
assert (1..4).include?(Dice.new("d4").roll)
assert (1..6).include?(Dice.new("d6").roll)
assert (1..8).include?(Dice.new("d8").roll)
assert (1..10).include?(Dice.new("d10").roll)
assert (1..12).include?(Dice.new("d12").roll)
assert (1..20).include?(Dice.new("d20").roll)
assert (1..30).include?(Dice.new("d30").roll)
assert (1..100).include?(Dice.new("d100").roll)
assert (1..100).include?(Dice.new("d%").roll)
end

def test_3d6
assert (3..18).include?(Dice.new("3d6").roll)
end

def test_complex
assert (5..25).include?(Dice.new("5d5").roll)
assert (1..21).include?(Dice.new("5d5-4").roll)
assert [4, 5, 8, 16].include?(Dice.new("16/d4").roll)
assert (1..336).include?(Dice.new("(5d5-4)d(16/d4)").roll)
assert (4..339).include?(Dice.new("(5d5-4)d(16/d4)+3").roll)
end
end
end

------=_Part_81463_5176244.1136752140088
Content-Type: application/octet-stream; name=syntax.rb
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment; filename="syntax.rb"

# Classes in this module allow one to define BNF-like grammar directly in
# Ruby
# Author: Eric Mahurin
# License: free, but you are at your own risk if you use it

module Syntax
# base class where common operators are defined
class Base
def |(other)
Alteration.new(self,other)
end
def +(other)
Sequence.new(self,other)
end
def *(multiplier)
Repeat.new(self,multiplier)
end
def +@
Positive.new(self)
end
def -@
Negative.new(self)
end
def qualify(*args,&code)
Qualify.new(self,*args,&code)
end
end

# just passes the syntax through - needed for recursive syntax
class Pass < Base
def initialize(syntax=NULL)
@syntax =
if (syntax.kind_of?Base)
syntax
else
Verbatim.new(syntax)
end
end
def <<(syntax)
initialize(syntax)
end
def ===(stream)
@syntax===stream
end
end

# generic code matches to the stream (first arg to the code)
# [] operator allows additional arguments to be passed to the code
class Code < Base
def initialize(*args,&code)
@args = args
@code = code
end
def ===(stream,*args) # passing args here will bypass creating a new object
(match = @code[stream,*(@args+args)]) ||
stream.buffered || raise(Error.new(stream,"a semantic error"))
match
end
def [](*args)
self.class.new(*(@args+args),&@code)
end
end

# qualify the match with some code that takes the match
# [] operator allows additional arguments to be passed to the code
class Qualify < Base
def initialize(syntax=NULL,*args,&code)
@syntax =
if (syntax.kind_of?Base)
syntax
else
Verbatim.new(syntax)
end
@args = args
@code = code
end
def ===(stream,*args) # passing args here will bypass creating a new object
(match = (@syntax===stream)) || (return match)
(match = @code[match,*(@args+args)]) ||
stream.buffered || raise(Error.new(stream,"a semantic qualification error"))
match
end
def [](*args)
self.class.new(@syntax,*(@args+args),&@code)
end
end

# sequence of syntaxes
class Sequence < Base
def initialize(*syntaxes)
@syntax = syntaxes.collect do |syntax|
if (syntax.kind_of?Base)
syntax
else
Verbatim.new(syntax)
end
end
end
def +(other)
self.class.new(*(@syntax+[other])) # pull in multiple sequence items
end
def <<(other)
@syntax << ((other.kind_of?Base)?other:Verbatim.new(other))
end
def ===(stream)
matches = []
@syntax.each do |syntax|
match = (syntax===stream)
if (!match)
matches=NIL
break
end
matches << match if match!=TRUE
end
matches
end
end

# alternative syntaxes
class Alteration < Base
def initialize(*syntaxes)
@syntax = syntaxes.collect do |syntax|
if (syntax.kind_of?Base)
syntax
else
Verbatim.new(syntax)
end
end
end
def |(other)
self.class.new(*(@syntax+[other])) # pull in multiple alteration items
end
def <<(other)
@syntax << ((other.kind_of?Base)?other:Verbatim.new(other))
end
def ===(stream)
match = nil
@syntax.detect do |syntax|
match = stream.buffer { |stream| syntax===stream }
end
match || stream.buffered || raise(Error.new(stream,nil,"an alteration"))
match
end
alias =~ ===
end

# repeating syntax
class Repeat < Base
def initialize(syntax,multiplier)
@syntax =
if (syntax.kind_of?Base)
syntax
else
Verbatim.new(syntax)
end
@repeat =
if (multiplier.kind_of?Proc)
multiplier
else
lambda do |matches|
compare = (multiplier<=>(matches.length+1))
if (compare==0)
compare = (multiplier<=>matches.length)
end
compare
end
end
end
def ===(stream)
matches = []
while ((compare=@repeat[matches])>=0)
if (compare>0)
unless (match = (@syntax===stream))
return NIL
end
else
unless (match = stream.buffer { |stream| @syntax===stream })
break
end
end
matches << match
end
# filter out simple TRUE elements
matches = matches.find_all { |match| match!=TRUE }
matches
end
end

# positive syntactic predicate
class Positive < Base
def initialize(syntax)
@syntax =
if (syntax.kind_of?Base)
syntax
else
Verbatim.new(syntax)
end
end
def ===(stream)
stream.buffer { |stream| match = (@syntax===stream); FALSE }
if (match)
TRUE
else
stream.buffered || raise(Error.new(stream,nil,"a positive syntatic predicate"))
FALSE
end
end
end

# negative syntactic predicate
class Negative < Positive
def ===(stream)
stream.buffer { |stream| match = (@syntax===stream); FALSE }
if (!match)
TRUE
else
stream.buffered || raise(Error.new(stream,nil,"a negative syntatic predicate"))
FALSE
end
end
end

# all atoms can also use ~ to invert what's matches

# element match (uses === to match)
class Atom < Base
def initialize(pattern,length=NIL,invert=FALSE)
@pattern = pattern
@length = length
@invert = invert
end
def ~@
new(pattern,length,!invert)
end
def ===(stream)
element = stream.get(@length)
match = (@pattern===element)
match = !match if (@invert)
if (match==TRUE)
element || TRUE
else
match || begin
stream.buffered || raise(Error.new(stream,element.inspect,@pattern.inspect))
FALSE
end
end
end
end

# element set (uses include? to match)
class Set < Atom
def ===(stream)
element = stream.get(@length)
match = @pattern.include?(element)
match = !match if (@invert)
if (match==TRUE)
element || TRUE
else
match || begin
stream.buffered || raise(Error.new(stream,element.inspect,"one of these: #{@pattern.to_s}"))
FALSE
end
end
end
end

# element lookup array or hash (uses [] to match)
# translation will occur if the lookup returns anything but TRUE
class Lookup < Atom
def =~(stream)
element = stream.get(@length)
match = @pattern[element]
match = !match if (@invert)
if (match==TRUE)
element || TRUE
else
match || begin
stream.buffered || raise(Error.new(stream,element.inspect,"one of these: #{@pattern.keys.to_s}"))
FALSE
end
end
end
end

# element sequence that knows its length
class Verbatim < Atom
def initialize(pattern,invert=FALSE)
@pattern = pattern
@invert = invert
end
def ~@
new(pattern,!invert)
end
def ===(stream)
element = stream.get(@pattern.length)
if (element)
match = (@pattern===element)
match = !match if (@invert)
else
match = FALSE
end
if (match==TRUE)
element || TRUE
else
match || begin
stream.buffered || raise(Error.new(stream,element.inspect,@pattern.inspect))
FALSE
end
end
end
end

# any element
class Any < Atom
def initialize(length=NIL,invert=FALSE)
@length = length
@invert = invert
end
def ~@ # create a never matching Atom
new(length,!invert)
end
def ===(stream)
element = stream.get(@length)
!@invert && element
end
end
ANY = Any.new


# zero length constants
FLUSH = Code.new { |stream| stream.flush; TRUE }
FAIL = Code.new { FALSE }
NULL = Code.new { TRUE }
NULLS = Code.new { [] }
EOF = Code.new { !(element = stream.get) }

# exception class for handling syntax errors
class Error < RuntimeError
attr_accessorstream,:found,:expected)
def initialize(stream=nil,found=nil,expected=nil)
@stream = stream
@found = found
@expected = expected
end
def to_s
err = [super]
err << "found #{found.to_s}" if found
err << "expected #{expected.to_s}" if expected
err << stream.location.to_s if stream
err * ", "
end
end

end

# class acts like an iterator over a string/array/etc except that using
# buffer allows one go back to a certain point another class could be
# designed to work on an IO/File
class RandomAccessStream
def initialize(s,pos=0)
@s = s
@pos = pos
@buffered = NIL
self
end
def get(termination=NIL)
if (@pos>[email protected])
# end of file/string/array
element = NIL
elsif (!termination)
# read one character/element
element = @s[@pos]
@pos += 1
else
# read a sub-string/sub-array
pos1 = (termination.kind_of?(Integer)) ? @pos+termination :
(t = @s.index(termination,@pos)) ? t+termination.length :
@s.length
element = @s[@pos...pos1]
@pos = pos1
end
element
end
def buffer(&code)
old_buffered = @buffered
@buffered = @pos if (!@buffered || @pos<@buffered)
pos = @pos
match = NIL
match = code[self]
if (@buffered && @buffered<=pos)
@buffered = old_buffered
elsif (!match)
raise(IndexError,"need to rewind buffer, but it was flushed")
end
@pos = pos if !match
match
end
def flush
@buffered = NIL
end
def buffered
@buffered ? TRUE : FALSE
end
def location
"index #{@pos} in #{@s.inspect}"
end
end

# Put stuff in String to have Syntax objects magically appear.
class String
def |(other)
Syntax::Verbatim.new(self)|other
end
def +@
+Syntax::Verbatim.new(self)
end
def -@
-Syntax::Verbatim.new(self)
end
alias _repeat *
def *(other)
if (other.kind_of?Numeric)
_repeat(other)
else
Syntax::Verbatim.new(self)*other
end
end
alias _concat +
def +(other)
if (other.kind_of?String)
_concat(other)
else
Syntax::Verbatim.new(self)+other
end
end
def ===(other)
if (other.kind_of?String)
self==other
else
Syntax::Verbatim.new(self)===other
end
end
def qualify(&code)
Syntax::Verbatim.new(self).qualify(&code)
end
end

# Allow an Array to look more like a Hash with keys and values
class Array
def keys
(0...length).find_all { |i| self }
end
def values
find_all { | element | element }
end
end

# make things fully comparable to Ranges
# also * makes a Syntax
class Range
include Comparable
def <=>(other)
if (other<self.begin)
+1
elsif (if exclude_end? then other>=self.end else other>self.end end)
-1
else
0
end
end
alias _old_equal ==
def ==(other)
if (other.kind_of?Range)
# undocumented previous functionality
_old_equal(other)
else
(self<=>other)==0
end
end
def *(other)
Syntax::Atom.new(self,1)*other
end
end

------=_Part_81463_5176244.1136752140088--

 

[Pablo Hoch]

Here is my solution. I convert the expression into RPN (using the algorithm
described in the Wikipedia article) and then calculate it (I have added a
'd' method to Fixnum so that I can use it like the standard arithmetic
operators). My solution is not very strict, so it allows '%' as an alias for
100 anywhere in the expression (not just after a 'd'), but I think that
should not be a big problem. It also ignores other characters, so whitespace
is allowed anywhere.


Pablo

---

#!/usr/bin/ruby

class Fixnum
def d(b)
(1..self).inject(0) {|s,x| s + rand(b) + 1}
end
end

class Dice

def initialize(exp)
@expr = to_rpn(exp)
end

def roll
stack = []
@expr.each do |token|
case token
when /\d+/
stack << token.to_i
when /[-+*\/d]/
b = stack.pop
a = stack.pop
stack << a.send(token.to_sym, b)
end
end
stack.pop
end

private

def to_rpn(infix)
stack, rpn, last = [], [], nil
infix.scan(/\d+|[-+*\/()d%]/) do |token|
case token
when /\d+/
rpn << token
when '%'
rpn << "100"
when /[-+*\/d]/
while stack.any? && stronger(stack.last, token)
rpn << stack.pop
end
rpn << "1" unless last =~ /\d+|\)|%/
stack << token
when '('
stack << token
when ')'
while (op = stack.pop) && (op != '(')
rpn << op
end
end
last = token
end
while op = stack.pop
rpn << op
end
rpn
end

def stronger(op1, op2)
(op1 == 'd' && op2 != 'd') || (op1 =~ /[*\/]/ && op2 =~ /[-+]/)
end

end

if $0 == __FILE__
d = Dice.new(ARGV[0])
(ARGV[1] || 1).to_i.times { print "#{d.roll} " }
end

 

[Dennis Ranke]

Hi,

Here is my solution #1 for this nice quiz. Hacky and short, without (!)
using eval...

module Dice
def self.roll(expr)
expr = expr.gsub(/\s/, '')
while
expr.sub!(/\(([^()]+)\)/) { roll($1) } ||
expr.sub!(/(\A|[^\d])\-\-(\d+)/, '\\1\\2') ||
expr.sub!(/d%/, 'd100') ||
expr.sub!(/(\d+)d(\d+)/) { (1..$1.to_i).inject(0) {|a, b| a +
rand($2.to_i) + 1} } ||
expr.sub!(/d(\d+)/, '1d\\1') ||
expr.sub!(/(\d+)\/(\-?\d+)/) { $1.to_i / $2.to_i } ||
expr.sub!(/(\d+)\*(\-?\d+)/) { $1.to_i * $2.to_i } ||
expr.sub!(/(\-?\d+)\-(\-?\d+)/) { $1.to_i - $2.to_i } ||
expr.sub!(/(\-?\d+)\+(\-?\d+)/) { $1.to_i + $2.to_i }
end
return $1.to_i if /\A(\-?\d+)\Z/ =~ expr
raise "Error evaluating dice expression, stuck at '#{expr}'"
end
end

(ARGV[1] || 1).to_i.times { print "#{Dice.roll(ARGV[0])} " }
puts

 

[Dennis Ranke]

Hi,

here is my second solution. Quite a bit longer, but a lot nicer.
For this I implemented a simple recursive descent parser class that
allows the tokens and the grammar to be defined in a very clean ruby
syntax. I think I'd really like to see a production quality
parser(generator) using something like this grammar format.

class RDParser
attr_accessor os
attr_reader :rules

def initialize(&block)
@lex_tokens = []
@rules = {}
@start = nil
instance_eval(&block)
end

def parse(string)
@tokens = []
until string.empty?
raise "unable to lex '#{string}" unless @lex_tokens.any? do |tok|
match = tok.pattern.match(string)
if match
@tokens << tok.block.call(match.to_s) if tok.block
string = match.post_match
true
else
false
end
end
end
@pos = 0
@max_pos = 0
@expected = []
result = @start.parse
if @pos != @tokens.size
raise "Parse error. expected: '#{@expected.join(', ')}', found
'#{@tokens[@max_pos]}'"
end
return result
end

def next_token
@pos += 1
return @tokens[@pos - 1]
end

def expect(tok)
t = next_token
if @pos - 1 > @max_pos
@max_pos = @pos - 1
@expected = []
end
return t if tok === t
@expected << tok if @max_pos == @pos - 1 && [email protected]?(tok)
return nil
end

private

LexToken = Struct.newpattern, :block)

def token(pattern, &block)
@lex_tokens << LexToken.new(Regexp.new('\\A' + pattern.source), block)
end

def start(name, &block)
rule(name, &block)
@start = @rules[name]
end

def rule(name)
@current_rule = Rule.new(name, self)
@rules[name] = @current_rule
yield
@current_rule = nil
end

def match(*pattern, &block)
@current_rule.add_match(pattern, block)
end

class Rule
Match = Struct.new attern, :block

def initialize(name, parser)
@name = name
@parser = parser
@matches = []
@lrmatches = []
end

def add_match(pattern, block)
match = Match.new(pattern, block)
if pattern[0] == @name
pattern.shift
@lrmatches << match
else
@matches << match
end
end

def parse
match_result = try_matches(@matches)
return nil unless match_result
loop do
result = try_matches(@lrmatches, match_result)
return match_result unless result
match_result = result
end
end

private

def try_matches(matches, pre_result = nil)
match_result = nil
start = @parser.pos
matches.each do |match|
r = pre_result ? [pre_result] : []
match.pattern.each do |token|
if @parser.rules[token]
r << @parser.rules[token].parse
unless r.last
r = nil
break
end
else
nt = @parser.expect(token)
if nt
r << nt
else
r = nil
break
end
end
end
if r
if match.block
match_result = match.block.call(*r)
else
match_result = r[0]
end
break
else
@parser.pos = start
end
end
return match_result
end
end
end

parser = RDParser.new do
token(/\s+/)
token(/\d+/) {|m| m.to_i }
token(/./) {|m| m }

start :expr do
matchexpr, '+', :term) {|a, _, b| a + b }
matchexpr, '-', :term) {|a, _, b| a - b }
matchterm)
end

rule :term do
matchterm, '*', :dice) {|a, _, b| a * b }
matchterm, '/', :dice) {|a, _, b| a / b }
matchdice)
end

def roll(times, sides)
(1..times).inject(0) {|a, b| a + rand(sides) + 1 }
end

rule :dice do
matchatom, 'd', :sides) {|a, _, b| roll(a, b) }
match('d', :sides) {|_, b| roll(1, b) }
matchatom)
end

rule :sides do
match('%') { 100 }
matchatom)
end

rule :atom do
match(Integer)
match('(', :expr, ')') {|_, a, _| a }
end
end

(ARGV[1] || 1).to_i.times { print "#{parser.parse(ARGV[0])} " }
puts

 

[James Edward Gray II]

Here is my solution. I convert the expression into RPN (using the
algorithm
described in the Wikipedia article) and then calculate it (I have
added a
'd' method to Fixnum so that I can use it like the standard arithmetic
operators).

Wow. That is very cool. Thanks for sharing!

James Edward Gray II

 

[Ross Bamford]

Sorry for the noise.

Sorry, I changed that. It gives a block now.

There were a few other inaccuracies in the comments, where I'd obviously
not been merciless enough when refactoring. Specifically, a (*) comment
about one of the parse regexps (no longer applies) and a comment in the
tests about Fixnum and class methods (from before I realised my error).
Oh, and a debug message used still referenced an attr that was no longer
set up at that point.

I updated the archive at the link I posted with those removed, and also
took the chance to slip in a tiny fix for whitespace (just remove it all
at the start of the parse) but I guess it doesn't 'count' for the quiz

Anyway, thanks all concerned for the fun quiz - this is the first one I've
done so take it easy on my solution

(Oh, and I missed [SOLUTION] before and since a lot of people seem to be
doing that I felt just [QUIZ] might get missed).

The original solution post was this one:

http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/174815

 

[James Edward Gray II]

For this I implemented a simple recursive descent parser class that
allows the tokens and the grammar to be defined in a very clean
ruby syntax.
Awesome!

I think I'd really like to see a production quality parser
(generator) using something like this grammar format.

I agree. This is fantastic.

So what do we have to do to get you to add the polish and make it
available?

James Edward Gray II

 

[Dominik Bathon]

Here is my solution.

It's a recursive descent parser, that parses the full BNF posted by =20
Matthew Moss. It doesn't "compile" the expresion into nodes or something =
=20
similar, instead it evaluates the expression while parsing (so it has to =
=20
be reparsed for every dice rolling). It uses StringScanner, which was =20
quite handy for this task. (And it also uses eval() ;-)

Dominik


require "strscan"

class Dice
def initialize(expr)
@expr =3D expr.gsub(/\s+/, "")
end

def roll
s =3D StringScanner.new(@expr)
res =3D expr(s)
raise "garbage after end of expression" unless s.eos?
res
end

private

def split_expr(s, sub_expr, sep)
expr =3D []
loop do
expr << send(sub_expr, s)
break unless s.scan(sep)
expr << s[1] if s[1]
end
expr
end

def expr(s)
eval(split_expr(s, :fact, /([+\-])/).join)
end

def fact(s)
eval(split_expr(s, :term, /([*\/])/).join)
end

def term(s)
first_rolls =3D s.match?(/d/) ? 1 : unit(s)
dices =3D s.scan(/d/) ? split_expr(s, :dice, /d/) : []
dices.inject(first_rolls) do |rolls, dice|
raise "invalid dice (#{dice})" unless dice > 0
(1..rolls).inject(0) { |sum, _| sum + rand(dice) + 1 }
end
end

def dice(s)
s.scan(/%/) ? 100 : unit(s)
end

def unit(s)
if s.scan(/(\d+)/)
s[1].to_i
else
unless s.scan(/\(/) && (res =3D expr(s)) && s.scan(/\)/)
raise "error in expression"
end
res
end
end
end

if $0 =3D=3D __FILE__
begin
d =3D Dice.new(ARGV[0])
puts (1..(ARGV[1] || 1).to_i).map { d.roll }.join(" ")
rescue =3D> e
puts e
end
end

 

[horndude77]

I didn't try anything fancy for this. I did try to get eval to do all
the work, but ran into too many problems. Here's my solution:

$searches = [
[/\(\d*\)/, lambda{|m| m[1..-2]}],
[/^d/, lambda{|m| "1d"}],
[/d%/, lambda{|m| "d100"}],
[/(\+|-|\*|\/|\()d\d+/, lambda{|m| m[0..0]+'1'+m[1..-1]}],
[/\d+d\d+/, lambda{|m| dice(*m.split('d').map {|i|i.to_i}) }],
[/\d+(\*|\/)\d+/, lambda{|m| eval m}],
[/\d+(\+|-)\d+/, lambda{|m| eval m}]
]
def parse(to_parse)
s = to_parse
while(s =~ /d|\+|-|\*|\/|\(|\)/)
$searches.each do |search|
if(s =~ search[0]) then
s = s.sub(search[0], &search[1])
break
end
end
end
s
end

def dice(times, sides)
Array.new(times){rand(sides)+1}.inject(0) {|s,i|s+i}
end

srand
string = ARGV[0]
(puts "usage: #{$0} <string> [<iterations>]"; exit) if !string
(ARGV[1] || 1).to_i.times { print parse(string), ' ' }



-----Horndude77

 

[Andrew McGuinness]

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=2 D5=5 D12=12 D12=12 p=0.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 = true )
subtreeleft).evaluate do |l|
subtreeright).evaluate do |r|
if force_same_type
if r.kind_of?( Roll_stat ) and ! l.kind_of?( Roll_stat )
l = Roll_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.


#!/usr/bin/env ruby

=begin
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
=end
class Freq_dist

class Freq
attr_accessor :value,
def initialize( v, p )
@value = v
@p = p
end
def <=> ( other )
@value <=> other.value
end
def to_s
print "[#{value},#{p}] "
end
end

attr_reader rob

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 = dist
self
end

def to_s
string=""
check_total = 0.0
@prob.each do |el|
string += ( "#{el.value}\t#{el.p}\n" )
check_total += el.p
end
string += ( "Check total: #{check_total}\n" )
string += stats
end

def coalesce
[email protected]
@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

=begin
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
=end
def merge ( other )
new_dist = Freq_dist.new.set_arr(@prob + (other.prob))
new_dist.coalesce
new_dist
end

def scale_prob( factor )
new_dist = Freq_dist.new.set_arr( @prob.map { |x| Freq.new( x.value, x.p * factor ) } )
end

=begin
These produce the distribution of a random variable which
is a function of two other random variables with distributions
provided (self and other
=end
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 = Freq_dist.new
result.set_arr( new_dist.sort )
result.coalesce
result
end

def combine_int( x )
result = Freq_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 = mean
sig_x2 - mu * mu
end

def std_dev
Math.sqrt( var )
end

def stats
"Mean #{mean} std. dev #{std_dev}"
end
end

=begin
This evaluates an already-parsed expression, generating an
appropriate random number for each dice roll
=end
class Evaluator
def initialize( parent )
@parsed_expr = parent
end

def null_value
return 0
end

def subtree(side)
self.class.new(@parsed_expr.subtree(side))
end

def eval_binop( force_same_type = true )
subtreeleft).evaluate do |l|
subtreeright).evaluate do |r|
yield(l,r)
end
end
end

def roll_one( sides )
val = 1 + 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 lus
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 = false )
@stack = [[:start]]
@state = :start
@debug = debug
end

@@precedence = { :dice => 4, lus => 2, :minus =>2, :mult => 3, :divide =>3 }

def tokenise( input )
pos = 0
len = input.length
while ( pos < len ) do
ch = input[pos..pos]
if "()+-dD*/%".include? ch
yield ch
elsif " \n\t".include? ch
;
elsif ch =~ /[0-9]/
numpos = pos
while ( ( pos+1 < len ) && ( input[pos+1..pos+1] =~ /[0-9]/ ))
pos += 1
end
yield input[numpos..pos]
else
throw "invalid char #{ch}"
end
pos += 1
end
yield "END"
end

def parse( str )
tokenise( str ) do |t|
parse_t( t )
end
tree = pop
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 = pop
if (( expr[0] == :expr ) || (expr[0] == :integer ))
while true do
if @debug
puts( "Debug: collapsing #{expr.inspect} on #{@stack.inspect}" )
end
if ( top[0] == pen )
push expr
break;
elsif ( top[0] == :start )
push expr
break;
elsif ( top[0] == :binop )
op = pop
left = pop
expr = [:expr, op, left, expr]
elsif ( top[0] == :unop )
op = pop
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 [pen]
when /[0-9]/
t = top
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( lus )
when "*"
operator( :mult )
when "-"
operator( :minus )
when "/"
operator( :divide )
when ")"
collapse_top
expr = pop
open = pop
if open[0] != pen
throw "Syntax error : #{open.inspect}, #{expr.inspect}, #{@stack.inspect}"
end
push expr
when "("
push [pen]
@state = :start
else
push "ERROR"
end
end
end

=begin
This is the main interface to the whole thing: it parses an
expression and can evaluate it in different ways
=end
class ParseTree
def initialize( source, debug = false )
@debug = debug
if source.kind_of?( String )
parse( source )
else
@tree = source.to_a
end
end

def to_a
@tree
end

def [](x)
@tree[x]
end

def parse( input )
session = Parser.new( @debug )
@tree = session.parse( input )
end

Operator_s = { lus => "+", :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 "(" +
subtreeleft).prettify +
Operator_s[@tree[1][1]] +
subtreeright).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="", prob=1.0 )
@roll = roll
@path = path
@p = prob
end
def binop(other)
if ( other.kind_of?( Numeric ) )
other = Roll_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, ath,
end

def roll_one( sides )
if sides.kind_of?(Numeric) ; sides = Roll_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 = Roll_stat.make( numdice )
sides = Roll_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 = true )
subtreeleft).evaluate do |l|
subtreeright).evaluate do |r|
if force_same_type
if r.kind_of?( Roll_stat ) and ! l.kind_of?( Roll_stat )
l = Roll_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 >= 1 )
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 = Freq_dist.new
sides.prob.each do |pr|
result = result.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 = Freq_dist.new
numdice.prob.each do |pr|
rolls = pr.value
if rolls < 0
throw "Negative number of dice #{rolls}"
end
score = Freq_dist.new.integer(0)
pr.value.times do
score = score + ( roll_one( sides ) { |x| x } )
end
result = result.merge( score.scale_prob( pr.p ) )
end
yield result
end
end

def eval_binop( force_same_type = true )
subtreeleft).evaluate do |l|
subtreeright).evaluate do |r|
if force_same_type
if r.kind_of?( Freq_dist ) and ! l.kind_of?( Freq_dist )
l = Freq_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 = ParseTree.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 = ParseTree.new(ARGV[1])
puts "Distribution:\n#{d.evaluate_dist.to_s}\n\n"
when "-cheat"
d = ParseTree.new(ARGV[1])
target = ARGV[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 = ParseTree.new(ARGV[0])
(ARGV[1] || 1).to_i.times { print "#{d.evaluate_random} " }
puts ""
end

 

[Gustav Munkby]

--------------040504030406060009030100
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit


this is my first ruby quiz, and here comes my solution.

as a couple of other solutions, it uses ruby to do the dirty work, and
implements the diceroll as a method on integer.

!g

--------------040504030406060009030100
Content-Type: text/plain;
name="q61-roll.rb"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
filename="q61-roll.rb"

#!/usr/bin/env ruby
#
# Ruby Quiz #61, Dice Roller
# http://www.rubyquiz.com/quiz61.html
#
# You should write a program that takes two arguments:
# * a dice expression
# * the number of times to roll it (default = 1)
#
# A dice expression looks somthing like this, plus
# a couple of rules which defines precedence and
# whatnot.
#
# <expr> := <expr> + <expr>
# | <expr> - <expr>
# | <expr> * <expr>
# | <expr> / <expr>
# | [<expr>] d <expr>
# | ( <expr> )
# | integer
#
# I solved this by delegating the task to Ruby. Since
# Ruby has built-in support for all these operations
# except the "d"-operation, that was the only thing
# which needed implementation.
#
# The quest for something with similar precedance which
# would work with minimal modification to the input
# yielded the following solution which replaces the
# "d"-operation with a method call on the integer object.
#
# Then all that has to be taken care of is to add
# paranthesis to the rhs, if neccessary, and to add a
# dot (.) in front of the d:s.
#
# If we would just do this, and then eval, the user
# could spawn much more complicated behaviour than what
# was intended, so therefore validation of the input
# string is added to ensure that the program works
# according to the specification
#

class Integer
# The dice-roll operation, Roll a dice of the specified
# size, as many times as this number represents
def dice(size)
self + (1..self).inject(0) do |sum, i|
sum + rand(size)
end
end
end

class Dice
Expression = /[1-9]\d*(?:[+-\/*d][1-9]\d*)*/

def initialize(str)
str = str.gsub(/(^|[\(+-\/*])d/, '\11d') # Implicit 1 before d
raise Exception.new("Illegal pattern") unless valid?(str.dup)
str.gsub!(/d(\d+)/, 'd(\1)') # Paranthesis if we must
str.gsub!(/d/, '.dice') # Method call requires .
instance_eval "def roll; #{str}; end"
end

private
# Validation method, this will destroy the input string
def valid?(str)
nil while str.gsub!(/\(#{Expression}\)/,'1') unless str=~/\)\(/
str =~ /^#{Expression}$/
end
end

d = Dice.new(ARGV[0])
(ARGV[1] || 1).to_i.times { print "#{d.roll} " }
puts

--------------040504030406060009030100--

 

[Gregory Seidman]

]
} here is the Ruby:
}
} #!/usr/bin/env ruby
} #
} # roll.rb
} #
}
} # fix up Fixnum to override ** with our desired d behavior
} class Fixnum
} def ** (sides)
} # validation
} if sides<1
} raise "Invalid sides value: '#{sides}', must be a positive Integer"
} end
} if self<1
} raise "Invalid number of rolls: '#{self}', must be a postitive Integer"
} end
} # roll the dice
} (0..self).to_a.inject{|x,y| x + rand(sides)}+self

I think I may be misunderstanding something here. You use 0..self, when I
would think it would have to be either 0...self or 1..self to get the right
number of rolls. Am I off? In my solution I used 1..self in much the same
way.

} end
} end
[...]

--Greg

 

[Paul Novak]

No, the mis-understanding is all mine. You are right, otherwise it
will include an extra roll. It should be:
(1..self).to_a.inject(0){|x,y| x + rand(sides)}+self

Further proof of the value of good unit tests. (Since (1..1).to_a
returns a single-member array, you need to provide inject with an
initial value to make it work.)

Regards,

Paul.

 

[Jacob Fugal]

No wonder I don't play D&D. I don't think I am smart enough.

Heh, I wouldn't say that. But I will admit that most of my attraction
to the game is the mental challenge of managing (and taking advantage
of) the complex rule system. Call me munchkin. Shrug.

What does 0 -> 10 mean. Does it mean a dice can have the
values 0,1,2,3...10?

No, that was a typo on my part. Should have been 0 -> 9 (e.g. rand(10)).

If so, why is a 0 never possible?

Zero is possible, but is interpreted as a 10. So the effective range
is 1 -> 19 (rand(10) + 1). In this respect, the outcome of a d10
follows the same rules of the outcome from a d6, d8 or d20 (rand(N) +
1). The presentation on the dice is the only difference. As noted by
Austin, this is primarily due to space limitations, but also for
convenience when using two d10 to simulate a d100.

Jacob Fugal

 

[Jacob Fugal]

Actually, when rolled together, both dice are zero-based. The
double-nought is the only special combination of 00 -> 100. When
rolled singly, a d10 has 0 -> 10. Rolling a 0 is never possible.

What does 0 -> 10 mean. Does it mean a dice can have the
values 0,1,2,3...10?

No, that was a typo on my part. Should have been 0 -> 9 (e.g. rand(10)).

Ok, I must fix this previous apology to Jim Freeze. 0 -> 10 was *not*
a typo. He just misinterpreted my notation. And seeing as I followed
his misinterpretation before second glance, it's perfectly justified.
In the paragraph above the -> represented "is interpreted as". So when
rolling two ten sided dice for a d100, double-nought ('00') is
interpreted as 100. When rolling a single d10, 0 is interpreted as 10.

Jacob Fugal

 

[Jacob Fugal]

Notation: [x,y] is any distribution with minimum x and maximum y. I then
get:

(5d5-4)d(16/d4)+3 =3D (adb =3D [a,a*b], so 5d5 =3D [5,25])

([5,25]-4)d(16/d4)+3 =3D ([x,y] - c =3D [x-c,y-c])

([1,21])d(16/d4)+3 =3D (adb =3D [a,a*b], so d4 =3D 1d4 =3D [1,4])

([1,21])d(16/[1,4])+3 =3D (c/[x,y] =3D [c/y,c/x] if x and y > 0)

([1,21])d([4,16])+3 =3D ([a,b]d[c,d] =3D [a*c,b*d] if a,b,c, and d >= 0)

[4,336]+3 =3D ([x,y] + c =3D [x+c,y+c])

[7,339]

As pointed out by others, the result should actually by [4,339]. The
error above is in the second to last step. [a,b]d[c,d] !=3D [a*c,b*d],
it should be [a,b]d[c,d] =3D [a,b*d]. The minimum effective value on a
die roll is always one, regardless of the number of sides (ie. whether
using a c-sided die or d-sided die). The minimum number of rolls being
a, the minimum roll total would then be a*1 =3D a. So we have:

[1,21]d[4,16]+3 =3D
[1,21*16]+3 =3D
[1+3,336+3] =3D
[4,339]

Jacob Fugal