[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

[SOLUTION] Countdown (#7

Dennis Ranke

11/14/2004 2:37:00 PM

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
14 Answers

Dennis Ranke

11/14/2004 2:42:00 PM

0

For those interested here is my first solution (you know, the one taking
up to an hour ;)
It generates the expressions as trees and iterates through all possible
trees using recursion. Every tree is then evaluated and the result
compared to the target.

class Solver
class Node
def initialize(parent, depth)
@value = nil
@parent = parent
@right_filled = false
if depth > 1
@left = Node.new(self, depth - 1)
@right = Node.new(self, depth - 1)
end
end

def down(values, num_open)
# first try single values
used = []
touse = values.dup
@value = nil
until touse.empty?
used << @value if @value
@value = touse.shift
@parent.up(used + touse, num_open)
end

# now try subexpression if enough values left
return if values.size < num_open + 2
@value = nil
[:+, :-, :*, :/].each do |@op|
@left.down(values, num_open + 1)
end
end

def up(values, num_open)
if @right_filled
@parent.up(values, num_open)
return
end

@right_filled = true
@right.down(values, num_open - 1)
@right_filled = false
end

def evaluate
return @value.to_f if @value
@left.evaluate.send(@op, @right.evaluate)
end

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

def initialize(sources, target)
@tree = Node.new(self, sources.size)
@target = target
@sources = sources
@best_result = (target * 1000).abs
end

def run
@tree.down(@sources, 0)
end

def up(values, num_open)
# return unless values.empty? # only allow solutions using all values
result = @tree.evaluate
return if result.nan? || @best_result <= (@target - result).abs
@best_result = (@target - result).abs
printf "%s = %f\n", @tree, result
exit if @best_result == 0
end
end

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

solver = Solver.new(ARGV[1..-1].map {|v| v.to_i}, ARGV[0].to_i)
solver.run

Hans Fugal

11/14/2004 4:22:00 PM

0

I didn't actually implement it, but my approach was going to be the
following.

The problem is basically a search through the (large) space of possible
expressions. I figured brute force would take a long time, and others
have proven that hypothesis correct.

I at first was going to use an A* search, but I realized that A* would
try to optimize the path length which (the way I was planning on
implementing it) would mean it would strive for the shortest correct
solution. The length of the solution didn't matter, though, all that
mattered was that a correct answer was found. So I decided a greedy
search would be better.

If people can do this in 30 seconds, they either know a trick I don't
know, or they are probably doing a sort of greedy search. Pick the
number/operation that gets you closer than the others, and if that
doesn't get you there fish around in the vicinity. So I think greedy
would work pretty well.

The trick of course is when an exact answer is not available. You would
have to exhaust the search space, and that takes a long time no matter
the algorithm. It would be natural to impose the time limit and
empirically strive for an algorithm that more often than not finds a
close answer within that time limit.

The reason I didn't finish the implementation is that I couldn't quite
decide how to build the state space tree in the time I had. I'm
interested in how others did this.

Dennis Ranke

11/14/2004 11:47:00 PM

0

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

David G. Andersen

11/15/2004 2:42:00 AM

0

On Mon, Nov 15, 2004 at 01:23:26AM +0900, Hans Fugal scribed:
>
> If people can do this in 30 seconds, they either know a trick I don't
> know, or they are probably doing a sort of greedy search. Pick the
> number/operation that gets you closer than the others, and if that
> doesn't get you there fish around in the vicinity. So I think greedy
> would work pretty well.

The trick is being clever about the combinations you try.
You don't need to do things like 1/1, or any changes that
produce the same number (4/2, for example, since it consumes a 4 and
a 2 and only produces a 2). Also, only some of the operations don't
commute -- so you need to try a + b, but not b + a. Since fractions
aren't allowed, you only need to do one division. Etc.

If you really want to speed it up, you can memoize it to avoid
searching the same sub-parts of the solution space over and over.
It consumes a bit of memory - I use a stupid memoization scheme
that represents the state as a string of numbers separated by
dashes that consumes about 10 megs - but it works pretty well.

-Dave

Brian Schröder

11/15/2004 9:44:00 AM

0

On Mon, 15 Nov 2004 08:48:24 +0900
Dennis Ranke <dennis.ranke@epost.de> wrote:

> 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 :)
>
> [snip]

Interesting read. I never thought about building the terms bottom up instead of top down ;). I was in such a recursive mindset. I hope your ideas don't force me to rethink my solutions and spend even more time that I don't have ;).

One thing I noticed is, that you used:

> best_difference = (@target * 1000).abs

this shurely works but is cheating. Why not use:

> best_difference = 1.0/0.0

That would really be bigger than any other difference you'd encounter.

