countdown numbers problem solver

countdown.rb

#!/usr/bin/env ruby

# countdown numbers problem solver
# 
# given a set of 6 numbers, typically `100`, `25` and four random numbers between 1 and 10
# use +, -, * and / (integer division) to arrive at a specified 3-digit target number
# numbers cannot be reused
# 
# this ruby script finds the first solution from a recursive depth-first search
# see at the bottom how to run it
# 
# the idea is to model (intermediate) operations that combine other operations.
# we start with simple assignment operations that just wrap the input numbers
# then we iterate over all combinations of operations to pick 2 and recurse
# we are done when the result of one of the operations equals the target number
# 
# home work: find the minimal solution (least number of operations)
# (would have worse runtime, though, because would need to brute-force and compare all combinations)


class Operation
  attr_reader :n # result of operation
end

class AssignmentOperation < Operation
  def initialize(n)
    @n = n
  end
  
  def to_s
    "#{n}"
  end
end

class AdditionOperation < Operation
  def initialize(o1, o2)
    @o1 = o1
    @o2 = o2
    @n = o1.n + o2.n
  end
  
  def to_s
    "(#{@o1} + #{@o2} = #{@n})"
  end
end

class MultiplicationOperation < Operation
  def initialize(o1, o2)
    @o1 = o1
    @o2 = o2
    @n = o1.n * o2.n
  end
  
  def to_s
    "(#{@o1} * #{@o2} = #{@n})"
  end
end

# maybe a simplification: avoid negative numbers
class SubstractionOperation < Operation
  def initialize(o1, o2)
    if o1.n >= o2.n
      @o1 = o1
      @o2 = o2
      @n = o1.n - o2.n
    else
      @o1 = o2
      @o2 = o1
      @n = o2.n - o1.n
    end
  end
  
  def to_s
    "(#{@o1} - #{@o2} = #{@n})"
  end
end

# integer division without remainder
class DivisionOperation < Operation
  def initialize(o1, o2)
    if o2.n != 0 && o1.n % o2.n == 0
      @o1 = o1
      @o2 = o2
      @n = o1.n / o2.n
    elsif o1.n != 0 && o2.n % o1.n == 0
      @o1 = o2
      @o2 = o1
      @n = o2.n / o1.n
    else
      @n = nil
    end
  end
  
  def to_s
    "(#{@o1} / #{@o2} = #{@n})"
  end
end

# recursive
def go(target, operations)
  
  operations.each { |o|
    if o.n == target
      puts o
      return true
    end
  }
  
  if operations.count > 1
    i = 0
    while i < operations.count
      j = i + 1
      while j < operations.count
        o1 = operations[i]
        o2 = operations[j]

        new_operations = Array.new(operations)
        new_operations.delete_at(j)
        new_operations.delete_at(i)
        
        if go(target, Array.new(new_operations).unshift(AdditionOperation.new(o1, o2)))
          return true
        elsif go(target, Array.new(new_operations).unshift(MultiplicationOperation.new(o1, o2)))
          return true
        elsif go(target, Array.new(new_operations).unshift(SubstractionOperation.new(o1, o2)))
          return true
        else
          o = DivisionOperation.new(o1, o2)
          if o.n && go(target, Array.new(new_operations).unshift(o))
            return true
          end
        end
        
        j += 1
      end
      i += 1
    end
  end

  return false
end

def run(target, numbers)
  operations = numbers.map { |n| AssignmentOperation.new(n) }
  if not go(target, operations)
    puts "FAILURE"
  end
end

if (ARGV.count == 7)
  run(ARGV[0].to_i, ARGV[1..6].map { |x| x.to_i })
else
  puts "****************"
  puts "countdown solver"
  puts "****************"
  puts ""
  puts "./countdown.rb target n1 n2 n3 n4 n5 n6"
  puts "e.g. ./countdown.rb 729 25 100 1 7 9 5"
end