ochaochaocha3/00_README.md

## 00_README.md

      
    Raw
  

              00_README.md
            
          
    Joel S. Cohen: "Computer Algebra and Symbolic Computation: Mathematical Methods",  A K Peters (2003)を参考にして、抽象構文木の変形による数式の代数的簡約化（algebraic simplification）を実装した。現在は、加算、減算、乗算、および符号反転（単項マイナス）のみに対応している。また、BCDiceでの需要に合わせて、加算部分は間の項をまたいで簡約化されないように文献からアルゴリズムを変えている。
実行にはparslet gemが必要。
実行例

require_relative 'parser'
require_relative 'simplification'

r1 = DiceParser.new.parse('1+4+2*3+2*2D6*3+1+2+3+2*4+3D6+5+7')
ast = DiceASTGenerator.new.apply(r1)
ast.s_exp
#=> "(+ (+ (+ (+ (+ (+ (+ (+ (+ (+ 1 4) (* 2 3)) (* (* 2 (DiceRoll 2 6)) 3)) 1) 2) 3) (* 2 4)) (DiceRoll 3 6)) 5) 7)"
Simplification.new(ast).run.s_exp
#=> "(+ 11 (* 6 (DiceRoll 2 6)) 14 (DiceRoll 3 6) 12)"

  
## 10_EXAMPLE.md

      
    Raw
  

              10_EXAMPLE.md
            
          
    1+2

(+ 1 2)

automatic_simplify: (+ (+ 1 2))
automatic_simplify: (+ 1 2)
automatic_simplify: 1
automatic_simplify: 2
simplify_addition_rec: operands = ["1", "2"]
  sum: 3

3

2D6

(DiceRoll 2 6)

automatic_simplify: (+ (DiceRoll 2 6))
automatic_simplify: (DiceRoll 2 6)

(DiceRoll 2 6)

2D6+1

(+ (DiceRoll 2 6) 1)

automatic_simplify: (+ (+ (DiceRoll 2 6) 1))
automatic_simplify: (+ (DiceRoll 2 6) 1)
automatic_simplify: (DiceRoll 2 6)
automatic_simplify: 1
simplify_addition_rec: operands = ["(DiceRoll 2 6)", "1"]

(+ (DiceRoll 2 6) 1)

1+2D6

(+ 1 (DiceRoll 2 6))

automatic_simplify: (+ (+ 1 (DiceRoll 2 6)))
automatic_simplify: (+ 1 (DiceRoll 2 6))
automatic_simplify: 1
automatic_simplify: (DiceRoll 2 6)
simplify_addition_rec: operands = ["1", "(DiceRoll 2 6)"]

(+ 1 (DiceRoll 2 6))

2D6+2*3+4

(+ (+ (DiceRoll 2 6) (* 2 3)) 4)

automatic_simplify: (+ (+ (+ (DiceRoll 2 6) (* 2 3)) 4))
automatic_simplify: (+ (+ (DiceRoll 2 6) (* 2 3)) 4)
automatic_simplify: (+ (DiceRoll 2 6) (* 2 3))
automatic_simplify: (DiceRoll 2 6)
automatic_simplify: (* 2 3)
automatic_simplify: 2
automatic_simplify: 3
simplify_multiplication_rec: operands = ["2", "3"]
  product: 6
simplify_addition_rec: operands = ["(DiceRoll 2 6)", "6"]
automatic_simplify: 4
simplify_addition_rec: operands = ["(+ (DiceRoll 2 6) 6)", "4"]
  merge_additions: ["(DiceRoll 2 6)", "6"], ["4"]
simplify_addition_rec: operands = ["6", "4"]
  sum: 10
  merge_additions: ["(DiceRoll 2 6)", "10"], []

(+ (DiceRoll 2 6) 10)

1+2*3+2D6+4+5*2

(+ (+ (+ (+ 1 (* 2 3)) (DiceRoll 2 6)) 4) (* 5 2))

automatic_simplify: (+ (+ (+ (+ (+ 1 (* 2 3)) (DiceRoll 2 6)) 4) (* 5 2)))
automatic_simplify: (+ (+ (+ (+ 1 (* 2 3)) (DiceRoll 2 6)) 4) (* 5 2))
automatic_simplify: (+ (+ (+ 1 (* 2 3)) (DiceRoll 2 6)) 4)
automatic_simplify: (+ (+ 1 (* 2 3)) (DiceRoll 2 6))
automatic_simplify: (+ 1 (* 2 3))
automatic_simplify: 1
automatic_simplify: (* 2 3)
automatic_simplify: 2
automatic_simplify: 3
simplify_multiplication_rec: operands = ["2", "3"]
  product: 6
