puzzle for 4-numbers. 4 つの数字から四則演算して 10 になるような計算式を得る。(num10.rb) 指定した個数の数字から四則演算して、指定した値になるような計算式を得る。(num10ex.rb)

num10.rb

# -*- coding: utf-8 -*-

# 演算子の優先度を返す
OP_INFO = {
  # 演算子 => [優先度、演算]
  '+' => { priority: 1, func: 'func_add' },
  '-' => { priority: 1, func: 'func_sub' },
  '*' => { priority: 2, func: 'func_mul' },
  '/' => { priority: 2, func: 'func_div' },
  # '**' => { priority: 3, func: 'func_exp' },
}
OPS = OP_INFO.keys

def func_add(a, b); a + b; end
def func_sub(a, b); a - b; end
def func_mul(a, b); a * b; end
def func_div(a, b)
  raise "invalid expression. div by zero #{a} / #{b}" if b == 0
  a / b
end
def func_exp(a, b); a ** b; end

# 逆ポ−ランド記法を数値評価する。
#  [1, 2, '+'] => 3
#  [1, 2, '+', 3, '*'] => 9
def eval_stack(stack)
  ans = []
  stack.each do |st|
    case st
    when 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
      ans.push Rational(st)
    else
      fail 'internal error. #{stack}' if ans.size < 2  # エラー
      (b, a) = [ans.pop, ans.pop]
      ans.push send(OP_INFO[st][:func], a, b)
    end
  end
  fail "internal error. #{stack}" unless ans.size == 1
  ans[0]
end

# 逆ポーランド記法から構文木に変換する。
# [n1, n2, op1, n3, n4, op2, op3] => [op3, [op1, n1, n2], [op2, n3, n4]]
def to_tree(stack)
  tree = []
  stack.each do |st|
    case st
    when 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
      tree.push "#{st}"
    else
      fail "internal error. #{stack}" if tree.size < 2
      (right, left) = [tree.pop, tree.pop]
      tree.push([st, left, right])
    end
  end
  fail "internal error. #{stack}" unless tree.size == 1
  tree[0]
end

# 候分木を数式表記にする。余分な (, ) を出さないようにする。
# 計算順序が無視できる場合は、小さい値をなるべく左にする ("2 + 1" => "1 + 2", "4 * 3" => "3 * 4"
def to_expression(tree)
  _to_expression(tree)[0]
end

def _to_expression(tree)
  ans = ''
  pr = 0
  if tree.kind_of? Array
    op = tree[0]

    pr = OP_INFO[op][:priority]
    (term_1, pr_1) = _to_expression(tree[1])
    (term_2, pr_2) = _to_expression(tree[2])

    term_1 = "(#{term_1})" if pr_1 < pr
    term_2 = "(#{term_2})" if pr_2 < pr || ((op == '-' || op == '/') && term_2.length > 1)

    (term_1, term_2) = [term_2, term_1] if (op == '+' || op == '*') && term_1 > term_2
    ans += "#{term_1} #{op} #{term_2}"
  else
    ans += "#{tree}"
    pr = 9
  end
  [ans, pr]
end

