calc-main.rb

calc-main.rb

# 4,6,6,5,6 を１つずつと四則演算、累乗のみを使って 777を作る

def solve(nums)
  if nums.length === 1
    yield({val: nums[0]})
    return
  end
  len = nums.length
  len.times do |i|
    solve(nums[0...i]) do |l|
      solve(nums[i...len]) do |r|
        [:add, :minus, :times, :div, :power].each do |action|
          yield({l: l, r: r, action: action})
        end
      end
    end
  end
end

def tree_text(tree)
  return tree[:val].to_s unless tree[:val].nil?
  "(#{tree_text(tree[:l])}#{op(tree[:action])}#{tree_text(tree[:r])})"
end

MAX = 10 ** 9

class OutOfRangeError < Exception; end

def tree_val(tree)
  return tree[:val] unless tree[:val].nil?
  l = tree_val(tree[:l])
  r = tree_val(tree[:r])
  raise OutOfRangeError if l > MAX || r > MAX
  res = case tree[:action]
        when :add
          l + r
        when :minus
          l - r
        when :div
          raise OutOfRangeError if l % r != 0
          l / r
        when :times
          l * r
        when :power
          raise OutOfRangeError if r < 0 || r > 50
          l ** r
        end
  raise OutOfRangeError if res.abs > MAX
  res
end

def op(sym)
  case sym
  when :add
    '+'
  when :minus
    '-'
  when :div
    '/'
  when :times
    '*'
  when :power
    '**'
  end
end

nums = [4, 6, 6, 5, 6]
ans = []
nums.permutation.to_a.uniq.each do |nums|
  solve(nums) do |expr|
    begin
      val = tree_val(expr)
      text = tree_text(expr)
      ans.push({val: val, text: text})
      puts "#{text}=#{val}" if false
    rescue ZeroDivisionError, OutOfRangeError => ex
      next
    end
  end
end
ans.uniq! {|a| a[:val]}
ans.sort {|a, b| a[:val] <=> b[:val]}.each do |item|
  puts "#{item[:text]}=#{item[:val]}"
end