```Hi,

Not a late entry, but a port from Haskell to Ruby

- 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

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

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 new(:op, 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 : :push, 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

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

```