# '+', '*' の可換性を加味して、試行すべき構文木を列挙する。
def get_stack_patterns(n1, n2, n3, n4, op1, op2, op3)
  stacks = []
  if (op1 == '+' && op2 == '+' && op3 == '+') || (op1 == '*' && op2 == '*' && op3 == '*')
    (n1, n2, n3, n4) = [n1, n2, n3, n4].sort
    stacks = [
      [n1, n2, n3, n4, op1, op2, op3]    # 1 op4 2 op 2 3 op1 4     # 1 + 2 + 3 + 4, 1 * 2 * 3 * 4
    ]
  elsif (op1 == '+' && op2 == '+') || (op1 == '*' && op2 == '*')
    stacks = [
      [n1, n2, n3, n4, op1, op2, op3],   # 1 op3 (2 op2 (3 op1 4))   # 1 / (2 + 3 + 4)
      [n1, n2, op1, n3, op2, n4, op3],   # ((1 op1 2) op2 3) op3 4   # (1 + 2 + 3) / 4
      [n1, n2, op1, n3, n4, op2, op3],   # (1 op1 2) op3 (3 op2 4)   # (1 + 2) / (3 + 4)
      # [n1, n2, n3, op1, n4, op2, op3],   # 1 op3 ((2 op1 3) op2 4) # 1 / (2 + 3 + 4)
      # [n1, n2, n3, op1, op2, n4, op3],   # (1 op2 (2 op1 3)) op3 4 # (1 + 2 + 3) / 4
    ]
  elsif (op2 == '+' && op3 == '+') || (op2 == '*' && op3 == '*')
    stacks = [
      [n1, n2, n3, n4, op1, op2, op3],   # 1 op3 (2 op2 (3 op1 4))   # 1 + 2 + 3 / 4
      [n1, n2, op1, n3, op2, n4, op3],   # ((1 op1 2) op2 3) op3 4   # 1 / 2 + 3 + 4
      # [n1, n2, op1, n3, n4, op2, op3],   # (1 op1 2) op3 (3 op2 4) # 1 / 2 + 3 + 4
      [n1, n2, n3, op1, n4, op2, op3],   # 1 op3 ((2 op1 3) op2 4)   # 1 + 2 / 3 + 4
      # [n1, n2, n3, op1, op2, n4, op3],   # (1 op2 (2 op1 3)) op3 4 # 1 + 2 / 3 + 4
    ]
  else
    stacks = [
      [n1, n2, n3, n4, op1, op2, op3],   # 1 op3 (2 op2 (3 op1 4))   # 1 / (2 + (3 + 4))
      [n1, n2, op1, n3, op2, n4, op3],   # ((1 op1 2) op2 3) op3 4   # ((1 + 2) + 3) / 4
      [n1, n2, op1, n3, n4, op2, op3],   # (1 op1 2) op3 (3 op2 4)   # (1 + 2) / (3 + 4)
      [n1, n2, n3, op1, n4, op2, op3],   # 1 op3 ((2 op1 3) op2 4)   # 1 / ((2 + 3) + 4)
      [n1, n2, n3, op1, op2, n4, op3],   # (1 op2 (2 op1 3)) op3 4   # (1 + (2 + 3)) / 4
    ]
  end
  stacks
end

# nums =[n1, n2, n3m n4]から四則演算で goal 値にする計算式を配列で得る。
def solve(nums, goal)
  ans = []
  nums.permutation(4).each do |n1, n2, n3, n4|
    OPS.repeated_permutation(3).each do |op1, op2, op3|
      get_stack_patterns(n1, n2, n3, n4, op1, op2, op3).each do |st|
        begin
          ans.push(to_expression(to_tree(st)))  if (eval_stack(st) - goal) == 0
        rescue => ex
          fail ex unless ex.message.index('invalid expression')
        end
      end
    end
  end
  ans.sort.uniq
end

# ４桁数字のすべての組み合わせに対して、四則演算で 10 になる計算式を得る。
goal = 10.0
goal = ARGV[0].to_i if ARGV.size == 1

[1, 2, 3 , 4, 5, 6, 7, 8, 9].repeated_combination(4) do |*digits|
  sol = solve(digits[0], goal)

  printf "#{digits[0]} #{sprintf('%03d', sol.size)}"
  if sol.size < 4
    sol.each_with_index do |s, idx|
      printf idx < 4 ? "\t\t#{s}" : "\n\t\t#{s}"
    end
    puts
  else
    puts
    sol.each { |s| puts "\t\t#{s}" }
  end
end
//--- End of File ---

num10ex.rb

# -*- coding: utf-8 -*-

# 演算子の優先度を返す
OP_INFO = {
  # 演算子 => [優先度、演算]
  '+' => { priority: 1, func: 'func_add' },
  '-' => { priority: 1, func: 'func_sub' },
  '*' => { priority: 2, func: 'func_mul' },
  '/' => { priority: 2, func: 'func_div' },
  # '**' => { priority: 3, func: 'func_exp' },
}
OPS = OP_INFO.keys

def func_add(a, b); a + b; end
def func_sub(a, b); a - b; end
def func_mul(a, b); a * b; end
def func_div(a, b)
  raise "invalid expression. div by zero #{a} / #{b}" if b == 0
  Rational(a, b)
end
def func_exp(a, b); a ** b; end

