{{ message }}

Instantly share code, notes, and snippets.

Last active Apr 19, 2020

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

実行例

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)"

1+2

(+ 1 2)
automatic_simplify: (+ (+ 1 2))
automatic_simplify: (+ 1 2)
automatic_simplify: 1
automatic_simplify: 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"]
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
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"]
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
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"]
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"]
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"]
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)))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 # 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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 # 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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters