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

[Luke Dunn]

yes power towers are allowed

exponentiation, multiplication, division, addition and subtraction. Brackets
when necessary but length is sorted on number of digits not number of
operators plus digits.

I always try my homework myself first. in 38 years of life I've learned only
to do what i want, if I wanted everyone else to do my work for me I'd be a
management consultant !
On Fri, Feb 20, 2009 at 3:52 PM, Luke Dunn <luke.dunn at gmail.com> wrote:

> I am teaching myself coding. No university or school, so i guess its
> homework if you like. i am interested in algorithms generally, after doing
> some of Project Euler. Of course my own learning process is best served by
> just getting on with it but sometimes you will do that while other times you
> might just choose to ask for help. if no one suggests then i will probably
> shelve it and come back to it myself when I'm fresh.
>
> no it's not a real world problem but my grounding is in math so i like pure
> stuff anyway. don't see how that is a problem, as a math person i accept the
> validity of pure research conducted just for curiosity and aesthetic
> satisfaction. it often finds an application later anyway
>
> Thanks for your helpful suggestion of trying other methods and i will do
> that in time. my motive was to share an interesting problem because a human
> of moderate math education can sit down with this and find minimal solutions
> easily but the intuition they use is quite subtle, hence the idea of
> converting the human heuristic into an algorithm became of interest, and
> particularly a recursive one. i find that the development of a piece of
> recursion usually comes as an 'aha', and since i hadn't had such a moment, i
> thought i'd turn the problem loose on the public. also i found no online
> reference to this problem so it seemed ripe for sharing.
>
>   On Fri, Feb 20, 2009 at 3:39 PM, Nigel Rantor <wiggly at wiggly.org> wrote:
>
>> Trip Technician wrote:
>>
>>> 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
>>
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20090220/3ed6c4f0/attachment.html>