# 構文木を数値評価する。
#  ['+', 1, 2] => 3
#  ['*', ['+', 1, 3], 3] => 9
def eval_tree(tree)
  ans = 0
  if tree.kind_of? Array
    if tree.size == 3
      ans = send(OP_INFO[tree[0]][:func], eval_tree(tree[1]), eval_tree(tree[2]))
    elsif tree.size == 1
      ans = tree[0]
    else
      fail "illegal tree #{tree}"
    end
  else
    ans = tree
  end
  ans
end

# 構文木を数式表記にする。余分な (, ) を出さないようにする。
# 計算順序が無視できる場合は、小さい値をなるべく左にする ("2 + 1" => "1 + 2", "4 * 3" => "3 * 4"
def to_expression(tree)
  _to_expression(tree)[0]
end

def _to_expression(tree)
  ans = ''
  pr = 0
  if tree.kind_of? Array
    op = tree[0]

    pr = OP_INFO[op][:priority]
    (term_1, pr_1) = _to_expression(tree[1])
    (term_2, pr_2) = _to_expression(tree[2])

    term_1 = "(#{term_1})" if pr_1 < pr
    term_2 = "(#{term_2})" if pr_2 < pr || ((op == '-' || op == '/') && term_2.length > 1)

    (term_1, term_2) = [term_2, term_1] if (op == '+' || op == '*') && term_1 > term_2
    ans += "#{term_1} #{op} #{term_2}"
  else
    ans += "#{tree}"
    pr = 9
  end
  [ans, pr]
end

# 逆ポーランド記法から構文木に変換する。
# [n1, n2, op1, n3, n4, op2, op3] => [op3, [op1, n1, n2], [op2, n3, n4]]
def to_tree(stack)
  tree = []
  stack.each do |st|
    case st
    when 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
      tree.push st
    else
      fail "internal error. #{stack}" unless OPS.include?(st)
      fail "internal error. #{stack}" if tree.size < 2
      (right, left) = [tree.pop, tree.pop]
      tree.push([st, left, right])
    end
  end
  tree[0]
end

# 試行すべき式のパターンを逆ポーランド式で列挙する。(1, + だけで構成したパターン)
def get_stack_patterns(num_digits)
  stacks = []

  ops_size = num_digits - 1
  ary_size = num_digits * 2 - 1

  # 逆ポーランド記法で計算式のパターンを組み立てる。(1, + だけで)
  idxs = []
  (2 .. (ary_size - 2)).each { |i| idxs << i }
  idxs.combination(ops_size - 1).each do |*idss|
    stack = Array.new(ary_size, 1)
    stack[-1] = '+'
    idss.each do |ids|
      ids.each { |id|stack[id] = '+' }
    end
    begin
      # 構文木に変換可能な式だけを残す。
      to_tree(stack)
      stacks << stack
    rescue => _ex
      # ignore error
    end
  end
  stacks
end

# 試行すべき計算式の高分岐を得る。
def get_tree_patterns_with_val(dgs, ops)
  trees = []
  stacks = get_stack_patterns(dgs.size)
  stacks = [stacks[-1]] if ops.sort.uniq.size == 1 && (ops[0] == '+' || ops[0] == '*')

  # 1, + だけでの逆ポーランド式に 実際の数字と演算子を埋め込む
  stacks.each do |st|
    dgsx = dgs.clone
    dgsx.sort! if stacks.size == 1
    opsx = ops.clone
    st_with_val = []
    st.each { |item| st_with_val << (item == 1 ?  dgsx.shift : opsx.shift) }
    fail "internal error #{st}" if dgsx.size > 0 || opsx.size > 0
    trees << to_tree(st_with_val)
  end
  trees
end

# nums =[n1, n2, ..., n#{num_digits}] から四則演算で goal 値にする計算式を配列で得る。
def solve(nums, goal = 10.0, num_digits = 4)
  ans = []
  nums.permutation(num_digits).each do |*dgs|
    OPS.repeated_permutation(num_digits - 1).each do |*ops|
      ops.freeze
      get_tree_patterns_with_val(dgs[0], ops[0]).each do |tree|
        begin
          ans.push(to_expression(tree)) if eval_tree(tree) == goal
        rescue => ex
          raise ex unless ex.message.index('invalid expression')
        end
      end
    end
  end
  ans.sort.uniq
