Skip to content

Instantly share code, notes, and snippets.

@ochaochaocha3
Last active Apr 19, 2020
Embed
What would you like to do?
式の簡単化

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

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)))
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
# 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment