From: Gregory Seidman <gsslist+ruby@...>
Date: 2006-01-10T02:33:27+09:00
Subject: [QUIZ SOLUTION] Dice Roller (#61)

On Sat, Jan 07, 2006 at 04:00:52AM +0900, Gregory Seidman wrote:
} On Sat, Jan 07, 2006 at 03:56:47AM +0900, Ruby Quiz wrote:
} [...]
} } [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.]
} 
} I would appreciate the full BNF, please.

Okay, so I said I wanted the full BNF, and I thought it would be useful if
I could find a convenient Ruby lex/yacc. Well, I couldn't. I now have two
solutions, both using my own parsing. Both use eval. One adds a method to
Fixnum to let eval do even more work. The more complicated version with
syntax trees, which came first, took roughly two hours to work out. The
second, simpler version with the Fixnum method took about 20 minutes to
build from the first version. Note that I maintained left associativity
with the d operator in both methods without having the 3dddd6 problem
Matthew Moss mentioned.

test61.rb runs the code on commandline arguments
61.rb is the complicated syntax tree version
61alt.rb is the simpler Fixnum method version

##### test61.rb ################################################################

#require '61'
require '61alt'

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

##### 61.rb ####################################################################

module DiceRoller

  class ArithOperator
    def initialize(left, op, right)
      @left = left
      @op = op
      @right = right
    end

    def to_i
      return (eval "#{@left.to_i}#{@op}#{@right.to_i}")
    end
  end

  class DieOperator
    #op is a dummy
    def initialize(left, op, right)
      @left = left
      @right = right
    end

    def to_i
      count = @left.to_i 
      fail "Die count must be nonnegative: '#{count}'" if count < 0
      die = @right.to_i
      fail "Die size must be positive: '#{die}'" if die < 1
      return (1..count).inject(0) { |sum, waste| sum + (rand(die)+1) }
    end
  end

  OpClass = { '+' => ArithOperator,
              '-' => ArithOperator,
              '*' => ArithOperator,
              '/' => ArithOperator,
              'd' => DieOperator }

  def lex(str)
    tokens = str.scan(/(00)|([-*\/()+d%0])|([1-9][0-9]*)|(.+)/)
    tokens.each_index { |i|
      tokens[i] = tokens[i].compact[0]
      if not /^(00)|([-*\/()+d%0])|([1-9][0-9]*)$/ =~ tokens[i]
        if /^\s+$/ =~ tokens[i]
          tokens[i] = nil
        else
          fail "Found garbage in expression: '#{tokens[i]}'"
        end
      end
    }
    return tokens.compact
  end

  def validate_and_cook(tokens)
    oper = /[-*\/+d]/
    num = /(\d+)|%/
    last_was_op = true
    paren_depth = 0
    prev = ''
    working = []
    tokens.each_index { |i|
      tok = tokens[i]
      if num =~ tok
        fail 'A number cannot follow an expression!' if not last_was_op
        fail 'Found spurious zero or number starting with zero!' if tok == '0'
        if ( tok == '00' || tok == '%' )
          fail 'Can only use % or 00 after d!' if prev != 'd'
          tokens[i] = 100
          working << 100
        else
          working << tok.to_i
        end
        last_was_op = false
      elsif oper =~ tok
        if last_was_op
          #handle case of dX meaning 1dX
          if tok == 'd'
            fail 'A d cannot follow a d!' if prev == RollMethod
            working << 1
          else
            fail 'An operator cannot follow a operator!'
          end
        end
        working << tok
        last_was_op = true
      elsif tok == "("
        fail 'An expression cannot follow an expression!' if not last_was_op
        paren_depth += 1
        working << :p_open
      elsif tok == ")"
        fail 'Incomplete expression at close paren!' if last_was_op
        fail 'Too many close parens!' if paren_depth < 1
        paren_depth -= 1
        last_was_op = false
        working << :p_close
      else #what did I miss?
        fail "What kind of token is this? '#{tok}'"
      end
      prev = tok
    }
    fail 'Missing close parens!' if paren_depth != 0
    return working
  end

  def parse_parens(tokens)
    working = []
    i = 0
    while i < tokens.length
      if tokens[i] == :p_open
        i += 1
        paren_depth = 0
        paren_tokens = []
        while (tokens[i] != :p_close) || (paren_depth > 0)
          if tokens[i] == :p_open
            paren_depth += 1
          elsif tokens[i] == :p_close
            paren_depth -= 1
          end
          paren_tokens << tokens[i]
          i += 1
        end
        working << parse(paren_tokens)
      else
        working << tokens[i]
      end
      i += 1
    end
    return working
  end

  def parse_ops(tokens, regex)
    fail "Something broke: len = #{tokens.length}" if tokens.length < 3 ||  (tokens.length % 2) == 0
    i = 1
    working = [ tokens[0] ]
    while i < tokens.length
      if regex =~ tokens[i].to_s
        op = OpClass[tokens[i]]
        lindex = working.length-1
        working[lindex] = op.new(working[lindex], tokens[i], tokens[i+1])
      else
        working << tokens[i]
        working << tokens[i+1]
      end
      i += 2
    end
    return working
  end

  #scan for parens, then d, then */, then +-
  def parse(tokens)
    working = parse_parens(tokens)
    fail "Something broke: len = #{working.length}" if (working.length % 2) == 0
    working = parse_ops(working, /^d$/) if working.length > 1
    fail "Something broke: len = #{working.length}" if (working.length % 2) == 0
    working = parse_ops(working, /^[*\/]$/) if working.length > 1
    fail "Something broke: len = #{working.length}" if (working.length % 2) == 0
    working = parse_ops(working, /^[+-]$/) if working.length > 1
    fail "Something broke: len = #{working.length}" if working.length != 1
    return working[0]
  end

  def parse_dice(str)
    tokens = lex(str)
    return parse(validate_and_cook(tokens))
  end

