[Tutor] A recreational math problem for Useless Python

[Rob Andrews]

Danny Yoo wrote:
> 
> Hiya everyone,
> 
> I've been glancing at Donald Knuth's neat "Selected Papers on Computer
> Science" and ran across an interesting problem that he presents.  It
> sounds like a lot of fun, and perhaps someone might be interested in
> trying their hand at it.  Here's the challenge problem (any mispelings are
> due to frantic typing):
> 
> """
> "The numbers sqrt(1), sqrt(2), ..., sqrt(50) are to be partitioned into
> two parts whose sum is nearly equal; find the best such partition you can,
> using less than 10 seconds of computer time.""
> 
> For example, it turns out to be possible to find the best partition of the
> smaller set of numbers [sqrt(1), sqrt(2), ... sqrt(30)] after only about
> one second of computer time; the answer is:
> 
>     sqrt(2) + sqrt(6) + sqrt(9) + sqrt(11) + sqrt(12) + sqrt(13) +
>     sqrt(14) + sqrt(21) + sqrt(23) + sqrt(24) + sqrt(25) + sqrt(26) +
>     sqrt(27) + sqrt(30)
> 
>     is approximately equal to
> 
>         56.04142 25880 73351 85163 20826
> 
>     and:
> 
>     sqrt(1) + sqrt(3) + sqrt(4) + sqrt(5) + sqrt(7) + sqrt(8) +
>     sqrt(10) + sqrt(15) + sqrt(16) + sqrt(17) + sqrt(18) +
>     sqrt(19) + sqrt(20) + sqrt(22) + sqrt(28) + sqrt(29)
> 
>     is approximately equal to
> 
>         56.04142 26276 19557 30332 11496
> 
> Note that the two sums agree to nine significant digits.  The problem with
> 50 instead of 30 is much more difficult, and it appears hopeless to find
> an absolutely optimum partition in only 10 seconds.  This is one of the
> beautiful features of Floyd's problem, since it allows for a friendly
> competition between the members of the class (with a tie score very
> unlikely), and especially because it makes the problem typical of real
> life situations.  We are often confronted with problems that cannot be
> solved exactly at reasonable cost, so we must do the best we can under
> finite limitations... The time restriction encourages us to think, not
> merely to compute!
> """

If I can come up with a short way of describing this (or if someone with
a better grasp of the problem than I have did so [hint, hint]), I'll
cheerfully post it to Useless.

I'm also about to post a link to the CPAN scripts archive on the
Challenges page. I count 144 Perl scripts in their collection, and I'd
say that Useless has at least about that many scripts (but they still
earn respect for their massive module collection, of course). I'd
imagine quite a few of these Perl scripts could be better written in
Python. (No disrespect to Perl here, which has not been cruel to me at
all. I just figure there's a reasonable likelihood that some of these
could be used to demonstrate strengths of Python by comparison.)

On the general subject of Perl/Python comparison, I notice from time to
time, in places other than the Tutor List, comparisons of Python and
Perl with a good bit of friendly competition. But I also notice that
these comparisons are often based around someone's experiment in which
they wrote a Perl script using regular expressions (which Perl is said
to excel at) and claimed that Python is significantly slower than Perl.

I really have no interest in provoking a (pointless) language debate.
There are plenty enough of those already if someone wants to find them.
What I do wonder is if Python has any niche areas comparable with the
fame of Perl's regular expression capability. Python does seem to be the
best language I've seen for CGI (by a very healthy margin), but *best*
is obviously a really subjective statement. I just have a mild academic
curiosity if the Python *underwater basket-weaving* module is considered
extremely refined in comparison with other *underwater basket-weaving*
approaches.

I have seen some odd magic in Python, in any event. I have encountred
anti-Python sentiment from some of my peers around here, but only before
they actually have to modify someone else's Python code. As soon as they
discover how readable it is, the complaints stop and Python book sales
increment.

I'd best get that second cup of coffee before I babble any further.

Happy Monday,
Rob

-- 
The source code repository you didn't see coming...
Useless Python!
http://www.lowerstandard.com/python