simplify_addition_rec: operands = ["1", "6"]
  sum: 7
automatic_simplify: (DiceRoll 2 6)
simplify_addition_rec: operands = ["7", "(DiceRoll 2 6)"]
automatic_simplify: 4
simplify_addition_rec: operands = ["(+ 7 (DiceRoll 2 6))", "4"]
  merge_additions: ["7", "(DiceRoll 2 6)"], ["4"]
simplify_addition_rec: operands = ["(DiceRoll 2 6)", "4"]
  merge_additions: ["7", "(DiceRoll 2 6)", "4"], []
automatic_simplify: (* 5 2)
automatic_simplify: 5
automatic_simplify: 2
simplify_multiplication_rec: operands = ["5", "2"]
  product: 10
simplify_addition_rec: operands = ["(+ 7 (DiceRoll 2 6) 4)", "10"]
  merge_additions: ["7", "(DiceRoll 2 6)", "4"], ["10"]
simplify_addition_rec: operands = ["4", "10"]
  sum: 14
  merge_additions: ["7", "(DiceRoll 2 6)", "14"], []

(+ 7 (DiceRoll 2 6) 14)

1-2*3+2D6-4*5+6

(+ (- (+ (- 1 (* 2 3)) (DiceRoll 2 6)) (* 4 5)) 6)

automatic_simplify: (+ (+ (- (+ (- 1 (* 2 3)) (DiceRoll 2 6)) (* 4 5)) 6))
automatic_simplify: (+ (- (+ (- 1 (* 2 3)) (DiceRoll 2 6)) (* 4 5)) 6)
automatic_simplify: (- (+ (- 1 (* 2 3)) (DiceRoll 2 6)) (* 4 5))
automatic_simplify: (+ (- 1 (* 2 3)) (DiceRoll 2 6))
automatic_simplify: (- 1 (* 2 3))
automatic_simplify: 1
automatic_simplify: (* 2 3)
automatic_simplify: 2
automatic_simplify: 3
simplify_multiplication_rec: operands = ["2", "3"]
  product: 6
automatic_simplify: (* -1 6)
automatic_simplify: -1
automatic_simplify: 6
simplify_multiplication_rec: operands = ["-1", "6"]
  product: -6
simplify_addition_rec: operands = ["1", "-6"]
  sum: -5
automatic_simplify: (DiceRoll 2 6)
simplify_addition_rec: operands = ["-5", "(DiceRoll 2 6)"]
automatic_simplify: (* 4 5)
automatic_simplify: 4
automatic_simplify: 5
simplify_multiplication_rec: operands = ["4", "5"]
  product: 20
automatic_simplify: (* -1 20)
automatic_simplify: -1
automatic_simplify: 20
simplify_multiplication_rec: operands = ["-1", "20"]
  product: -20
simplify_addition_rec: operands = ["(+ -5 (DiceRoll 2 6))", "-20"]
  merge_additions: ["-5", "(DiceRoll 2 6)"], ["-20"]
simplify_addition_rec: operands = ["(DiceRoll 2 6)", "-20"]
  merge_additions: ["-5", "(DiceRoll 2 6)", "-20"], []
automatic_simplify: 6
simplify_addition_rec: operands = ["(+ -5 (DiceRoll 2 6) -20)", "6"]
  merge_additions: ["-5", "(DiceRoll 2 6)", "-20"], ["6"]
simplify_addition_rec: operands = ["-20", "6"]
  sum: -14
  merge_additions: ["-5", "(DiceRoll 2 6)", "-14"], []

(+ -5 (DiceRoll 2 6) -14)

1+2D6+3*4+1D6+5+6+7

(+ (+ (+ (+ (+ (+ 1 (DiceRoll 2 6)) (* 3 4)) (DiceRoll 1 6)) 5) 6) 7)

