[QUIZ.SUMMARY] Dice Roller (#61)

[Matthew Moss]

------=_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=

 

[James Edward Gray II]

Thanks to everyone for the great submissions and lively discussion
on the
mailing list (and the correction to the quiz that I missed!).

I want to thank Matthew Moss for a wonderful problem and a
sensational summary! I also happen to know that Matthew already has
another quiz in the queue for a week from tomorrow. How cool is that?

Matthew, you rock.

James Edward Gray II

 

[Gregory Seidman]

]
} 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.
[...]
} The second class of solutions involved using a parsing library or parser
} generator tool.
[...]
} 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.
[...]

I want to go through my handcrafted parser solution, which may have gotten
missed in the shuffle. This is especially likely since I also submitted one
using the eval method. In fact, my handcrafted parser used eval, but only
for the +, -, /, and * operators.

The important bit is that all of the nodes in my syntax tree respond to
to_i with the computed result of its subexpression. This was largely to
make numbers behave the same way that my syntactic elements did, and vice
versa. My parsing method looks like this (with a fail check to make sure
nothing went wrong after each line, mainly for debugging purposes) to
create the syntax tree:

1) token_array = tokenize(expression)
uses String#scan and checks for garbage
2) token_array = validate_and_cook(token_array)
replaces some tokens with symbols, deals with dX => 1dX, d00 =>
d100, d% => d100, makes sure open parens have close parens and
the operators and operands are in grammatically appropriate places
3) parse_tokens(token_array)
a) token_array = parse_parens(token_array)
finds parenthesized expressions and runs the subarray through
parse_tokens; nested parens are handled recursively. Note that
there is no need for error checking, since the expression has
already been validated.
b) token_array = parse_ops(token_array, /^d$/) if token_array.length > 1
finds all d operators and creates a DieOperator object with its
left and right operands. Since all the operators in this grammar
are left-associative, parse_ops is left-associative. The regex is
used to determine if the token is the operator(s) being handled.
c) token_array = parse_ops(token_array, /^[*\/]$/) if token_array.length > 1
same as b, but for * and / operators. In this case, ArithOperator
objects are created. The parse_ops method uses an OpsClass hash
that matches the operator (d, *, /, +, or -) to the appropriate
class to call new on.
d) token_array = parse_ops(token_array, /^[-+]$/) if token_array.length > 1
same as c, but for + and - operators. Still using ArithOperator
objects.

The ArithOperator class is what uses eval. It is given the operator as a
string, and its to_i method calls eval "#{@left.to_i}#{@op}#{@right.to_i}"
to produce its value.

The points I'm trying to make are:

1) the grammar was so simple that there was no need for a proper
recursive-descent parser
2) duck typing is way cool and let me treat numbers, DieOperators, and
ArithOperators identically
3) a little eval let me use one class instead of four for ArithOperator
4) doing all that validation ahead of time let me replace my syntax tree
with using eval for the whole expression without giving up my nice,
clear failure messages

} 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.

This one was loads of fun, if not as challenging as the Numeric Maze (which
was my first). It's a pity I'll be out of town this weekend and won't be
able to do the next one.

--Greg

 

[Matthew Moss]

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

And I can see I already that I need to read my regexps a little more
carefully. The third regexp in Christian Neukirchen's solution doesn't
provide the default 1 to the 'd' operator; it actually turns the 'd'
operator into a method call on Integer. And the second regexp sets up
parenthesis around the number following the 'd' as arguments for that call.
Silly me....

I want to thank Matthew Moss for a wonderful problem and a
sensational summary! I also happen to know that Matthew already has
another quiz in the queue for a week from tomorrow. How cool is that?

Matthew, you rock.

James Edward Gray II

------=_Part_629_19452453.1137079439127--

 

[Bill Kelly]

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.

Yes I could probably dominate the "cheesiest approach" category.
I did extend a class in my "solution"... String#die_to_meth


Thanks for a fun quiz and an excellent summary.


Regards,

Bill

 

[Matthew Moss]

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

