James Gray
11/23/2004 8:50:00 PM
(forwarded to Ruby Talk by JEG2)
Begin forwarded message:
> 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]
> 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.338s
>
> This 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.