arithmetic_puzzle_solver.rb

# Solves arithmetic puzzle.
# Input four integers and the expected answer
# and the program searches a possible expression.
#
# e.g.
# in: 1,3,9,0 and 10
# out: 1+(3*0)+9
# in: 3,4,7,8 and 10
# out: (3-7/4)*8

OPERATORS = [:+, :-, :*, :/]
PARENTHESES = [
  [[0, 1]], # (a op b) op c op d
  [[1, 2]], # a op (b op c) op d
  [[2, 3]], # a op b op (c op d)
  [[0, 2]], # (a op b op c) op d
  [[1, 3]], # a op (b op c op d)
  [[0, 1], [2, 3]], # (a op b) op (c op d)
  [[0, 2], [0, 1]], # ((a op b) op c) op d
  [[0, 2], [1, 2]], # (a op (b op c)) op d
  [[1, 3], [1, 2]], # a op ((b op c) op d)
  [[1, 3], [2, 3]], # a op (b op (c op d))
]

puts "give me 4 numbers: e.g. 1,1,9,9"
nums = gets.chomp.split(',').map(&:to_i)

puts "give me the expected answer: e.g. 10"
ans = gets.chomp.to_i

combinations = []
64.times do |i|
  combination = []
  arr = i.digits(4)
  while arr.length < 3
    arr << 0
  end
  arr.each do |j|
    combination << OPERATORS[j]
  end
  combinations << combination
end

nums.permutation do |permutation|
  combinations.each do |combination|
    arr = permutation.map { |num| "#{num}.to_r" }
    PARENTHESES.each do |parenthesis|
      arr = arr.zip(combination).flatten
      inserted = []
      parenthesis.reverse.each do |(l, r)|
        n = l * 2
        m = r * 2 + 1

        offset = inserted.count { |i| i <= m }
        arr.insert(m+offset, ')')
        inserted << m

        offset = inserted.count { |i| i <= n }
        arr.insert(n+offset, '(')
        inserted << n
      end
      exp = arr.join('')
      begin
        if eval(exp) == ans
          puts exp.tr('.to_r', '')
          exit
        end
      rescue ZeroDivisionError
        # no-op
      end
      arr = permutation.map { |num| "#{num}.to_r" }
    end
  end
end

puts 'impossible'