From: Dennis Ranke <dennis.ranke@...>
Date: 2004-11-14T23:38:23+09:00
Subject: [SOLUTION] Countdown (#7)

Hi, here is my second solution for this very interesting quiz.

My first solution took an estimated one hour in the worst case (when no 
exact solution exists), this one is A LOT faster. The actual time 
depends a bit on the input values, but I have never seen it take more 
than 8 seconds.

This solution works by combining two sub terms at a time into new 
composite terms until either a term with the target value is found or 
all combinations have been generated.
The most important optimization was to ignore a new term if another term 
of the same value using the same input numbers has already been found. 
To further improve the speed I also decided not to allow terms giving 
fractions, zero or negative values.

So here it is:

class Solver
   class Term
     attr_reader :value, :mask

     def initialize(value, mask, op = nil, left = nil, right = nil)
       @value = value
       @mask = mask
       @op = op
       @left = left
       @right = right
     end

     def to_s
       return @value.to_s unless @op
       "(#@left #@op #@right)"
     end
   end

   def initialize(sources, target)
     printf "%s -> %d\n", sources.inspect, target
     @target = target
     @new_terms = []
     @num_sources = sources.size

     # the hashes are used to check for duplicate terms
     # (terms that have the same value and use the same
     # source numbers)
     @term_hashes = Array.new(1 << @num_sources) { {} }

     # enter the source numbers as (simple) terms
     sources.each_with_index do |value, index|

       # each source number is represented by one bit in the bit mask
       mask = 1 << index
       term = Term.new(value, mask)
       @new_terms << term
       @term_hashes[mask][value] = term
     end
   end

   def run
     best_difference = (@target * 1000).abs
     next_new_terms = [nil]
     until next_new_terms.empty?
       next_new_terms = []

       # temporary hashes for terms found in this iteration
       # (again to check for duplicates)
       new_hashes = Array.new(1 << @num_sources) { {} }

       # iterate through all the new terms (those that weren't yet used
       # to generate composite terms)
       @new_terms.each do |term|

         # iterate through the hashes and find those containing terms
         # that share no source numbers with 'term'
         @term_hashes.each_with_index do |hash, index|
           next if term.mask & index != 0

           # iterate through the hashes and build composite terms using
           # the four basic operators
           hash.each_value do |other|
             [:+, :-, :*, :/].each do |op|

               # don't allow fractions
               # if you want to allow fractions remove this line and
               # make sure that the source numbers are floats (or
               # include rational.rb)
               next if op == :/ && term.value % other.value != 0

               # calculate value of composite term
               value = term.value.send(op, other.value)

               # don't allow negative values or zero
               # (negative subterms are not necessairy as long as the
               # target is positive)
               next if value <= 0

               # ignore this composite term if this value was already
               # found for a different term using the same source
               # numbers
               mask = term.mask | other.mask
               next if @term_hashes[mask].has_key?(value) ||
                 new_hashes[mask].has_key?(value)

               new_term = Term.new(value, mask, op, term, other)

               # if the new term is closer to the target than the
               # best match so far print it out
               if (value - @target).abs < best_difference
                 best_difference = (value - @target).abs
                 printf "%s = %d (error: %d)\n", new_term, value,
                                     best_difference
                 return if best_difference == 0
               end

               # remember the new term for use in the next iteration
               next_new_terms << new_term
               new_hashes[mask][value] = new_term
             end
           end
         end
       end

       # merge the hashes with the new terms into the main hashes
       @term_hashes.each_with_index do |hash, index|
         hash.merge!(new_hashes[index])
       end

       # the newly found terms will be used in the next iteration
       @new_terms = next_new_terms
     end
   end
end

if ARGV[0] && ARGV[0].downcase == 'random'
   ARGV[0] = rand(900) + 100
   ARGV[1] = (rand(4) + 1) * 25
   5.times {|i| ARGV[i + 2] = rand(10) + 1}
end

if ARGV.size < 3
   puts "Usage: ruby countdown.rb <target> <source1> <source2> ..."
   puts "   or: ruby countdown.rb random"
   exit
end

start_time = Time.now
Solver.new(ARGV[1..-1].map {|v| v.to_i}, ARGV[0].to_i).run
printf "%f seconds\n", Time.now - start_time