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

[Jonathan Gardner]

On Feb 20, 6:31 am, Trip Technician <luke.d... at gmail.com> 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.


Actually, representing 33 has an even shorter answer: '33'

There is actually a really easy solution for this. What you are really
doing is finding the shortest path from point A (the expression '') to
another expression that evaluates to the target number.

>From each point, you can take steps that (a) add a digit to the end or
(b) add an operator---but only if it makes sense. Since operators
don't count, those steps don't add anything to the distance, while the
digits do.

What you do is you start walking the map from point A to some
mysterious point that evaluates to the result you want. Actually, you
send out walkers in all directions, and tell only the walkers that
have taken the fewest steps to take another step. Once a walker gets
to an expression with the result, you have your answer since he is the
first walker to get there. When a walker gets to an expression that
has already been visited, you can tell that walker to go home since
his path was no good. When a walker gets to an expression that
evaluates to a value you have already seen, that walker too should go
home since he has just found a longer path to the same result.

So you have a set of walkers, and each walker has the expression they
used to get to where they are and how many steps they took to get
there. You also have a set of values you have seen before and thus
values that if a walker finds you are no longer interested in.

For each iteration, you take each surviving walker and spawn a new
walker that takes a step in each possible direction. Then you check if
any of those walkers found the value you are looking for. If so,
you've found the answer. If they hit a value you've already seen, you
drop that walker from the set.

The only hanging point is parentheses. What you can do here is instead
of building a linear expression, build a tree expression that shows
the operations and the values they operate. It should be trivial to
calculate all the different new trees that are one digit longer than a
previous tree.