It is not possible to find all solutions, using your programm, did I understand this right?

Best Regards,

Brian


--
Brian Schröder
http://www.brian-sch...

Dennis Ranke

11/15/2004 11:00:00 AM

0

Brian Schröder wrote:
> On Mon, 15 Nov 2004 08:48:24 +0900
> Dennis Ranke <dennis.ranke@epost.de> wrote:
>
>
>>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 :)
>>
>>[snip]
>
>
> Interesting read. I never thought about building the terms bottom up
> instead of top down ;). I was in such a recursive mindset.

It seems to me that this weeks quiz received the largest amount of
really unique approaches of all the quizzes, yet. That's what makes it
this interesting. :)

> I hope your ideas don't force me to rethink my solutions and spend
> even more time that I don't have ;).

Oh yes, it's hard to lay down this quiz. ;)

> One thing I noticed is, that you used:
>
>
>> best_difference = (@target * 1000).abs
>
>
> this shurely works but is cheating. Why not use:
>
>
>> best_difference = 1.0/0.0
>
>
> That would really be bigger than any other difference you'd encounter.

True, good idea.

> It is not possible to find all solutions, using your programm, did I understand this right?

This is correct, it will only find one solution in it's current
incarnation, as it just throws away a new term if it has already found
another term with the same value using the same input numbers. However,
it would be easily possible to remeber those terms instead (say, the
first term found holds a list of duplicates) and then iterate through
all the possible solutions in the end. This shouldn't slow down the
calculations a lot (the main factor would be the creation of a lot more
Term instances), but it would take a lot more memory.

Hans Fugal

11/15/2004 2:39:00 PM

0

David G. Andersen wrote:
> On Mon, Nov 15, 2004 at 01:23:26AM +0900, Hans Fugal scribed:
>
>>If people can do this in 30 seconds, they either know a trick I don't
>>know, or they are probably doing a sort of greedy search. Pick the
>>number/operation that gets you closer than the others, and if that
>>doesn't get you there fish around in the vicinity. So I think greedy
>>would work pretty well.

Hmm, I just realized that may not have come across how I wanted. What I
meant was, if human beings on a game show can do it in 30 seconds...

> The trick is being clever about the combinations you try.
> You don't need to do things like 1/1, or any changes that
> produce the same number (4/2, for example, since it consumes a 4 and
> a 2 and only produces a 2). Also, only some of the operations don't
> commute -- so you need to try a + b, but not b + a. Since fractions
> aren't allowed, you only need to do one division. Etc.

Yeah, it was a combination of special cases I knew would help and the
details of spawning expressions methodically that I didn't get
straightened out in my head in the time I had. For example, adding a
term and operator each time would search through (a+b)+c but not
(a+b)+(c+d). I think the bottom-up approach is perhaps what I was
searching for.

> If you really want to speed it up, you can memoize it to avoid
> searching the same sub-parts of the solution space over and over.
> It consumes a bit of memory - I use a stupid memoization scheme
> that represents the state as a string of numbers separated by
> dashes that consumes about 10 megs - but it works pretty well.
>
> -Dave
>
>

David G. Andersen

11/15/2004 7:45:00 PM

0

On Mon, Nov 15, 2004 at 08:48:24AM +0900, Dennis Ranke scribed:
> 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 :)

Thanks for the inspiration to improve my code a little more. :-)
This version uses a search trie to perform duplicate elimination,
and steals Dennis's point about not needing to worry about negative
numbers (since there's also a "minus" operator.. can't believe I forgot
that the first time). The code is a little cleaner, and the memory
utilization is down to about 2.5 megabytes for the memoized version,
since it now knows that if you test "25 5 3" you don't need to test "25 5"
or "25".

the search trie addition is kind of cute. It's a nice demonstration
of how easy it can be to implement some cool data structures in Ruby. :)

Runtime is about 2.7 seconds using -m for an unsolvable case,
and 2 seconds for the "hard" solvable case of 926 75 2 8 5 10 10 that
someone posted earlier. Without -m, it takes about 12 seconds / 5
seconds, respectively, but there's no reason not to use memoization since
it consumes so little memory now.

#!/usr/local/bin/ruby

# The exit from the processing loop is a little ugly. Would be
# better to cascade the return values, but that required more
# tests. ;-)
#
# Use with "-m" to memoize parts of the solution space and avoid
# duplicate configurations. Requires about 14 megs of ram; runs
# about 10x faster.

raise "usage: quiz.rb [-m] [target] [source1] [source2] ...\n" if ARGV.length < 2

$lots_of_memory = ARGV.delete("-m")
target, *source = ARGV.map { |a| a.to_i }

