From: James Edward Gray II <james@...>
Date: 2004-11-24T05:49:42+09:00
Subject: Fwd: Ruby quiz suggestion - Countdown

--Apple-Mail-2-529212249
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
	charset=US-ASCII;
	format=flowed

(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.

--Apple-Mail-2-529212249
Content-Transfer-Encoding: 7bit
Content-Type: application/octet-stream;
	x-unix-mode=0666;
	name="countdown.rb"
Content-Disposition: attachment;
	filename=countdown.rb

#!/usr/local/bin/ruby -w

class CNumber     # a number together with the formula which produces it
  include Comparable
  attr_reader :value, :formula
  def initialize(value, formula="#{value}")
    @value = value
    @formula = formula
  end
  def <=>(other)
    self.value <=> other.value
  end
end

class CNumberSet  # a collection of numbers, which we maintain sorted
  def initialize(val = [])
    @numbers = val
    @numbers.sort!
  end
  def without(*indices)
    n = @numbers.dup
    indices.each do |i|
      n[i] = nil
    end
    n.compact!
    CNumberSet.new(n)
  end
  def <<(v)
    @numbers << v
    @numbers.sort!
  end
  def [](x)
    @numbers[x]
  end
  def size
    @numbers.size
  end
end

class Countdown
  def initialize(target, sources)
    @target = target.to_i
    @combinations = [ CNumberSet.new(
      sources.collect { |n| CNumber.new(n.to_i) }
    )]
    @nearest, @error = CNumber.new(0,""), @target
    @rounds = sources.size - 1
    @found = false
  end
  def run
    @rounds.times do
      output = []
      @combinations.each do |nset|
        combine(output, nset)
        return @nearest if @error == 0    # found a solution?
      end
      @combinations = output
    end
    return @nearest
  end
  def combine(result, nset)
    (0...nset.size).each do |i|
      (i+1...nset.size).each do |j|
        v1 = nset[i].value
        v2 = nset[j].value
        # Try all operators; we know v2 >= v1
        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
    return if r == nset[j].value # eliminate 3/1=3, 3*1=3, 4-2=2 etc.
    return if r == nset[i].value
    return if r > @target * 2    # heuristic
    s = nset.without(i,j)
    n = CNumber.new(r, "(#{nset[j].formula}#{op}#{nset[i].formula})")
    s << n
    result << s
    return if (@target-r).abs >= @error
    @nearest,@error = n, (@target-r).abs
  end
end

unless ARGV.size > 0
  STDERR.puts "Usage: #{$0} target source source source..."
  exit 1
end
target = ARGV.shift
sources = ARGV
solution = Countdown.new(target,sources).run
puts "Solution: #{solution.value}=#{solution.formula}"

--Apple-Mail-2-529212249--