--Apple-Mail-3-538353748
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
	charset-ASCII;
	format­´wed

(forwarded to Ruby Talk by JEG2)

Begin forwarded message:

> From: Brian Candler <B.Candler / pobox.com>
> Date: November 23, 2004 5:16:20 PM CST
> To: James Edward Gray II <james / grayproductions.net>
> Subject: Re: Ruby quiz suggestion - Countdown
>
> On Tue, Nov 23, 2004 at 08:12:46PM +0000, Brian Candler wrote:
>> 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.
>
> I've not finished yet, but already got it down to 3 seconds :-)
>
> $ time ruby countdown2.rb 926 75  2  8  5  10  10
> Solution: 926(75+(8-5))*(10+2))-10)
>
> real    0m3.117s
> user    0m3.025s
> sys     0m0.008s

--Apple-Mail-3-538353748
Content-Transfer-Encoding: 7bit
Content-Type: application/octet-stream;
	x-unix-mode66;
	name
ountdown2.rb" Content-Disposition: attachment; filenamentdown2.rb #!/usr/local/bin/ruby -w # HOW IT WORKS: # We start with an initial card set # a, b, c, d, e, f # In the first round we generate all the results from combining two cards: # (a+b), c, d, e, f # (a-b), c, d, e, f # (a*b), c, d, e, f # (a/b), c, d, e, f # (a+c), b, d, e, f # (a-c), b, d, e, f # etc. Note that we only need to calculate each pair one way round: addition # and multiplication are commutative, negative numbers are not helpful # (because we can always subtract instead of add), and fractions are # not allowed. So sorting the values lets us always take them in a fixed order. # Now, this by itself works reasonably well, but it generates a lot of # unnecessary duplicate intermediate values. For example, # 78 5+10+8-5+10 # is clearly of no benefit compared to # 78 5+8-5 # And indeed these are duplicates too: # 78 5+8-5 # 78 5-5+8 # But much care is required when trying to trim these. Consider, for # example, that our final solution is (a+b)*(c+d). In the first round, we # will generate subsets including # (a+b), c, d # a, b, (c+d) # In the second round, we must not reject the possibility of calculating # (c+d) for the first set, or (a+b) for the second set, even though those # composite values have been seen before in the first round. # So the rule is (I think): when generating a new subset # (x), (y), (z) # we can eliminate it if in a previous round or earlier in the same round # we have seen # (x), (y), (z) # or (x), (y), (z), other... # i.e. our result is a subset of or identical to a previous result. # And we only need to consider the values (not the formulas, or which # cards they came from) because it's the values which get combined in # subsequent rounds to move towards our target. # The hard part is doing this efficiently. I've done a partial solution # which seems moderately effective: when I generate the set a,b,c,d # then I tag that I've seen [a,b,c,d] and also all combinations with # one removed, i.e. [b,c,d], [a,c,d], [a,b,d], [a,b,c] ########################################################################### # class CNumber contains # - a number # - the formula which produces it class CNumber include Comparable attr_reader :value, :formula def initialize(value, formula{value}") @value alue @formula ormula end def <other) self.value <other.value end def to_s @formula end end class CNumberSet # a collection of CNumbers, which we maintain sorted def initialize(val ]) @numbers al @numbers.sort! end def without(*indices) n numbers.dup indices.each do |i| n[i] il end n.compact! CNumberSet.new(n) end def <<(v) @numbers << v @numbers.sort! end def [](x) @numbers[x] end def size @numbers.size end def each(&blk) @numbers.each(&blk) end def values @numbers.collect { |n| n.value }.sort end end class Countdown def initialize(target, sources) @target arget.to_i @combinations CNumberSet.new( sources.collect { |n| CNumber.new(n.to_i) } )] @nearest, @error Number.new(0,""), @target @combinations[0].each do |c| next if (@target - c.value).abs > error @nearest, @error , (@target - c.value).abs end @seen_sets } valset combinations[0].values @seen_sets[valset] rue valset.each_index do |i| v2 alset.dup.delete_at(i) @seen_sets[v2] rue end @rounds ources.size - 1 end def run catch(:found) do @rounds.times do output ] @combinations.each do |nset| combine(output, nset) end @combinations utput end end return @nearest end def combine(result, nset) (0...nset.size).each do |i| (i+1...nset.size).each do |j| v1 set[i].value v2 set[j].value # Try all operators; we know v2 > 1 add_result(result, v2+v1, :"+", nset, j, i) add_result(result, v2-v1, :"-", nset, j, i) add_result(result, v2*v1, :"*", nset, j, i) add_result(result, v2/v1, :"/", nset, j, i) if v2%v1 0 end end end def add_result(result, r, op, nset, j, i) return if r < 1 # eliminate 3-3 return if r nset[j].value # eliminate 3/10 3*10 4-2 etc. return if r nset[i].value return if r > @target * 10 # heuristic s set.without(i,j) n Number.new(r, "(#{nset[j].formula}#{op}#{nset[i].formula})") s << n # have we already seen this set? valset .values return if @seen_sets[valset] @seen_sets[valset] rue valset.each_index do |i| v2 alset.dup.delete_at(i) @seen_sets[v2] rue end # This is a new solution, keep it result << s return if (@target-r).abs > error @nearest,@error , (@target-r).abs throw :found if @error 0 end end unless ARGV.size > 0 STDERR.puts "Usage: #{$0} target source source source..." exit 1 end target RGV.shift sources RGV solution ountdown.new(target,sources).run puts "Solution: #{solution.value}solution.formula}" --Apple-Mail-3-538353748--