On Feb 20, 6:31 am, Trip Technician <luke.d...@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. -- http://mail.python.org/mailman/listinfo/python-list
