From: Dennis Ranke <dennis.ranke@...>
Date: 2004-11-15T08:48:24+09:00
Subject: Re: [SOLUTION] Countdown (#7)

Here is a small update to my solution. A simple optimization speeds up 
the solver by a factor of nearly two. Now I'm down to 5 seconds for the 
worst case on this machine :)

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
     collision = 0
     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'
         index = 1
         term_mask = term.mask

         # skip over indeces that clash with term_mask
         index += collision - ((collision - 1) & index) while
                     (collision = term_mask & index) != 0
         while index < 64
           hash = @term_hashes[index]

           # iterate through the hashes and build composite terms using
           # the four basic operators
           hash.each_value do |other|
             new_mask = term_mask | other.mask
             hash = @term_hashes[new_mask]
             new_hash = new_hashes[new_mask]
             [:+, :-, :*, :/].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
               next if hash.has_key?(value) || new_hash.has_key?(value)

               new_term = Term.new(value, new_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_hash[value] = new_term
             end
           end
           index += 1
           index += collision - ((collision - 1) & index) while
                       (collision = term_mask & index) != 0
         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