From: Matthew Moss <matthew.moss.coder@...>
Date: 2006-01-12T16:04:58+09:00
Subject: [QUIZ.SUMMARY] Dice Roller (#61)

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

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 qui=
z
#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 poin=
t
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 tha=
t
(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, sinc=
e
aside from the 'd' operator, the expression were valid Ruby already.  Let's
take a look at Christian Neukirchen's solution:

    class Integer
      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:

    def initialize(dice)
       @src =3D dice.gsub(/d(%|00)(\D|$)/, 'd100\2').
                   gsub(/d(\d+)/, 'd(\1)').
                   gsub(/(\d+|\))d/, '\1.d').
                   gsub(/\d+/) { $&.gsub(/^0+/, '') }

       @dice =3D 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 express 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 tha=
n
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 gsu=
b
calls actually substituted the results during parsing.  And Stefan Walk win=
s
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 that 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 sho=
w
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 follo=
w
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 Christe=
r
Nilsson also have recursive descent parsers that can not only roll dice, bu=
t
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 hi=
s
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:

    parser =3D RDParser.new do
      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 solutio=
n
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:

    def to_rpn(infix)
       stack, rpn, last =3D [], [], 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 =3D~ /\d+|\)|%/
             stack << token
           when '('
             stack << token
           when ')'
             while (op =3D stack.pop) && (op !=3D '(')
               rpn << op
             end
         end
         last =3D token
       end
       while op =3D stack.pop
         rpn << op
       end
       rpn
    end

I love to see code that I can understand immediately, and also recognize ho=
w
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:

    def roll
       stack =3D []
       @expr.each do |token|
         case token
           when /\d+/
             stack << token.to_i
           when /[-+*\/d]/
             b =3D stack.pop
             a =3D 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 character=
s
stats of 18.

------=_Part_29937_1546487.1137049482283--