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

[andrew cooke]

this is a neat problem.

here is what i would do: use generators that extend an input.  a stream
approach.  the initial input would be the numbers themselves.

[('1', 1),('2', 2),('3', 3)]

those are (expression, value) pairs

then an initial attempt at the next function would be to extend that list
with additions:

def additions(pairs):
  for (expr1, value1) in pairs:
    # first, pass through unchanged
    yield (expr1, value1)
    # then generate all possible additions
    for (expr2, value2) in pairs:
      yield ('%s+%s'%(value1, value2), value1 + value2))

this would give you:

[('1', 1),('2', 2),('3', 3), ('1+1', 2), ...]

(you may need to add parentheses to expressions to preserve meaning
correctly)

you could extend that with an extra loop over different operations.
(subtraction, multiplication, etc)

then you could repeat that as often as you want (eating its own tail, in a
sense, i think).  an infinite list is ok because these are generators.

then you could filter that to group expressions that give a certain value,
and find the shortest.

andrew



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.
> --
> http://mail.python.org/mailman/listinfo/python-list
>
>