automatic_simplify: (+ (+ (+ (+ (+ (+ (+ 1 (DiceRoll 2 6)) (* 3 4)) (DiceRoll 1 6)) 5) 6) 7))
automatic_simplify: (+ (+ (+ (+ (+ (+ 1 (DiceRoll 2 6)) (* 3 4)) (DiceRoll 1 6)) 5) 6) 7)
automatic_simplify: (+ (+ (+ (+ (+ 1 (DiceRoll 2 6)) (* 3 4)) (DiceRoll 1 6)) 5) 6)
automatic_simplify: (+ (+ (+ (+ 1 (DiceRoll 2 6)) (* 3 4)) (DiceRoll 1 6)) 5)
automatic_simplify: (+ (+ (+ 1 (DiceRoll 2 6)) (* 3 4)) (DiceRoll 1 6))
automatic_simplify: (+ (+ 1 (DiceRoll 2 6)) (* 3 4))
automatic_simplify: (+ 1 (DiceRoll 2 6))
automatic_simplify: 1
automatic_simplify: (DiceRoll 2 6)
simplify_addition_rec: operands = ["1", "(DiceRoll 2 6)"]
automatic_simplify: (* 3 4)
automatic_simplify: 3
automatic_simplify: 4
simplify_multiplication_rec: operands = ["3", "4"]
  product: 12
simplify_addition_rec: operands = ["(+ 1 (DiceRoll 2 6))", "12"]
  merge_additions: ["1", "(DiceRoll 2 6)"], ["12"]
simplify_addition_rec: operands = ["(DiceRoll 2 6)", "12"]
  merge_additions: ["1", "(DiceRoll 2 6)", "12"], []
automatic_simplify: (DiceRoll 1 6)
simplify_addition_rec: operands = ["(+ 1 (DiceRoll 2 6) 12)", "(DiceRoll 1 6)"]
  merge_additions: ["1", "(DiceRoll 2 6)", "12"], ["(DiceRoll 1 6)"]
simplify_addition_rec: operands = ["12", "(DiceRoll 1 6)"]
  merge_additions: ["1", "(DiceRoll 2 6)", "12", "(DiceRoll 1 6)"], []
automatic_simplify: 5
simplify_addition_rec: operands = ["(+ 1 (DiceRoll 2 6) 12 (DiceRoll 1 6))", "5"]
  merge_additions: ["1", "(DiceRoll 2 6)", "12", "(DiceRoll 1 6)"], ["5"]
simplify_addition_rec: operands = ["(DiceRoll 1 6)", "5"]
  merge_additions: ["1", "(DiceRoll 2 6)", "12", "(DiceRoll 1 6)", "5"], []
automatic_simplify: 6
simplify_addition_rec: operands = ["(+ 1 (DiceRoll 2 6) 12 (DiceRoll 1 6) 5)", "6"]
  merge_additions: ["1", "(DiceRoll 2 6)", "12", "(DiceRoll 1 6)", "5"], ["6"]
simplify_addition_rec: operands = ["5", "6"]
  sum: 11
  merge_additions: ["1", "(DiceRoll 2 6)", "12", "(DiceRoll 1 6)", "11"], []
automatic_simplify: 7
simplify_addition_rec: operands = ["(+ 1 (DiceRoll 2 6) 12 (DiceRoll 1 6) 11)", "7"]
  merge_additions: ["1", "(DiceRoll 2 6)", "12", "(DiceRoll 1 6)", "11"], ["7"]
simplify_addition_rec: operands = ["11", "7"]
  sum: 18
  merge_additions: ["1", "(DiceRoll 2 6)", "12", "(DiceRoll 1 6)", "18"], []

(+ 1 (DiceRoll 2 6) 12 (DiceRoll 1 6) 18)

2D6-1D6*3

(- (DiceRoll 2 6) (* (DiceRoll 1 6) 3))

automatic_simplify: (+ (- (DiceRoll 2 6) (* (DiceRoll 1 6) 3)))
automatic_simplify: (- (DiceRoll 2 6) (* (DiceRoll 1 6) 3))
automatic_simplify: (DiceRoll 2 6)
automatic_simplify: (* (DiceRoll 1 6) 3)
automatic_simplify: (DiceRoll 1 6)
automatic_simplify: 3
simplify_multiplication_rec: operands = ["(DiceRoll 1 6)", "3"]
  flip: ["3", "(DiceRoll 1 6)"]
automatic_simplify: (* -1 (* 3 (DiceRoll 1 6)))
automatic_simplify: -1
automatic_simplify: (* 3 (DiceRoll 1 6))
automatic_simplify: 3
automatic_simplify: (DiceRoll 1 6)
simplify_multiplication_rec: operands = ["3", "(DiceRoll 1 6)"]
simplify_multiplication_rec: operands = ["-1", "(* 3 (DiceRoll 1 6))"]
  merge_multiplications: ["-1"], ["3", "(DiceRoll 1 6)"]
