by Matthew D Moss
Time to release your inner nerd.
The task for this Ruby Quiz is to write a dice roller. You should write a program that takes two arguments: a dice expression followed by the number of times to roll it (being optional, with a default of 1). So to calculate those stats for your AD&D character, you would do this:
> roll.rb "3d6" 6
6 6 9 11 9 13
Or, for something more complicated:
> roll.rb "(5d5-4)d(16/d4)+3"
31
[NOTE: You'll usually want quotes around the dice expression to hide parenthesis from the shell, but the quotes are not part of the expression.]
The main code of roll.rb should look something like this:
(ARGV[1] || 1).to_i.times { print "#{d.roll} " }
The meat of this quiz is going to be parsing the dice expression (i.e., implementing Dice.new). Let's first go over the grammar, which I present in a simplified BNF notation with some notes:
<expr> := <expr> + <expr>
| <expr> - <expr>
| <expr> * <expr>
| <expr> / <expr>
| ( <expr> )
| [<expr>] d <expr>
| integer
* Integers are positive; never zero, never negative.
* 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
[NOTE: The BNF above is simplified here for clarity and space. If requested, I will make available the full BNF description I've used in my own solution, which incorporates the association and precedence rules.]
A few more things... Feel free to either craft this by hand or an available lexing/parsing library. Handling whitespace between integers and operators is nice. Some game systems use d100 quite often, and may abbreviate it as "d%" (but note that '%' is only allowed immediately after a 'd').
Quiz Summary
by Matthew Moss
My reason for choosing a dice roller is somewhat selfish: I was interested to see how people would solve a problem that required parsing a mini-language. I've written lexers and parsers before, years ago, but I wanted to see what methods the Ruby gurus would employ.
I was not unsurprised. While there were some "traditional" solutions, there were also a few that made me remember something I realized in past Ruby Quizzes: it's all about pattern matching. One of the solutions to past quiz #24 (Texas Hold'Em) showed how much power can be gained by a careful examination of the patterns in the problem; with a few carefully built regular expressions, some gsub calls and a bit of magic, you can turn what looks like a complex problem into something much similar. I should have remembered that (or, at the least, realized that someone else would).
Discussion on the list about the quiz was rather active, most of the time getting into the nitty-gritty details of what d10 and 5d6d7 meant, and occassionally joking about munchkins and their stats of all 18 (with a strength of 18/00, of course). As solutions came in, it was nice to see about four or five people making their first attempt. With them, this quiz gets the bronze medal for submission count, behind the LCD Numbers quiz (#14) and the Numeric Maze quiz (#60).
I found unique bits in most every solution; even those that took almost identical approaches would often, at the least, have different regular expressions. If you are afraid of the mighty regexp, now would be a good time to study some samples, since the syntax for the dice expressions is reasonably simple, and many people documented their regular expressions.
Most solutions fell into one of a few types. I'll cover each a bit and point out anything in particular that attracted my attention.
The first class of solutions massaged the input expression a bit, then used Ruby's eval method to do the work. This simple solution eluded me, since I was so fixed on seeing parsing code. Apparently a bunch of you realized that (as Paul Novak so nicely put) "we don't need no steenking parsers." A few substitutions and a helper function or two was enough to do the trick, since aside from the 'd' operator, the expression were valid Ruby already. Let's take a look at Christian Neukirchen's solution:
def d(n)
(1..self).inject(0) { |a, e| a + rand(n) + 1 }
end
end
First off we have the random number generation; most solutions had this or a very similar variant. So the call 3.d(6) will roll and accumulate three six-sided dice, and the expression 3.d(6) is almost a valid dice expression. It is in Christian's initialization method that dice expressions are turned into Ruby expressions:
@src = dice.gsub(/d(%|00)(\D|$)/, 'd100\2').
gsub(/d(\d+)/, 'd(\1)').
gsub(/(\d+|\))d/, '\1.d').
gsub(/\d+/) { $&.gsub(/^0+/, '') }
@dice = eval "lambda { #@src }"
end
(I've left out a bit of error checking; see the full solution to see everything.) The first substitution fixes up percentage and double-zero values as 100. The second turns 'd' as a binary operator into 'd' as a method call. The third substitution provides the default dice count of 1 if it wasn't specified. And the last substitution removes leading zeroes of integers; this last substitution prevents the Ruby from interpreting values as octal.
The morphed expression is saved away in a lambda, which allows Christian to reevaluate the expression repeatedly without performing those substitutions every time roll is called.
There were several variations of the eval method solution, mostly in the regular expression substitutions. A couple variations rewrote existing operators (rather than adding new methods to Integer or Fixnum). Rather than change the 'd' operator into a method call, he made a slightly different twist and rolled the dice in method_missing. Perhaps Bill didn't know that classes could be extended, or maybe he was hacking around for fun. Dennis Ranke had a eval-looking solution with no eval to be found, because the gsub calls actually substituted the results during parsing. And Stefan Walk wins for the shortest solution: three lines of hard to read Ruby code.
The second class of solutions involved using a parsing library or parser generator tool. Three of these showed up: Pierre Barbier de Reuille used racc, Austin Ziegler used syntax.rb, and David Tran pulled out ANTLR to generate his parser. Each of these will let you describe your language in BNF format, or something quite similar to it, and it will generate a Ruby language parser for you. These can be quite powerful solutions, although readability of the language specification and the support code varies widely. But I do recommend looking into these tools if you have need to do something more powerful than dice expressions; generating a complex parser with one of these would save much time and effort over a handcoded solution.
And now we're at the third class of solutions: the handcrafted parsers. About nine people handcrafted parsers, mostly recursive descent which is rather easy to code. Because these generally involve more code, I won't show much, but I suggest taking a look at some of them.
Dominik Bathon's solution, while it prefers to use the eval method as it goes along rather than build a parse tree, is a easy to read solution and makes good use of StringScanner. Morus Walter's solution is decent to follow and understand and builds up an expression tree with his Expr class, which gets evaluated at the end with a single call to roll. My own solution is similar, but creates a tree of proc objects. Andrew McGuinness and Christer Nilsson also have recursive descent parsers that can not only roll dice, but calculation frequency distributions and histograms, and cheat.
I want to look now at a couple of standouts. First, let's look at Dennis Ranke's second submission. It's a recursive descent parser, contained in his class RDParser which is included with the submission but a little too long to summarize here. However, what RDParser has done is allow Dennis to write this solution:
token(/\s+/)
token(/\d+/) {|m| m.to_i }
token(/./) {|m| m }
start :expr do
match(:expr, '+', :term) {|a, _, b| a + b }
match(:expr, '-', :term) {|a, _, b| a - b }
match(:term)
end
rule :term do
match(:term, '*', :dice) {|a, _, b| a * b }
match(:term, '/', :dice) {|a, _, b| a / b }
match(:dice)
end
def roll(times, sides)
(1..times).inject(0) {|a, b| a + rand(sides) + 1 }
end
rule :dice do
match(:atom, 'd', :sides) {|a, _, b| roll(a, b) }
match('d', :sides) {|_, b| roll(1, b) }
match(:atom)
end
rule :sides do
match('%') { 100 }
match(:atom)
end
rule :atom do
match(Integer)
match('(', :expr, ')') {|_, a, _| a }
end
end
Do I need to say how beautiful that is? It's short, clean, easy to read and understand... and all Ruby. Package that RDParser into a module and ship it! I think I've found my next parsing tool...
Let's look at the guts of one more solution, by Pablo Hoch. Pablo's solution didn't exactly fit into the other classes of solution: it's somewhere between a parser and an eval-uator. He decided to take the infix dice expression and turn it into a RPN (Reverse Polish Notation, that is, postfix) expression:
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
I love to see code that I can understand immediately, and also recognize how it could be useful for other applications. This is definitely one of those because postfix expressions (or prefix, to be complete) are a breeze for a computer to evaluate:
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
Thanks to everyone for the great submissions and lively discussion on the mailing list (and the correction to the quiz that I missed!). I just hope when we all sit down to play that I don't see any of you with all characters stats of 18.
