From: "Brian Schröder" <ruby@...>
Date: 2004-11-15T03:25:54+09:00
Subject: Re: [QUIZ] Countdown (#7) [Solution]

Hello Group,

This was quite an interesting quiz. I tried different solutions of varying complexity, but it turned out that the simplest approach worked best.

The problem is exponential in the number of source cards. It is solvable for six cards, but this algorithm is not a general solution for an arbitrary number of cards.

I recursively generate each possible term, and evaluate it. In my recursive generation process, each subterm is generated multiple times, so I used optional memoization to speed up the search. An exhaustive search takes around 300s without and 110s with memoization, but memoization uses a lot of ram.

If you only need one solution, it is usually found within 20s.

The full programm with commandline parsing and different implementations - Integer-Only vs. Float
- Brute Force vs. Memoization

can be found at:

http://ruby.brian-schroeder.de/quiz/

There is also a only version, that solves a random problem.

Following are the main routines of the program:

The Term structure is a direct implementation of the term-tree:

# Node of a Term Tree.
class Term
  attr_reader :left, :right, :operation
  
  def initialize(left, right, operation)
    @left = left
    @right = right
    @operation = operation
  end

  def to_s
    "(#{@left} #{operation} #{@right})"
  end

  def value
    @value || (@value = (@left.value).send(@operation, (@right.value)))
  end

  def ==(o)
    return false unless o.is_a?Term
    to_s == o.to_s
  end
end

The methods I use to create all the terms are:

Brute Force:
 def Integral.each_term_over(source)
      if source.length == 1
        yield source[0]
      else
        source.each_partition do | p1, p2 |
          each_term_over(p1) do | op1 |
            yield op1
            each_term_over(p2) do | op2 |
              yield op2
              if op2.value != 0
                yield Term.new(op1, op2, :+) 
                yield Term.new(op1, op2, :-)
                yield Term.new(op1, op2, :'/') if op2.value != 1 and op1.value % op2.value == 0
              end
              if op1.value != 0
                yield Term.new(op2, op1, :-)
                if op1.value != 1
                  yield Term.new(op2, op1, :'/') if op2.value % op1.value == 0
                  yield Term.new(op1, op2, :*) if op2.value != 0 and op2.value != 1
                end
              end
            end
          end
        end
      end
  end

With Memoization:

    def Integral.each_term_over(source, memo = {}, &block)
      return memo[source] if memo[source]

      result = []
      if source.length == 1
        result << source[0]
      else
        source.each_partition do | p1, p2 |
          each_term_over(p1, memo, &block).each do | op1 |
            each_term_over(p2, memo, &block).each do | op2 |
              if op2.value != 0
                result << Term.new(op1, op2, :+) 
                result << Term.new(op1, op2, :-)
                result << Term.new(op1, op2, :'/') if op2.value != 1 and op1.value % op2.value == 0
              end
              if op1.value != 0
                result << Term.new(op2, op1, :-)
                if op1.value != 1
                  result << Term.new(op2, op1, :'/') if op2.value % op1.value == 0
                  result << Term.new(op1, op2, :*) if op2.value != 0 and op2.value != 1
                end
              end
            end
          end
        end
      end

      result.each do | term | block.call(term) end
      memo[source] = result
    end


# Extending Array with simple set functions
class Array
  # Returns each true partition (containing no empty set) exactly once.
  def each_partition
    return nil if empty?
    head, *tail = *self
    tail._each_partition do | subset, rest |
      yield [subset.unshift(head), rest] unless rest.empty?
    end
  end

  protected
  # Returns each partition twice, as (s1, s2) and (s2, s1)
  def _each_partition
    if empty?
      yield([], [])
      return nil
    end
    head, *tail = *self
    tail._each_partition do | s1, s2 |
      yield([head] + s1, s2) 
      yield(s1, [head] + s2)
    end
  end
end

-- 
Brian Schr�der
http://www.brian-schroeder.de/