Ya, you did extend a class.

Man, I must really be tired. Or forgot how to read. Or had a few brain cell=
s
short out. Or something. Or be really tired.

fun.

Yes I could probably dominate the "cheesiest approach" category.
I did extend a class in my "solution"... String#die_to_meth


Thanks for a fun quiz and an excellent summary.


Regards,

Bill

------=_Part_5164_8688387.1137104410608--

 

[J. Ryan Sobol]

I could have evaluated @src each time without substituting anew, but a
lambda only makes it need to *parse* once.

Hey Christian,

I didn't have time to write my own solution to quiz #61, so I'm going
over yours, which is similar to what I was kicking around in my
head. Unfortunately, I confused by your eval statement, which is
wrapped over a new Proc object. Instead, why not wrap the lambda
around the eval like so?

@dice = lambda { eval @src }

The both _seem_ to produce the same output, yet conceptually, my
approach makes more sense to me. Perhaps I'm missing something
crucial in my statement like...

Does eval parse @src for each call() message? Or does the parsing
happen on initialization of the Proc (like I would expect)? I
suppose I could trace the execution using the debugger, but I'm
unaware how to step inside a Kernel method like eval or lambda with it.

~ ryan ~

 

[James Edward Gray II]

Hey Christian,

I didn't have time to write my own solution to quiz #61, so I'm
going over yours, which is similar to what I was kicking around in
my head. Unfortunately, I confused by your eval statement, which
is wrapped over a new Proc object. Instead, why not wrap the
lambda around the eval like so?

@dice = lambda { eval @src }

The both _seem_ to produce the same output, yet conceptually, my
approach makes more sense to me. Perhaps I'm missing something
crucial in my statement like...

Does eval parse @src for each call() message?

Yes. You pass lambda() a block of code that is executed each time
the code it called.

James Edward Gray II

 

[Logan Capaldo]

Hey Christian,

I didn't have time to write my own solution to quiz #61, so I'm
going over yours, which is similar to what I was kicking around in
my head. Unfortunately, I confused by your eval statement, which
is wrapped over a new Proc object. Instead, why not wrap the
lambda around the eval like so?

@dice = lambda { eval @src }

The both _seem_ to produce the same output, yet conceptually, my
approach makes more sense to me. Perhaps I'm missing something
crucial in my statement like...

Does eval parse @src for each call() message? Or does the parsing
happen on initialization of the Proc (like I would expect)? I
suppose I could trace the execution using the debugger, but I'm
unaware how to step inside a Kernel method like eval or lambda with
it.

~ ryan ~

@dice.call has eval parse @src everytime (@src may have changed). By
doing something like eval "lambda { #{@src} }" you parse @src once
and get back a lambda.

 

[J. Ryan Sobol]

Yes. You pass lambda() a block of code that is executed each time
the code it called.

Executed yes. But when is it parsed / checked for valid grammar,
syntax, etc.? Did you mean to say that the block of code is parsed
AND executed for each call() it receives?

~ ryan ~

 

[James Edward Gray II]

Executed yes. But when is it parsed / checked for valid grammar,
syntax, etc.? Did you mean to say that the block of code is parsed
AND executed for each call() it receives?

lambda() doesn't imply that, but eval() does. It must be reparsed
with each call.

James Edward Gray II

 

[J. Ryan Sobol]

Executed yes. But when is it parsed / checked for valid grammar,
syntax, etc.? Did you mean to say that the block of code is parsed
AND executed for each call() it receives?

~ ryan ~

obj = lambda { eval "#{2**10}" }

(1..1_000_000).each do
obj.call
end

$ time ruby test.rb

real 0m26.046s
user 0m24.377s
sys 0m0.358s

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

obj = eval "lambda { #{2**10} }"

(1..1_000_000).each do
obj.call
end

$ time ruby test.rb

real 0m3.132s
user 0m2.895s
sys 0m0.047s

What a difference! I'll agree that parsing of eval's string happens
on every call() message in the first example.

~ ryan ~