simplify_multiplication_rec: operands = ["-1", "3"]
  product: -3
  merge_multiplications: [], ["(DiceRoll 1 6)"]
simplify_addition_rec: operands = ["(DiceRoll 2 6)", "(* -3 (DiceRoll 1 6))"]

(+ (DiceRoll 2 6) (* -3 (DiceRoll 1 6)))


## example.rb
require 'optparse'
require_relative 'parser'
require_relative 'simplification'

opt = OptionParser.new
verbose = false
opt.on('-v', '--verbose', '冗長出力モード') do
  verbose = true
end

opt.parse!

testcases = [
  '1+2',
  '2D6',
  '2D6+1',
  '1+2D6',
  '2D6+2*3+4',
  '1+2*3+2D6+4+5*2',
  '1-2*3+2D6-4*5+6',
  '1+2D6+3*4+1D6+5+6+7',
  '2D6-1D6*3',
]

testcases.each_with_index do |c, i|
  puts if i > 0
  puts(c)

  tree =
    begin
      DiceParser.new.parse(c)
    rescue => e
      puts("Parse error: #{e}")
      next
    end

  ast =
    begin
      DiceASTGenerator.new.apply(tree)
    rescue => e
      puts("AST generating error: #{e}")
      next
    end

  puts("  #{ast.s_exp}")

  simplified_ast = Simplification.new(ast, verbose).run
  puts("  #{simplified_ast.s_exp}")
end

## node.rb
# frozen_string_literal: true

Number = Struct.new(:value) do
  def s_exp
    value.to_s
  end

  def eval
    value
  end

  def zero?
    value.zero?
  end

  def one?
    value == 1
  end
end

MultiaryOp = Struct.new(:op, :operands) do
  def s_exp
    s_exps_of_operands = operands.map(&:s_exp)
    "(#{op} #{s_exps_of_operands.join(' ')})"
  end

  def eval
    operands
      .map(&:eval)
      .reduce(op)
  end
end

class Add < MultiaryOp
  def initialize(operands)
    super('+', operands)
  end
end

class Subtract < MultiaryOp
  def initialize(operands)
    super('-', operands)
  end
end

class Multiply < MultiaryOp
  def initialize(operands)
    super('*', operands)
  end
end

Negate = Struct.new(:term) do
  def s_exp
    "(- #{term.s_exp})"
  end
end

DiceRoll = Struct.new(:num, :sides) do
  def s_exp
    "(DiceRoll #{num.s_exp} #{sides.s_exp})"
  end
end

## parser.rb
# frozen_string_literal: true

require 'parslet'
require_relative 'node'

class DiceParser < Parslet::Parser
  root(:addition)

  rule(:add_op) { match['-+'].as(:o) }

  rule(:addition) {
    multiplication.as(:first) >> (add_op >> multiplication.as(:r)).repeat(1).as(:rest) |
    multiplication
  }

  rule(:mul_op) { match['*/'].as(:o) }

  rule(:multiplication) {
    term.as(:first) >> (mul_op >> term.as(:r)).repeat(1).as(:rest) | term
  }

  rule(:term) {
    negate | dice_roll | number
  }

  rule(:negate) {
    str('-') >> term.as(:neg_term)
  }

  rule(:number) { match('[0-9]').repeat(1).as(:n) }

  rule(:dice_roll) {
    number.as(:num) >> match['Dd'] >> number.as(:sides)
  }
end

class DiceASTGenerator < Parslet::Transform
  OP_TO_NODE_CLASS = {
    '+' => Add,
    '-' => Subtract,
    '*' => Multiply,
  }

  rule({
    n: simple(:n)
  }) {
    Number.new(n.to_i)
  }

  rule({
    first: simple(:first),
    rest: subtree(:rest)
  }) {
    root = first

    rest.each do |tree|
      op = tree[:o].to_s
      node_class = OP_TO_NODE_CLASS[op] || MultiaryOp
      root = node_class.new([root, tree[:r]])
    end

    root
  }

  rule({
    num: simple(:num),
    sides: simple(:sides)
  }) {
    DiceRoll.new(num, sides)
  }

  rule({
    neg_term: simple(:neg_term)
  }) {
    Negate.new(neg_term)
  }
end

## simplification.rb
# frozen_string_literal: true

require 'byebug'

