JAMAICA solver

jamaica.rb

#!/usr/bin/env ruby
# -*- coding: utf-8 -*-

# JAMAICA solver
#   by takehikom (http://d.hatena.ne.jp/takehikom/)

# Usage:
#   ruby jamaica.rb | more
#   ruby jamaica.rb 25 1 3 2 4 1

class Array
  def remove(*a)
    # [1, 1, 2].remove(1) #=> [1, 2]
    # [1, 1, 2].delete_if {|x| x == 1} #=> [2]
    # [1, 1, 2].remove(1, 2) #=> [1]
    ary = self.dup
    a.each do |e|
      i = ary.index(e)
      next if i.nil?
      ary.delete_at(i)
    end
    ary
  end

  def each_one
    self.uniq.each do |i|
      yield(i)
    end
  end

  # This is not used at present but defined to generate an equality
  # such as "(1+3)*(2+4)+1=25" in the future.
  def each_two
    return if length < 2
    each_one do |i|
      remove(i).each_one do |j|
        yield(i, j)
      end
    end
  end
end

class Rational
  def to_i_or_r
    denominator == 1 ? numerator : self
  end
end

module Jamaica
  class Solver
    def initialize(param)
      if param.empty?
        param = [21, 4, 1, 3, 6, 4]
        # http://www.amazon.co.jp/dp/4902756161
      end
      @nums = param.map {|item| item.to_i}
      @goal = @nums.shift
      @opt_el = false # true if "elementary school arithmetic" only
      @opt_neg = !@opt_el # true if negative numbers permitted
      @opt_rat = !@opt_el # true if rational numbers permitted
    end

    def eval(s)
      Kernel.eval(s.gsub(/\d/, 'Rational(\&)')).to_i_or_r
    end

    def resolve(g = @goal, ary = @nums)
      result = []
      return [] if ary.empty?
      return [] if !@opt_neg && g < 0
      return [] if !@opt_rat && Rational === g && g.denominator > 1

      if ary.length == 1
        if g == ary.first
          return [g.to_i]
        else
          return []
        end
      end

      # ary.length >= 2
      binary = (ary.length == 2)

      # g == i + {{ary.remove(i)}}
      ary.each_one do |i|
        resolve(g - i, ary.remove(i)).each do |ans_i|
          if @opt_el
            if binary
              result << "#{i}＋#{ans_i}＝#{ir(g)}"
              result << "#{ans_i}＋#{i}＝#{ir(g)}"
            else
              ans_last = ans_i.split(/＝/)[-1]
              result << "#{ans_i}　#{i}＋#{ans_last}＝#{ir(g)}"
              result << "#{ans_i}　#{ans_last}＋#{i}＝#{ir(g)}"
            end
          else
            result << "#{i}+#{ans_i}"
            result << "#{ans_i}+#{i}"
          end
        end
      end

      # g == i - {{ary.remove(i)}}
      ary.each_one do |i|
        resolve(i - g, ary.remove(i)).each do |ans_i|
          if @opt_el
            if binary
              result << "#{i}－#{ans_i}＝#{ir(g)}"
            else
              ans_last = ans_i.split(/＝/)[-1]
              result << "#{ans_i}　#{i}－#{ans_last}＝#{ir(g)}"
            end
          else
            result << (binary ? "#{i}-#{ans_i}" : "#{i}-(#{ans_i})")
          end
        end
      end

      # g == i * {{ary.remove(i)}}
      ary.each_one do |i|
        next if i == 0
        resolve(Rational(g) / i, ary.remove(i)).each do |ans_i|
          if @opt_el
            if binary
              result << "#{i}×#{ans_i}＝#{ir(g)}"
              result << "#{ans_i}×#{i}＝#{ir(g)}"
            else
              ans_last = ans_i.split(/＝/)[-1]
              result << "#{ans_i}　#{i}×#{ans_last}＝#{ir(g)}"
              result << "#{ans_i}　#{ans_last}×#{i}＝#{ir(g)}"
            end
          else
            result << (binary ? "#{i}*#{ans_i}" : "#{i}*(#{ans_i})")
            result << (binary ? "#{ans_i}*#{i}" : "(#{ans_i})*#{i}")
          end
        end
      end

      # g == i / {{ary.remove(i)}}
      ary.each_one do |i|
        next if g == 0
        resolve(Rational(i) / g, ary.remove(i)).each do |ans_i|
          if @opt_el
            if binary
              result << "#{i}÷#{ans_i}＝#{ir(g)}"
            else
              ans_last = ans_i.split(/＝/)[-1]
              result << "#{ans_i}　#{i}÷#{ans_last}＝#{ir(g)}"
            end
          else
            result << (binary ? "#{i}/#{ans_i}" : "#{i}/(#{ans_i})")
          end
        end
      end

      # g == {{ary.remove(i)}} - i
      ary.each_one do |i|
        resolve(g + i, ary.remove(i)).each do |ans_i|
          if @opt_el
            if binary
              result << "#{ans_i}－#{i}＝#{ir(g)}"
            else
              ans_last = ans_i.split(/＝/)[-1]
              result << "#{ans_i}　#{ans_last}－#{i}＝#{ir(g)}"
            end
          else
            result << "#{ans_i}-#{i}"
          end
        end
      end

      # g == {{ary.remove(i)}} / i
      ary.each_one do |i|
        resolve(g * i, ary.remove(i)).each do |ans_i|
          if @opt_el
            if binary
              result << "#{ans_i}÷#{i}＝#{ir(g)}"
            else
              ans_last = ans_i.split(/＝/)[-1]
              result << "#{ans_i}　#{ans_last}÷#{i}＝#{ir(g)}"
            end
          else
            result << (binary ? "#{ans_i}/#{i}" : "(#{ans_i})/#{i}")
          end
        end
      end

      # return result if ary.length == 2
      # ary.length >= 3

      return result
    end

    def start
      result = resolve.sort.uniq
      puts "goal = #{@goal}; nums = #{@nums.join(', ')}"
      puts "#{result.size} answer(s)."
      result.each do |ans|
        if @opt_el
          puts ans
        else
          puts "#{ans} = #{eval(ans)}"
        end
      end
    end

    private

    def ir(num)
      (Rational === num) ? num.to_i_or_r : num
    end
  end
end

if __FILE__ == $0
  Jamaica::Solver.new(ARGV).start
end