end

# ４桁数字のすべての組み合わせに対して、四則演算で 10 になる計算式を得る。
goal = 10.0
num_digits = 4

goal = ARGV[0].to_i if ARGV.size > 0
num_digits = ARGV[1].to_i if ARGV.size > 1

[1, 2, 3 , 4, 5, 6, 7, 8, 9].repeated_combination(num_digits) do |*digits|
  sol = solve(digits[0], goal, num_digits)

  printf "#{digits[0]} #{sprintf('%03d', sol.size)}"
  if sol.size < 4
    sol.each_with_index do |s, idx|
      printf idx < 4 ? "\t\t#{s}" : "\n\t\t#{s}"
    end
    puts
  else
    puts
    sol.each { |s| puts "\t\t#{s}" }
  end
end

sample-run-ex.txt

$ ruby num10ex.rb 10 5 > 10-5.txt

$ grep 001 10-5.txt 
[4, 4, 4, 4, 4] 001		(4 + 4) / 4 + 4 + 4
[5, 9, 9, 9, 9] 001		(9 / 9 + 9 / 9) * 5
[7, 7, 7, 7, 7] 001		(7 + 7 + 7) / 7 + 7

$ grep 002 10-5.txt 
[1, 1, 1, 1, 3] 002		(1 + 1 + 1) * 3 + 1		(1 + 1 + 3) * (1 + 1)
[1, 1, 1, 7, 7] 002		(7 - 1) / (1 + 1) + 7		7 - ((1 - 7) / (1 + 1))
[1, 7, 7, 7, 7] 002		(7 + 7) / 7 + 1 + 7		(7 + 7) / 7 + 7 + 1
[6, 6, 6, 6, 6] 002		6 + 6 - ((6 + 6) / 6)		6 - ((6 + 6) / 6 - 6)
[6, 6, 7, 7, 7] 002		6 + 6 - ((7 + 7) / 7)		6 - ((7 + 7) / 7 - 6)

$ wc 10-5.txt
  350206 3148272 8097452 10-5.txt

sample-run.txt

$ ruby num10.rb > all.rb

$ head all.txt
[1, 1, 1, 1] 000
[1, 1, 1, 2] 000
[1, 1, 1, 3] 000
[1, 1, 1, 4] 001		(1 + 1) * (1 + 4)
[1, 1, 1, 5] 008
		(1 + 1 * 1) * 5
		(1 + 1 / 1) * 5
		(1 + 1) * 1 * 5
		(1 + 1) * 5 * 1
		(1 + 1) * 5 / 1

