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
&&