class Simplification
  def initialize(ast, verbose = false)
    @root = Add.new([ast])
    @verbose = verbose
  end

  def run
    automatic_simplify(@root)
  end

  private

  def debug(*x)
    return unless @verbose
    puts(*x)
  end

  def automatic_simplify(u)
    debug("automatic_simplify: #{u.s_exp}")
    case u
    when Number, DiceRoll
      return u
    when MultiaryOp
      simplified_operands = u.operands.map { |o|
        automatic_simplify(o)
      }

      case u
      when Multiply
        return simplify_multiplication(Multiply.new(simplified_operands))
      when Add
        return simplify_addition(Add.new(simplified_operands))
      when Subtract
        return simplify_subtraction(Subtract.new(simplified_operands))
      else
        raise NotImplementedError, "#{u.class}: #{u.s_exp}"
      end
    when Negate
      simplified_term = automatic_simplify(u.term)
      return simplify_negation(Negate.new(simplified_term))
    else
      raise NotImplementedError
    end
  end

  def simplify_multiplication(u)
    if u.operands.any? { |v| v.is_a?(Number) && v.zero? }
      debug("simplify_multiplication: contains 0")
      return Number.new(0)
    end

    if u.operands.length == 1
      return u.operands.first
    end

    v = simplify_multiplication_rec(u.operands)
    case v.length
    when 0
      return Number.new(1)
    when 1
      return v.first
    else
      return Multiply.new(v)
    end
  end

  def simplify_multiplication_rec(operands)
    debug("simplify_multiplication_rec: operands = #{operands.map(&:s_exp)}")

    if operands.length == 2
      if operands.any? { |u| u.is_a?(Multiply) }
        return simplify_binary_multiplication_of_multiply_nodes(operands)
      end

      return simplify_binary_multiplication_of_non_multiply_nodes(operands)
    end

    return simplify_multiary_multiplication(operands)
  end

  def simplify_binary_multiplication_of_non_multiply_nodes(operands)
    u1, u2 = operands

    if operands.all? { |u| u.is_a?(Number) }
      product = u1.value * u2.value
      debug("  product: #{product}")
      return product == 1 ? [] : [Number.new(product)]
    end

    if u1.is_a?(Number) && u1.one?
      debug("  multiply 1: #{u2.s_exp}")
      return [u2]
    end

    if u2.is_a?(Number) && u2.one?
      debug("  multiply 1: #{u1.s_exp}")
      return [u1]
    end

    if !u1.is_a?(Number) && u2.is_a?(Number)
      debug("  flip: #{[u2, u1].map(&:s_exp)}")
      return [u2, u1]
    end

    return operands
  end

  def simplify_binary_multiplication_of_multiply_nodes(operands)
    u1, u2 = operands

    if u1.is_a?(Multiply) && !u2.is_a?(Multiply)
      return merge_multiplications(u1.operands, [u2])
    end

    if !u1.is_a?(Multiply) && u2.is_a?(Multiply)
      return merge_multiplications([u1], u2.operands)
    end

    return merge_multiplications(u1.operands, u2.operands)
  end

  def simplify_multiary_multiplication(operands)
    u1, *rest = operands
    w = simplify_multiplication_rec(rest)

    if u1.is_a?(Multiply)
      return merge_multiplications(u1.operands, w)
    end

    return merge_multiplications([u1], w)
  end

  def merge_multiplications(operands1, operands2)
    debug("  merge_multiplications: #{operands1.map(&:s_exp)}, #{operands2.map(&:s_exp)}")

    if operands2.empty?
      return operands1
    end

    if operands1.empty?
      return operands2
    end

    operands1_1, *operands1_rest = operands1
    operands2_1, *operands2_rest = operands2

    h = simplify_multiplication_rec([operands1_1, operands2_1])
    case h.length
    when 0, 1
      return h + merge_multiplications(operands1_rest, operands2_rest)
    when 2
      if h == [operands2_1, operands1_1]
        return [operands2_1] + merge_multiplications(operands1, operands2_rest)
      else
        return [operands1_1] + merge_multiplications(operands1_rest, operands2)
      end
    else
      raise "invalid length of simplify_multiplication_rec: #{h.length}"
    end
  end

  def simplify_addition(u)
    if u.operands.length == 1
      return u.operands.first
    end

    v = simplify_addition_rec(u.operands)
    case v.length
    when 0
      return Number.new(0)
    when 1
      return v.first
    else
      return Add.new(v)
    end
  end

  def simplify_addition_rec(operands)
    debug("simplify_addition_rec: operands = #{operands.map(&:s_exp)}")

    if operands.length == 2
      if operands.any? { |u| u.is_a?(Add) }
        return simplify_binary_addition_of_add_nodes(operands)
      end

      return simplify_binary_addition_of_non_add_nodes(operands)
    end

    return simplify_multiary_addition(operands)
  end

  def simplify_binary_addition_of_non_add_nodes(operands)
    u1, u2 = operands

    if operands.all? { |u| u.is_a?(Number) }
      sum = u1.value + u2.value
      debug("  sum: #{sum}")
      return sum == 0 ? [] : [Number.new(sum)]
    end

    if u1.is_a?(Number) && u1.zero?
      debug("  add zero: #{u2.s_exp}")
      return [u2]
    end

    if u2.is_a?(Number) && u2.zero?
      debug("  add zero: #{u1.s_exp}")
      return [u1]
    end

    return operands
  end

  def simplify_binary_addition_of_add_nodes(operands)
    u1, u2 = operands

    if u1.is_a?(Add) && !u2.is_a?(Add)
      return merge_additions(u1.operands, [u2])
    end

    if !u1.is_a?(Add) && u2.is_a?(Add)
      return merge_additions([u1], u2.operands)
    end

    return merge_additions(u1.operands, u2.operands)
  end

  def simplify_multiary_addition(operands)
    u1, *rest = operands
    w = simplify_addition_rec(rest)

    if u1.is_a?(Add)
      return merge_additions(u1.operands, w)
    end

    return merge_additions([u1], w)
  end

  def merge_additions(operands1, operands2)
    debug("  merge_additions: #{operands1.map(&:s_exp)}, #{operands2.map(&:s_exp)}")

    if operands2.empty?
      return operands1
    end

    if operands1.empty?
      return operands2
    end

    *operands1_rest, operands1_last = operands1
    operands2_1, *operands2_rest = operands2

    return merge_additions(
      operands1_rest + simplify_addition_rec([operands1_last, operands2_1]),
      operands2_rest
    )
  end

  def simplify_subtraction(u)
    case u.operands.length
    when 1
      return u.operands.first
    when 2
      v = Add.new([
        u.operands[0],
        automatic_simplify(Multiply.new([Number.new(-1), u.operands[1]]))
      ])

      return simplify_addition(v)
    else
      raise NotImplementedError
    end
  end

  def simplify_negation(u)
    v = Multiply.new([Number.new(-1), u.term])
    return simplify_multiplication(v)
  end
