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

[Dan Goodman]

MRAB wrote:
> 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)

Sadly this doesn't work because you're assuming that the shortest 
expression always involves increasing the size of the numbers at every 
step. For example, your algorithm for 63 gives:

(3 * (3 * (1 + (2 * 3))))

which involves 4 operations, whereas the simplest is:

2**(2*3)-1

which only involves 3 (but has an intermediate value 2**6=64 above the 
target value).

Fixing this is actually pretty hard, because the search space becomes 
very large if you allow yourself arbitrarily large numbers. You can't do 
any obvious pruning that I can think of, because operations between very 
large numbers can end up very small (for example, 13**3-3**7=10 even 
though 13**3=2197 and 3**7=2187 are both very large), and the shortest 
path to a small number might go through very large numbers (I bet with a 
bit more thought than I have put into it, you could come up with some 
examples where the intermediate calculations are arbitrarily larger than 
the end result). As well as the growth of the search space, the 
computations get hairy too, try computing 3**3**3**3 for example (or 
better, don't, because it has 3638334640025 digits).

I haven't got a solution that can be guaranteed correct and is feasible 
to compute for anything but very small examples - anyone done better?

Dan