[SOLUTION] Countdown (#7)

[Dennis Ranke]

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

 

[Dennis Ranke]

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

 

[Dennis Ranke]

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]

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]

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

 

[Dennis Ranke]

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:




this shurely works but is cheating. Why not use:




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.

 

[David G. Andersen]

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 < source[j])
ival, istack = source, stack
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]

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]

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

 

[Dennis Ranke]

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:

I have now looked closer at this issue and have identified two bugs in
your code.

The first (and fairly trivial one) is that you don't allow divisions
that yield 1 as their result. So your code can't solve
Target = 99, Sources = 100, 5, 5
for example. (Should be 100 - (5 / 5))

The second one is the one that allows your solution to finish this
fast.. In your fs function you have two loops using the variables i
and j. Inside the inner loop you sort i and j by source and
source[j]. Then in the next iteration of the inner loop you are still
using the changed i, which is of course wrong. This can be resolved by
using a copy of i in the inner loop.

Regards, Dennis

 

[David G. Andersen]

The second one is the one that allows your solution to finish this
fast.. In your fs function you have two loops using the variables i
and j. Inside the inner loop you sort i and j by source and
source[j]. Then in the next iteration of the inner loop you are still
using the changed i, which is of course wrong. This can be resolved by
using a copy of i in the inner loop.

Thanks - I corrected them yesterday bu got distracted trying
to gain back the lost speed. I'll poke at it a bit more in my
spare time. When I find some spare time, that is. Eek.

-dave

 

[daz]

Hi,

Not a late entry, but a port from Haskell to Ruby
(read as: derivative work).

- The quiz summary has been posted [talk:120778]

The mediochre speed is probably due to my conversion since
this was a shock introduction to a foreign language.
Dennis Ranke's excellent(!) submission blows this one away
as well.

I'm running a slow P200 with 128Mb memory but Dennis's
script fizzes out solutions in less than 2 seconds that
can take minutes here.

I'd summarize this solver as "Partially-optimised, brute force
method with partial memoisation." ?
(It doesn't repeat evaluation of terms but when showing all
solutions, many appear/are very similar.)

Comments/analysis welcome, but I suspect there isn't much
that hasn't been seen in the other creditable solutions.


daz


<Quiz-related QUOTE from "AskOxford">

In March 1997, young James Martin, at the time a Maths Ph.D.
student at Cambridge University, astounded the Countdown viewers
by finding the best ever solution to a numbers game.

The numbers were - 25 50 75 100 3 6 and the target was 952.

Within the 30-second time limit, James managed to come up with
this answer:

100 + 6 = 106
106 * 3 = 318
318 * 75 = 23850
23850 - 50 = 23800
23800 / 25 = 952.

</QUOTE>


# Dennis => 36.97s (75 * 3 * (100 + 6) - 50) / 25 -> 952
# below => 602.75s (75 * 3 * (100 + 6) - 50) / 25 -> 952
#------------------------------------------------------------


# Acknowledgements/apologies to Graham Hutton
# http://www.cs.nott.ac.uk/~gmh/countdown.pdf
#
# daz - 2004/11/16

class Countdown
OPS = [:+, :-, :*, :/]

class Term
# new(Int) or newop, Term, Term)
def initialize(op, x=nil, y=nil)
if x # obj is Op
@op, @x, @y, x, y = op, x, y, x.val, y.val
# validate / evaluate
@Val =
case @op
when :+
(x < y) ? false : x + y
when :-
(x > y) ? x - y : false
when :*
((x == 1) or (y == 1) or (x < y)) ? false : x * y
when :/
x1, y1 = x.divmod(y)
((y == 1) or (y1 > 0) or (x1 == 0) or (x1 == y)) ? false : x1
end
else @Val = op # obj is Int
end
end

attr_reader :val # true value if valid / false if garbage

def to_s
opx = OPS.index(@op); b1, b0 = (opx && opx < 2) ? ['(',')'] : ['','']
opx ? ('%s%s %c %s%s' % [b1, @x.to_s, '+-*/'[opx], @y.to_s, b0]) : val.to_s
end
end

private

def Countdown.permute(arr, beg=0) # recursive
if beg < arr.size
ar2 = arr.dup
for j in beg...ar2.size
ar2[j], ar2[beg] = ar2[beg], ar2[j]
permute(ar2, beg+1) { |ary| yield ary }
end
else
yield arr
end
end

def Countdown.results(target, sel)
if sel.size > 1
(sel.size-1).times do |n|
# "non-empty split": ABCD -> [A,BCD],[AB,CD],[ABC,D]
az = [[], []]; aix = 0
sel.each_with_index do |elem, eix|
aix = 1 if eix == (n+1)
az[aix] << elem
end
results(target, az[0]) do |lx|
results(target, az[1]) do |ry|
# combine
OPS.each do |op|
res = Term.new(op, lx, ry)
yield res if res.val
end
end
end
end
else
yield sel[0] if sel[0] # and sel[0].val
end
end

public

def Countdown.solve(target, sel, all_solutions=nil)
p [:TARGET, target, sel]
best = +10; start = Time.now
sel.map! {|s| Term.new(s)}

(2 ** sel.size).times do |n|
subseq = []
sel.each_with_index do |elem, eix|
n[eix] == 1 and subseq << elem
end
permute(subseq) do |pp|
results(target, pp) do |res|
rv = res.val
err = (rv - target)
if err == 0
best = 0
## display solution
print '* OK => %6.2fs ' % [Time.now - start]
print res.to_s, ' -> ', target; puts
return unless all_solutions
end
if err.abs < best
best = err.abs
puts 'Best so far: %d (%s%d)' % [rv, (rv > target) ? '+':'', err]
end
end
end
end
puts 'END => %6.2fs' % [Time.now - start]
end
end # class Countdown


# RUN IT

STDOUT.sync = true

if !ARGV.empty?
if ARGV[0] == 'cecil'
large = [25,50,75,100]
avail = large + (1..10).to_a + (2..10).to_a
sel = []
6.times do |i|
if i == 5 and avail[3] == 100 and rand(3) > 1
avail = large
end
num = avail.delete_at(rand(avail.size))
sel.send(num > 10 ? :unshift : ush, num)
end
target = rand(899) + 101
Countdown::solve(target, sel, :FIND_ALL)
else
target = ARGV[0].to_i
sel = ARGV[1..-1].map {|s| s.to_i}
Countdown::solve(target, sel, :FIND_ALL)
end
else
Countdown::solve(429, [75, 4, 8, 10, 6, 10])
end

#------------------------------------------------------------

 

[James Edward Gray II]

Hi,

Not a late entry, but a port from Haskell to Ruby
(read as: derivative work).

- The quiz summary has been posted [talk:120778]

The mediochre speed is probably due to my conversion since
this was a shock introduction to a foreign language.

Which language are you new to? Ruby?

If so, welcome.

Nice submission, by the way.

James Edward Gray II