end
	require 'optparse'
	require_relative 'parser'
	require_relative 'simplification'

	opt = OptionParser.new
	verbose = false
	opt.on('-v', '--verbose', '冗長出力モード') do
	verbose = true
	end

	opt.parse!

	testcases = [
	'1+2',
	'2D6',
	'2D6+1',
	'1+2D6',
	'2D6+2*3+4',
	'1+23+2D6+4+52',
	'1-23+2D6-45+6',
	'1+2D6+3*4+1D6+5+6+7',
	'2D6-1D6*3',
	]

	testcases.each_with_index do \|c, i\|
	puts if i > 0
	puts(c)

	tree =
	begin
	DiceParser.new.parse(c)
	rescue => e
	puts("Parse error: #{e}")
	next
	end

	ast =
	begin
	DiceASTGenerator.new.apply(tree)
	rescue => e
	puts("AST generating error: #{e}")
	next
	end

	puts(" #{ast.s_exp}")

	simplified_ast = Simplification.new(ast, verbose).run
	puts(" #{simplified_ast.s_exp}")
	end
	# frozen_string_literal: true

	Number = Struct.new(:value) do
	def s_exp
	value.to_s
	end

	def eval
	value
	end

	def zero?
	value.zero?
	end

	def one?
	value == 1
	end
	end

	MultiaryOp = Struct.new(:op, :operands) do
	def s_exp
	s_exps_of_operands = operands.map(&:s_exp)
	"(#{op} #{s_exps_of_operands.join(' ')})"
	end

	def eval
	operands
	.map(&:eval)
	.reduce(op)
	end
	end

	class Add < MultiaryOp
	def initialize(operands)
	super('+', operands)
	end
	end

	class Subtract < MultiaryOp
	def initialize(operands)
	super('-', operands)
	end
	end

	class Multiply < MultiaryOp
	def initialize(operands)
	super('*', operands)
	end
	end

	Negate = Struct.new(:term) do
	def s_exp
	"(- #{term.s_exp})"
	end
	end

	DiceRoll = Struct.new(:num, :sides) do
	def s_exp
	"(DiceRoll #{num.s_exp} #{sides.s_exp})"
	end
	end
	# frozen_string_literal: true

	require 'parslet'
	require_relative 'node'

	class DiceParser < Parslet::Parser
	root(:addition)

	rule(:add_op) { match['-+'].as(:o) }

	rule(:addition) {
	multiplication.as(:first) >> (add_op >> multiplication.as(:r)).repeat(1).as(:rest) \|
	multiplication
	}

	rule(:mul_op) { match['*/'].as(:o) }

	rule(:multiplication) {
	term.as(:first) >> (mul_op >> term.as(:r)).repeat(1).as(:rest) \| term
	}

	rule(:term) {
	negate \| dice_roll \| number
	}

	rule(:negate) {
	str('-') >> term.as(:neg_term)
	}

	rule(:number) { match('[0-9]').repeat(1).as(:n) }

	rule(:dice_roll) {
	number.as(:num) >> match['Dd'] >> number.as(:sides)
	}
	end

	class DiceASTGenerator < Parslet::Transform
	OP_TO_NODE_CLASS = {
	'+' => Add,
	'-' => Subtract,
	'*' => Multiply,
	}

	rule({
	n: simple(:n)
	}) {
	Number.new(n.to_i)
	}

	rule({
	first: simple(:first),
	rest: subtree(:rest)
	}) {
	root = first

	rest.each do \|tree\|
	op = tree[:o].to_s
	node_class = OP_TO_NODE_CLASS[op] \|\| MultiaryOp
	root = node_class.new([root, tree[:r]])
	end

	root
	}

	rule({
	num: simple(:num),
	sides: simple(:sides)
	}) {
	DiceRoll.new(num, sides)
	}

	rule({
	neg_term: simple(:neg_term)
	}) {
	Negate.new(neg_term)
	}
	end
	# frozen_string_literal: true

	require 'byebug'

	class Simplification
	def initialize(ast, verbose = false)
	@root = Add.new([ast])
	@verbose = verbose
	end

	def run
	automatic_simplify(@root)
	end

	private

	def debug(*x)
	return unless @verbose
	puts(*x)
	end

	def automatic_simplify(u)
	debug("automatic_simplify: #{u.s_exp}")
	case u
	when Number, DiceRoll
	return u
	when MultiaryOp
	simplified_operands = u.operands.map { \|o\|
	automatic_simplify(o)
	}

	case u
	when Multiply
	return simplify_multiplication(Multiply.new(simplified_operands))
	when Add
	return simplify_addition(Add.new(simplified_operands))
	when Subtract
	return simplify_subtraction(Subtract.new(simplified_operands))
	else
	raise NotImplementedError, "#{u.class}: #{u.s_exp}"
	end
	when Negate
	simplified_term = automatic_simplify(u.term)
	return simplify_negation(Negate.new(simplified_term))
	else
	raise NotImplementedError
	end
	end

	def simplify_multiplication(u)
	if u.operands.any? { \|v\| v.is_a?(Number) && v.zero? }
	debug("simplify_multiplication: contains 0")
	return Number.new(0)
	end

	if u.operands.length == 1
	return u.operands.first
	end

	v = simplify_multiplication_rec(u.operands)
	case v.length
	when 0
	return Number.new(1)
	when 1
	return v.first
	else
	return Multiply.new(v)
	end
	end

	def simplify_multiplication_rec(operands)
	debug("simplify_multiplication_rec: operands = #{operands.map(&:s_exp)}")

	if operands.length == 2
	if operands.any? { \|u\| u.is_a?(Multiply) }
	return simplify_binary_multiplication_of_multiply_nodes(operands)
	end

	return simplify_binary_multiplication_of_non_multiply_nodes(operands)
	end

	return simplify_multiary_multiplication(operands)
	end

	def simplify_binary_multiplication_of_non_multiply_nodes(operands)
	u1, u2 = operands

	if operands.all? { \|u\| u.is_a?(Number) }
	product = u1.value * u2.value
	debug(" product: #{product}")
	return product == 1 ? [] : [Number.new(product)]
	end

	if u1.is_a?(Number) && u1.one?
	debug(" multiply 1: #{u2.s_exp}")
	return [u2]
	end

	if u2.is_a?(Number) && u2.one?
	debug(" multiply 1: #{u1.s_exp}")
	return [u1]
	end

	if !u1.is_a?(Number) && u2.is_a?(Number)
	debug(" flip: #{[u2, u1].map(&:s_exp)}")
	return [u2, u1]
	end

	return operands
	end

	def simplify_binary_multiplication_of_multiply_nodes(operands)
	u1, u2 = operands

	if u1.is_a?(Multiply) && !u2.is_a?(Multiply)
	return merge_multiplications(u1.operands, [u2])
	end

	if !u1.is_a?(Multiply) && u2.is_a?(Multiply)
	return merge_multiplications([u1], u2.operands)
	end

	return merge_multiplications(u1.operands, u2.operands)
	end

	def simplify_multiary_multiplication(operands)
	u1, *rest = operands
	w = simplify_multiplication_rec(rest)

	if u1.is_a?(Multiply)
	return merge_multiplications(u1.operands, w)
	end

	return merge_multiplications([u1], w)
	end

	def merge_multiplications(operands1, operands2)
	debug(" merge_multiplications: #{operands1.map(&:s_exp)}, #{operands2.map(&:s_exp)}")

	if operands2.empty?
	return operands1
	end

	if operands1.empty?
	return operands2
	end

	operands1_1, *operands1_rest = operands1
	operands2_1, *operands2_rest = operands2

	h = simplify_multiplication_rec([operands1_1, operands2_1])
	case h.length
	when 0, 1
	return h + merge_multiplications(operands1_rest, operands2_rest)
	when 2
	if h == [operands2_1, operands1_1]
	return [operands2_1] + merge_multiplications(operands1, operands2_rest)
	else
	return [operands1_1] + merge_multiplications(operands1_rest, operands2)
	end
	else
	raise "invalid length of simplify_multiplication_rec: #{h.length}"
	end
	end

	def simplify_addition(u)
	if u.operands.length == 1
	return u.operands.first
	end

	v = simplify_addition_rec(u.operands)
	case v.length
	when 0
	return Number.new(0)
	when 1
	return v.first
	else
	return Add.new(v)
	end
	end

	def simplify_addition_rec(operands)
	debug("simplify_addition_rec: operands = #{operands.map(&:s_exp)}")

	if operands.length == 2
	if operands.any? { \|u\| u.is_a?(Add) }
	return simplify_binary_addition_of_add_nodes(operands)
	end

	return simplify_binary_addition_of_non_add_nodes(operands)
	end

	return simplify_multiary_addition(operands)
	end

	def simplify_binary_addition_of_non_add_nodes(operands)
	u1, u2 = operands

	if operands.all? { \|u\| u.is_a?(Number) }
	sum = u1.value + u2.value
	debug(" sum: #{sum}")
	return sum == 0 ? [] : [Number.new(sum)]
	end

	if u1.is_a?(Number) && u1.zero?
	debug(" add zero: #{u2.s_exp}")
	return [u2]
	end

	if u2.is_a?(Number) && u2.zero?
	debug(" add zero: #{u1.s_exp}")
	return [u1]
	end

	return operands
	end

	def simplify_binary_addition_of_add_nodes(operands)
	u1, u2 = operands

	if u1.is_a?(Add) && !u2.is_a?(Add)
	return merge_additions(u1.operands, [u2])
	end

	if !u1.is_a?(Add) && u2.is_a?(Add)
	return merge_additions([u1], u2.operands)
	end

	return merge_additions(u1.operands, u2.operands)
	end

	def simplify_multiary_addition(operands)
	u1, *rest = operands
	w = simplify_addition_rec(rest)

	if u1.is_a?(Add)
	return merge_additions(u1.operands, w)
	end

	return merge_additions([u1], w)
	end

	def merge_additions(operands1, operands2)
	debug(" merge_additions: #{operands1.map(&:s_exp)}, #{operands2.map(&:s_exp)}")

	if operands2.empty?
	return operands1
	end

	if operands1.empty?
	return operands2
	end

	*operands1_rest, operands1_last = operands1
	operands2_1, *operands2_rest = operands2

	return merge_additions(
	operands1_rest + simplify_addition_rec([operands1_last, operands2_1]),
	operands2_rest
	)
	end

	def simplify_subtraction(u)
	case u.operands.length
	when 1
	return u.operands.first
	when 2
	v = Add.new([
	u.operands[0],
	automatic_simplify(Multiply.new([Number.new(-1), u.operands[1]]))
	])

	return simplify_addition(v)
	else
	raise NotImplementedError
	end
	end

	def simplify_negation(u)
	v = Multiply.new([Number.new(-1), u.term])
	return simplify_multiplication(v)
	end
	end