[Tutor] making math problems mmmm fun

[John Fouhy]

On 11/09/2007, max baseman <dos.fool at gmail.com> wrote:
> basically the problem is to find a bunch of ways to put 1,2,3,4,5
> into different math problems to that equal 1-25, i haven't spent to
> much time thinking about how to do this but i cant think of a way to
> do it it without writing making the program rather long here is the
> page from the book for the rules i will be working on this for the
> next week or so thanks for any help :)

I've seen this kind of problem before.. though not usually with quite
as much freedom as this one :-)  You could brute force it, by trying
all possible combinations of numbers and operators.  The only problem
is that the freedom they give you means you get horrible combinatorial
explosion.

I'll give you my attempt at brute-force code.  Basically, my thought
process was:
   1. Solve the problem for N digits by solving it for N-1 digits,
then combining those solutions with the last remaining digit.

   2. Because of non-commutivity and non-associativity, we need to
pick do this for each possible digit we could remove, and for both
directions.

   3. If I stick to binary operators, I guarantee that the number of
digits always reduces.  So I will forget about factorial and square
root for now.

Anyway, here's my code.  I'm happy to answer questions about it if you
like.  I guess I could be doing your homework for you, but only if
you've got access to some pretty staunch hardware -- it's pretty
snappy on [1, 2, 3], but if I try it on [1, 2, 3, 4] on my machine,
python gets up to about 1.3GB memory usage before crashing with a
MemoryError :-)

#######
import operator

binops = { 'add':operator.add,
           'sub':operator.sub,
           'mul':operator.mul,
           'div':operator.truediv,
           'pow':operator.pow,
           'join':lambda x, y: int(str(x)+str(y))
           }

patterns = { 'add':'(%s) + (%s)',
             'sub':'(%s) - (%s)',
             'mul':'(%s) * (%s)',
             'div':'(%s) / (%s)',
             'pow':'(%s)^(%s)',
             'join':'%s%s'
             }

def combine(digits):
    """ digits :: set(int)

    output :: [ (value, expression) ]
      value :: int
      expression :: str -- string representation of math expression
    """

    # We're going to solve this instance in terms of the solution
    # for a list with one fewer digit.

    # Because of non-commutativity, we have to do this twice for each
    # possible start digit.

    res = []

    # Base case.
    if len(digits) == 1:
        return [(digit, str(digit)) for digit in digits]

    # Otherwise..
    for digit in digits:
        remainder = digits - set([digit])

        for val, exp in combine(remainder):
            for binop in binops:
                if binop == 'join':
                    # Ensure we only join numbers, not expressions.
                    try:
                        int(exp)
                    except ValueError:
                        continue

                try:
                    newval1 = binops[binop](digit, val)
                    pattern1 = patterns[binop] % (str(digit), exp)
                    res.append((newval1, pattern1))
                except ZeroDivisionError:
                    pass

                try:
                    newval2 = binops[binop](val, digit)
                    pattern2 = patterns[binop] % (exp, str(digit))
                    res.append((newval2, pattern2))
                except ZeroDivisionError:
                    pass

    return res

if __name__ == '__main__':
    res = combine(set(range(1, 4)))