D

#### Dennis Ranke

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