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

[Trip Technician]

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.

 

[Nigel Rantor]

anyone interested in looking at the following problem.

if you can give me a good reason why this is not homework I'd love to
hear it...I just don't see how this is a real 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.

Wow. Okay, what other ways have you tried so far? Or are you beating
your head against the "search the entire problem space" solution still?

This problem smells a lot like factorisation, so I would think of it in
terms of wanting to reduce the target number using as few operations as
possible.

If you allow exponentiation that's going to be your biggest hitter so
you know that the best you can do using 2 digits is n^n where n is the
largest digit you allow yourself.

Are you going to allow things like n^n^n or not?

n

 

[Paul Rubin]

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.

This sounds a little like a homework assignment, or maybe a challenge
you are trying to solve for yourself, rather than be given a complete
answer for. Anyway, the basic idea is to enumerate the expression
trees with 1 digit, then 2 digits, then 3 digits, etc, and compute the
value expressed by each tree.

 

[Trip Technician]

This sounds a little like a homework assignment, or maybe a challenge
you are trying to solve for yourself, rather than be given a complete
answer for.  Anyway, the basic idea is to enumerate the expression
trees with 1 digit, then 2 digits, then 3 digits, etc, and compute the
value expressed by each tree.

Thanks will get onto it. It's just a challenge I set myself so hints
only are cool.

 

[Trip Technician]

if you can give me a good reason why this is not homework I'd love to
hear it...I just don't see how this is a real problem.











Wow. Okay, what other ways have you tried so far? Or are you beating
your head against the "search the entire problem space" solution still?

This problem smells a lot like factorisation, so I would think of it in
terms of wanting to reduce the target number using as few operations as
possible.

If you allow exponentiation that's going to be your biggest hitter so
you know that the best you can do using 2 digits is n^n where n is the
largest digit you allow yourself.

Are you going to allow things like n^n^n or not?

   n- Hide quoted text -

- Show quoted text -

yes n^n^n would be fine. agree it is connected to factorisation.
building a tree of possible expressions is my next angle.

 

[Nigel Rantor]

yes power towers are allowed

right, okay, without coding it here's my thought.

factorise the numbers you have but only allowing primes that exist in
your digit set.

then take that factorisation and turn any repeated runs of digits
multiplied by themselves into power-towers

any remainder can then be created in other ways, starting with a way
other than exponentiation that is able to create the largest number,
i.e. multiplication, then addition...

I've not got time to put it into code right now but it shouldn't be too
hard...

e.g.

digits : 3, 2, 1

n : 10
10 = 2*5 - but we don't have 5...
10 = 3*3 + 1
10 = 3^2+1
3 digits

n : 27
27 = 3*3*3
27 = 3^3
2 digits

n : 33
33 = 3*3*3 + 6
33 = 3*3*3 + 3*2
33 = 3^3+3*2
4 digits

 

[Nigel Rantor]

yes n^n^n would be fine. agree it is connected to factorisation.
building a tree of possible expressions is my next angle.

I think building trees of the possible expressions as a couple of other
people have suggested is simply a more structured way of doing what
you're currnetly doing.

Right now you're throwing darts at the problem space, and hoping that
the next one point you hit will be a more optimal solution.

If you enumerate all the expression trees you are just ensuring you
don't miss any solutions.

I think the algorithm/hueristic I just posted should get you to the
answer quicker though...

n

 

[Tim Wintle]

Luke Dunn wrote:

<snip>

That was my initial thought when I read this too - but I'm not certain
that is guaranteed to find a solution (i.e. a solution that's optimal).

I'd welcome a proof that it will though, a few minutes thought hasn't
found a counter-example.

 

[Dan Goodman]

This sounds kind of similar to a problem I posted to this list last
year, you might find that thread gives you some ideas:

http://mail.python.org/pipermail/python-list/2008-January/474071.html

Dan

 

[Jonathan Gardner]

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.

 

[Rhodri James]

On Thu, 26 Feb 2009 23:10:20 -0000, Jonathan Gardner

[snip]

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.

This relies each value having the same set of next states no matter how
it's reached. Unfortunately that's not true. Consider what happens
when you walk on from (1+3) and (2+2):

One possible step from (1+3) is ((1/3)+3) == 3.33... There's no single
step from (2+2) that can get you to the same place.

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.

Trivial yes, but the number of different new trees is large when you're
dealing with four digits, and ridiculous with 5.

 

[MRAB]

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)

 

[Dan Goodman]

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