```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

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?
tail._each_partition do | subset, rest |
end
end

protected
# Returns each partition twice, as (s1, s2) and (s2, s1)
def _each_partition
if empty?
yield([], [])
return nil
end