$ grep 001 all.txt
[1, 1, 1, 4] 001		(1 + 1) * (1 + 4)
[1, 1, 1, 6] 001		(1 + 1) * (6 - 1)
[1, 1, 1, 7] 001		1 + 1 + 1 + 7
[1, 1, 4, 4] 001		1 + 1 + 4 + 4
[1, 1, 4, 9] 001		(1 + 1) * (9 - 4)
[1, 1, 5, 8] 001		8 / (1 - (1 / 5))
[1, 1, 6, 7] 001		6 / (1 + 1) + 7
[1, 1, 8, 9] 001		(1 + 1) * 9 - 8
[1, 1, 9, 9] 001		(1 + 1 / 9) * 9
[1, 3, 3, 7] 001		(1 + 7 / 3) * 3
[1, 3, 8, 8] 001		8 + 8 / (1 + 3)
[1, 5, 5, 5] 001		(1 + 5 / 5) * 5
[1, 5, 6, 6] 001		(1 + 6 / 6) * 5
[1, 5, 9, 9] 001		(1 + 9 / 9) * 5
[2, 2, 8, 9] 001		(9 - (8 / 2)) * 2
[2, 2, 9, 9] 001		(2 + 9 + 9) / 2
[2, 6, 6, 6] 001		(6 - (6 / 6)) * 2
[3, 3, 3, 3] 001		3 * 3 + 3 / 3
[3, 3, 5, 7] 001		(3 * 3 - 7) * 5
[3, 3, 6, 6] 001		3 * 3 + 6 / 6
[3, 3, 7, 7] 001		3 * 3 + 7 / 7
[3, 4, 6, 6] 001		(4 * 6 + 6) / 3
[3, 4, 7, 8] 001		(3 - (7 / 4)) * 8
[3, 5, 7, 7] 001		(3 - (7 / 7)) * 5
[3, 5, 8, 8] 001		(3 - (8 / 8)) * 5
[4, 4, 4, 9] 001		(4 + 4 * 9) / 4
[4, 4, 6, 6] 001		(4 + 6 * 6) / 4
[4, 4, 6, 7] 001		(6 - 4) * 7 - 4
[4, 5, 5, 9] 001		(5 * 9 - 5) / 4
[4, 6, 7, 9] 001		(7 + 9) / 4 + 6
[5, 5, 5, 7] 001		5 * 7 - (5 * 5)
[5, 5, 5, 9] 001		(5 + 5 * 9) / 5
[5, 6, 7, 9] 001		(6 + 9) / 5 + 7
[5, 7, 7, 8] 001		(7 + 8) / 5 + 7
[7, 7, 7, 8] 001		(7 + 7) / 7 + 8
[7, 7, 7, 9] 001		(7 + 7 * 9) / 7
[7, 8, 8, 9] 001		(7 + 9) / 8 + 8
[7, 8, 9, 9] 001		(9 - 7) * 9 - 8
[8, 8, 8, 8] 001		(8 + 8) / 8 + 8
[8, 8, 8, 9] 001		(8 + 8 * 9) / 8
[8, 9, 9, 9] 001		(9 + 9) / 9 + 8
[9, 9, 9, 9] 001		(9 + 9 * 9) / 9

$ grep 002 all.txt
[1, 1, 6, 8] 002		(1 + 1) * 8 - 6		6 + 8 / (1 + 1)
[1, 2, 2, 2] 002		(1 + 2 * 2) * 2		(1 + 2 + 2) * 2
[1, 2, 7, 7] 002		(7 - 1) / 2 + 7		7 - ((1 - 7) / 2)
[1, 2, 8, 8] 002		(1 + 2 / 8) * 8		(1 + 8) * 2 - 8
[1, 3, 3, 3] 002		(1 / 3 + 3) * 3		1 + 3 + 3 + 3
[1, 3, 3, 6] 002		(6 - 3) * 3 + 1		1 - ((3 - 6) * 3)
[1, 7, 7, 8] 002		1 + 7 / 7 + 8		1 + 8 + 7 / 7
[1, 8, 8, 8] 002		1 + 8 + 8 / 8		1 + 8 / 8 + 8
[2, 2, 2, 2] 002		(2 + 2) * 2 + 2		2 + 2 * 2 * 2
[2, 2, 7, 9] 002		(2 * 7 - 9) * 2		(7 + 9) / 2 + 2
[2, 4, 7, 7] 002		(2 - (4 / 7)) * 7		(4 + 7 / 7) * 2
[2, 5, 5, 7] 002		2 + 5 / 5 + 7		2 + 7 + 5 / 5
[2, 7, 7, 7] 002		2 + 7 + 7 / 7		2 + 7 / 7 + 7
[3, 3, 3, 6] 002		3 + 3 / 3 + 6		3 + 6 + 3 / 3
[3, 3, 3, 9] 002		(3 + 3 * 9) / 3		(3 + 3 / 9) * 3
[3, 3, 4, 9] 002		3 + 4 + 9 / 3		3 + 9 / 3 + 4
[4, 4, 4, 8] 002		(4 + 4) / 4 + 8		4 + 4 + 8 / 4
[4, 8, 8, 8] 002		8 + 8 / (8 - 4)		8 - (8 / (4 - 8))
[5, 8, 8, 9] 002		8 + 8 / (9 - 5)		8 - (8 / (5 - 9))
[6, 6, 7, 8] 002		6 / (8 - 6) + 7		7 - (6 / (6 - 8))
[6, 7, 7, 9] 002		6 / (9 - 7) + 7		7 - (6 / (7 - 9))
[6, 7, 8, 8] 002		(6 + 8 * 8) / 7		(6 + 8) / 7 + 8
[6, 8, 8, 9] 002		(8 - 6) * 9 - 8		8 * 8 - (6 * 9)