class TreeMap
# Quick and dirty search trie for duplicate detection / elimination
def initialize()
@root = Hash.new
end

def test_and_add(arr)
cur = @root
found = true
arrs = arr.sort
while (head = arrs.pop)
found = false unless cur.has_key?(head)
cur = cur[head] ||= Hash.new
end
return found
end
end

$tm = TreeMap.new if $lots_of_memory
$closest_diff = target
$closest_stack = nil
$itercount = 0

def fs(stack, target, source)
$itercount += 1
recent = source[-1]
raise "#{stack[-1]}" if (recent == target)
return false if ($lots_of_memory && $tm.test_and_add(source))
if (recent - target).abs < $closest_diff
$closest_diff = (recent - target).abs
$closest_stack = stack[-1]
end
return false if (source.length == 1)
i = j = ns = nt = ival = istack = jval = jstack = myid = 0
observed = Hash.new
(0...source.length).each do |i|
(i+1...source.length).each do |j|
ns = source[0...i] + source[i+1...j] + source[j+1..-1]
nt = stack[0...i] + stack[i+1...j] + stack[j+1..-1]
i, j = j, i if (source[i] < source[j])
ival, istack = source[i], stack[i]
jval, jstack = source[j], stack[j]
# Linear space duplicate suppression is cheap; use always
myid = "#{ival}-#{jval}"
next if (observed.has_key?(myid))
observed[myid] = true
fs(nt + ["(#{istack} + #{jstack})"], target, ns + [ival + jval])
fs(nt + ["(#{istack} - #{jstack})"], target, ns + [ival - jval]) unless ival==jval
if (jval > 1)
if (ival != jval && 0 == (ival % jval))
fs(nt + ["(#{istack} / #{jstack})"], target, ns + [ival / jval])
end
fs(nt + ["(#{istack} * #{jstack})"], target, ns + [ival * jval])
end
end
end
end

begin
raise "Source contains target." if source.include? target
fs(source.dup, target, source)
p $closest_stack
rescue => err
print "Done: #{err}\n"
ensure
print "Itercount: #{$itercount}\n"
end

Dennis Ranke

11/16/2004 12:03:00 AM

0

David G. Andersen wrote:
> Thanks for the inspiration to improve my code a little more. :-)
> [...]

This improved solution is nicely fast. However I have found one example
where it doesn't find the closest solution:
(The code is as posted, I have only modified it to print out the time
taken (in seconds).)

Dennis-Rankes-Computer:~/Desktop exo$ ./countdown2.rb -m 93475 3 7 17 29
51 71
"(((71 * 51) - (17 + 7)) * (29 - 3))"
Itercount: 16504
2.082612
Dennis-Rankes-Computer:~/Desktop exo$ irb
irb(main):001:0> (((71*51)-(17+7))*(29-3))
=> 93522
irb(main):002:0> (((17*71)+7)*((29-3)+51))
=> 93478

The lower solution has been found by my code.

Dennis Ranke

11/16/2004 12:33:00 PM

0

I have just found a bug in both versions of my fast solution. They are
unable to find (for example) the solution 25-(2*3) = 19:

Dennis-Rankes-Computer:~/coding/ruby-quiz exo$ ruby 07-countdown2.rb 19
25 2 3
[25, 2, 3] -> 19
(25 + 2) = 27 (error: 8)
(25 - 2) = 23 (error: 4)
(25 - 3) = 22 (error: 3)
((25 - 2) - 3) = 20 (error: 1)
0.016051 seconds

In addition, the optimized version had a bug that only let it cope with
exactly 6 input numbers.

I have fixed both, which slows down the solution a slight bit (it takes
about 7% longer to go through all combinations):

Dennis-Rankes-Computer:~/coding/ruby-quiz exo$ ruby 07-countdown4.rb 19
25 2 3[25, 2, 3] -> 19
(25 + 2) = 27 (error: 8)
(25 - 2) = 23 (error: 4)
(25 - 3) = 22 (error: 3)
((25 - 2) - 3) = 20 (error: 1)
(25 - (3 * 2)) = 19 (error: 0)
0.016437 seconds

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
@num_hashes = 1 << @num_sources

# 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(@num_hashes) { {} }

# 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 = 1.0/0.0
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(@num_hashes) { {} }

# 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 < @num_hashes
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]

# sort the source terms so that the term with the larger
# value is left
# (we don't allow fractions and negative subterms are not
# necessairy as long as the target is positive)
if term.value > other.value
left_term = term
right_term = other
else
left_term = other
right_term = term
end
[:+, :-, :*, :/].each do |op|

# don't allow fractions
next if op == :/ &&
left_term.value % right_term.value != 0

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

# don't allow zero
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, left_term,
right_term)

# 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