(forwarded to Ruby Talk by JEG2)
From: Brian Candler <B.Candler@pobox.com>
Date: November 23, 2004 2:12:46 PM CST
To: James Edward Gray II <james@grayproductions.net>
Subject: Re: Ruby quiz suggestion - Countdown
[snip old off-list conversation]
countdown.rb (2.28 KB)
···
Begin forwarded message:
I've been away from Ruby-Talk for a few weeks, and forgot that this
competition would come and go! Thanks for your excellent summary as usual. I
purposely kept the language over fractions vague, (a) because I didn't know
the actual TV rules in this case, and (b) because I wasn't sure there would
be any case where you could make use of them - although I see at
RubyTalk:120156 that there is.FWIW, I thought I'd give it a go myself (not having looked at any other
results), and my solution is attached. On my machine it takes <24
CPU-seconds to handle the "hard" example:$ time ruby countdown.rb 926 75 2 8 5 10 10
Solution: 926=(((75+(8-5))*(10+2))-10)real 0m26.208s
user 0m23.273s
sys 0m0.338sThis is an AMD Athlon 2500+ (1.833GHz, 512KB cache), 512MB RAM system.
I cheated a little by assuming the fractions-not-allowed rule
And also
by pruning any intermediate values which exceeded twice the target. I'm not
sure what a "safe" upper bound there is, although changing it to target*10
only makes it run about 3 seconds slower.There are clearly other optimisations possible. One is to reject any
solution for value N using source numbers (a,b,c,d) if we have already seen
a solution for N using only a strict subset of (a,b,c,d). But there's a bit
of work involved there.Cheers,
Brian.