code challenge: generate minimal expressions using only digits 1,2,3

[MRAB]

Trip Technician wrote:
> anyone interested in looking at the following problem.
> 
> we are trying to express numbers as minimal expressions using only the
> digits one two and three, with conventional arithmetic. so for
> instance
> 
> 33 = 2^(3+2)+1 = 3^3+(3*2)
> 
> are both minimal, using 4 digits but
> 
> 33 = ((3+2)*2+1)*3
> 
> using 5 is not.
> 
> I have tried coding a function to return the minimal representation
> for any integer, but haven't cracked it so far. The naive first
> attempt is to generate lots of random strings, eval() them and sort by
> size and value. this is inelegant and slow.
> 
> I have a dim intuition that it could be done with a very clever bit of
> recursion, but the exact form so far eludes me.
> 
Here's my solution (I haven't bothered with making it efficient, BTW):

import operator

def solve(n):
     best_len = n
     best_expr = ""
     for x in range(1, n - 2):
         for y in range(x, n):
             for op, name in operator_list:
                 # Does this pair with this op give the right answer?
                 if op(x, y) == n:
                     lx, ex = numbers[x - 1]
                     ly, ey = numbers[y - 1]
                     # How many digits in total?
                     l = lx + ly
                     # Fewer digits than any previous attempts?
                     if l < best_len:
                         # Build the expression.
                         e = "(%s %s %s)" % (ex, name, ey)
                         best_len, best_expr = l, e
     return best_len, best_expr

operator_list = [(operator.add, "+"), (operator.sub, "-"), 
(operator.mul, "*"), (operator.div, "/"), (operator.pow, "^")]

# Tuples contain number of digits used and expression.
numbers = [(1, str(n)) for n in range(1, 4)]

for n in range(4, 34):
     numbers.append(solve(n))

for i, (l, e) in enumerate(numbers):
     print "%2d = %s" % (i + 1, e)