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

--Apple-Mail-3-538353748
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 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-mode=0666;
	name="countdown2.rb"
Content-Disposition: attachment;
	filename=countdown2.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 = 75+10+8-5+10
# is clearly of no benefit compared to
#     78 = 75+8-5
# And indeed these are duplicates too:
#     78 = 75+8-5
#     78 = 75-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 = value
    @formula = formula
  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 = 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
  def each(&blk)
    @numbers.each(&blk)
  end
  def values
    @numbers.collect { |n| n.value }.sort
  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
    @combinations[0].each do |c|
      next if (@target - c.value).abs >= @error
      @nearest, @error = c, (@target - c.value).abs
    end
    @seen_sets = { }
    valset = @combinations[0].values
    @seen_sets[valset] = true
    valset.each_index do |i|
      v2 = valset.dup.delete_at(i)
      @seen_sets[v2] = true
    end
    @rounds = sources.size - 1
  end
  def run
    catch(:found) do
      @rounds.times do
        output = []
        @combinations.each do |nset|
          combine(output, nset)
        end
        @combinations = output
      end
    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              # eliminate 3-3=0
    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 * 10   # heuristic

    s = nset.without(i,j)
    n = CNumber.new(r, "(#{nset[j].formula}#{op}#{nset[i].formula})")
    s << n

    # have we already seen this set?
    valset = s.values
    return if @seen_sets[valset]
    @seen_sets[valset] = true
    valset.each_index do |i|
      v2 = valset.dup.delete_at(i)
      @seen_sets[v2] = true
    end

    # This is a new solution, keep it
    result << s
    return if (@target-r).abs >= @error
    @nearest,@error = n, (@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 = ARGV.shift
sources = ARGV
solution = Countdown.new(target,sources).run
puts "Solution: #{solution.value}=#{solution.formula}"

--Apple-Mail-3-538353748--