From: daz <dooby@...10.karoo.co.uk>
Date: 2004-11-19T09:58:12+09:00
Subject: Re: [SOLUTION] Countdown (#7) - port from Haskell


Hi,

Not a late entry, but a port from Haskell to Ruby
(read as: derivative work).

- The quiz summary has been posted [talk:120778]

The mediochre speed is probably due to my conversion since
this was a shock introduction to a foreign language.
Dennis Ranke's excellent(!) submission blows this one away
as well.

I'm running a slow P200 with 128Mb memory but Dennis's
script fizzes out solutions in less than 2 seconds that
can take minutes here.

I'd summarize this solver as "Partially-optimised, brute force
method with partial memoisation." ?
(It doesn't repeat evaluation of terms but when showing all
solutions, many appear/are very similar.)

Comments/analysis welcome, but I suspect there isn't much
that hasn't been seen in the other creditable solutions.


daz


  <Quiz-related QUOTE from "AskOxford">

   In March 1997, young James Martin, at the time a Maths Ph.D.
   student at Cambridge University, astounded the Countdown viewers
   by finding the best ever solution to a numbers game.

   The numbers were - 25 50 75 100 3 6 and the target was 952.

   Within the 30-second time limit, James managed to come up with
   this answer:

       100 + 6 = 106
       106 * 3 = 318
       318 * 75 = 23850
       23850 - 50 = 23800
       23800 / 25 = 952.

  </QUOTE>


# Dennis =>  36.97s  (75 * 3 * (100 + 6) - 50) / 25 -> 952
# below  => 602.75s  (75 * 3 * (100 + 6) - 50) / 25 -> 952
#------------------------------------------------------------


# Acknowledgements/apologies to Graham Hutton
# http://www.cs.nott.ac.uk/~gmh/countdown.pdf
#
# daz - 2004/11/16

class Countdown
  OPS = [:+, :-, :*, :/]

  class Term
    # new(Int) or new(:op, Term, Term)
    def initialize(op, x=nil, y=nil)
      if x  # obj is Op
        @op, @x, @y, x, y = op, x, y, x.val, y.val
        # validate / evaluate
        @val =
          case @op
          when :+
            (x < y) ? false : x + y
          when :-
            (x > y) ? x - y : false
          when :*
            ((x == 1) or (y == 1) or (x < y)) ? false : x * y
          when :/
            x1, y1 = x.divmod(y)
            ((y == 1) or (y1 > 0) or (x1 == 0) or (x1 == y)) ? false : x1
          end
      else @val = op  # obj is Int
      end
    end

    attr_reader :val  # true value if valid / false if garbage

    def to_s
      opx = OPS.index(@op); b1, b0 = (opx && opx < 2) ? ['(',')'] : ['','']
      opx ? ('%s%s %c %s%s' % [b1, @x.to_s, '+-*/'[opx], @y.to_s, b0]) : val.to_s
    end
  end

  private

  def Countdown.permute(arr, beg=0)  # recursive
    if beg < arr.size
      ar2 = arr.dup
      for j in beg...ar2.size
        ar2[j], ar2[beg] = ar2[beg], ar2[j]
        permute(ar2, beg+1) { |ary| yield ary }
      end
    else
      yield arr
    end
  end

  def Countdown.results(target, sel)
    if sel.size > 1
      (sel.size-1).times do |n|
        # "non-empty split": ABCD -> [A,BCD],[AB,CD],[ABC,D]
        az = [[], []]; aix = 0
        sel.each_with_index do |elem, eix|
          aix = 1 if eix == (n+1)
          az[aix] << elem
        end
        results(target, az[0]) do |lx|
          results(target, az[1]) do |ry|
            # combine
            OPS.each do |op|
              res = Term.new(op, lx, ry)
              yield res if res.val
            end
          end
        end
      end
    else
      yield sel[0] if sel[0]  # and sel[0].val
    end
  end

  public

  def Countdown.solve(target, sel, all_solutions=nil)
    p [:TARGET, target, sel]
    best = +10;  start = Time.now
    sel.map! {|s| Term.new(s)}

    (2 ** sel.size).times do |n|
      subseq = []
      sel.each_with_index do |elem, eix|
        n[eix] == 1 and subseq << elem
      end
      permute(subseq) do |pp|
        results(target, pp) do |res|
          rv = res.val
          err = (rv - target)
          if err == 0
            best = 0
            ## display solution
            print '* OK => %6.2fs  ' % [Time.now - start]
            print res.to_s, ' -> ', target; puts
            return unless all_solutions
          end
          if err.abs < best
            best = err.abs
            puts 'Best so far: %d (%s%d)' % [rv, (rv > target) ? '+':'', err]
          end
        end
      end
    end
    puts 'END => %6.2fs' % [Time.now - start]
  end
end  # class Countdown


# RUN IT

STDOUT.sync = true

if !ARGV.empty?
  if ARGV[0] == 'cecil'
    large = [25,50,75,100]
    avail = large + (1..10).to_a + (2..10).to_a
    sel = []
    6.times do |i|
      if i == 5 and avail[3] == 100 and rand(3) > 1
        avail = large
      end
      num = avail.delete_at(rand(avail.size))
      sel.send(num > 10 ? :unshift : :push, num)
    end
    target = rand(899) + 101
    Countdown::solve(target, sel, :FIND_ALL)
  else
    target = ARGV[0].to_i
    sel = ARGV[1..-1].map {|s| s.to_i}
    Countdown::solve(target, sel, :FIND_ALL)
  end
else
  Countdown::solve(429, [75, 4, 8, 10, 6, 10])
end

#------------------------------------------------------------