end

class Dice

  def initialize(expression)
    @expression = parse_dice(expression)
  end

  def roll
    return @expression.to_i
  end

  private

  include DiceRoller

end

##### 61alt.rb #################################################################

module DiceRoller

  RollMethod = '.roll'

  def lex(str)
    tokens = str.scan(/(00)|([-*\/()+d%0])|([1-9][0-9]*)|(.+)/)
    tokens.each_index { |i|
      tokens[i] = tokens[i].compact[0]
      if not /^(00)|([-*\/()+d%0])|([1-9][0-9]*)$/ =~ tokens[i]
        if /^\s+$/ =~ tokens[i]
          tokens[i] = nil
        else
          fail "Found garbage in expression: '#{tokens[i]}'"
        end
      end
    }
    return tokens.compact
  end

  def validate_and_cook(tokens)
    oper = /[-*\/+d]/
    num = /(\d+)|%/
    last_was_op = true
    paren_depth = 0
    prev = ''
    working = []
    tokens.each_index { |i|
      tok = tokens[i]
      if num =~ tok
        fail 'A number cannot follow an expression!' if not last_was_op
        fail 'Found spurious zero or number starting with zero!' if tok == '0'
        if ( tok == '00' || tok == '%' )
          fail 'Can only use % or 00 after d!' if prev != RollMethod
          tokens[i] = 100
          tok = 100
        else
          tok = tok.to_i
        end
        if prev == RollMethod
          working << "(#{tok})"
        else
          working << tok
        end
        last_was_op = false
      elsif oper =~ tok
        tok = RollMethod if tok == 'd'
        if last_was_op
          #handle case of dX meaning 1dX
          if tok == RollMethod
            fail 'A d cannot follow a d!' if prev == RollMethod
            working << 1
          else
            fail 'An operator cannot follow a operator!'
          end
        end
        working << tok
        last_was_op = true
      elsif tok == "("
        fail 'An expression cannot follow an expression!' if not last_was_op
        paren_depth += 1
        working << tok
      elsif tok == ")"
        fail 'Incomplete expression at close paren!' if last_was_op
        fail 'Too many close parens!' if paren_depth < 1
        paren_depth -= 1
        last_was_op = false
        working << tok
      else #what did I miss?
        fail "What kind of token is this? '#{tok}'"
      end
      prev = tok
    }
    fail 'Missing close parens!' if paren_depth != 0
    return working
  end

  def parse_dice(str)
    tokens = lex(str)
    return validate_and_cook(tokens).to_s
  end

end

class Fixnum
  def roll(die)
    fail "Die count must be nonnegative: '#{self}'" if self < 0
    fail "Die size must be positive: '#{die}'" if die < 1
    return (1..self).inject(0) { |sum, waste| sum + (rand(die)+1) }
  end
end

class Dice

  def initialize(expression)
    @expression = parse_dice(expression)
  end

  def roll
    return (eval @expression)
  end

  private

  include DiceRoller

end