[Tutor] A recreational math problem for Useless Python

[Daniel Coughlin]

Well I know this is not a very good solution - but it is my first attempt.
I used the random module to create the number sets ad that can take a long time.
Is there a better way of going about creating the sets? (I dont want to check
the article yet - besides i doubt i will understand any of it ;-)
The other problem I encountered which is probably soaking up time is that there
is an unaccounted for runtime error that happens periodically. I handle this,
but i know it still happens, and it is knawing at me... If anyone can
figure out way that happens, I'd love to know.

One thing you will notice is that you can change the level of precision by
changing the string slice indexes.

To get two decimal places over usually takes between 5 and 15 seconds. But
sometimes it takes a while.
BTW - I *really* like problems like this - If you have any others, I'd love to
hear about them.
Here's the script:

#!/usr/bin/env python
import math, random

def begin():
	nlist, alist = [], []
	try:
		create(nlist, alist)
	except StandardError, s:
		begin()


def create(newlist2, newlist3):
	if len(newlist2) == 0:
		newlist3 = []
		for i in range(1, 51):
			newlist2.append(i)
	num = int(random.random() * len(newlist2))
	newlist3.append(newlist2[num])
	newlist2.remove(newlist2[num])

	asum, nsum = 0, 0
	for item in newlist3:
		asum = asum + math.sqrt(item)
	for item in newlist2:
		nsum = nsum + math.sqrt(item)
	newlist = [nsum, asum, newlist2, newlist3]
	n = str(newlist[0])
	a = str(newlist[1])
	if n[:5] == a[:5]:
		print newlist[0], newlist[2]
		print newlist[1], newlist[3]
	else:
		create(newlist[2], newlist[3])
print 'Searching..'
begin()



On Mon, 13 Aug 2001, Tim Peters wrote:

> [Danny Yoo]
> > 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): ...
>
> It's an excellent problem, although I wish he would have left square roots
> out of it (floating-point arithmetic complicates the problem to no good
> end).
>
> There's a large and difficult literature on the "subset sum" problem, of
> which this is an instance.  That doesn't mean people should be scared away,
> it means an exact solution is *so* hard ("NP-hard" in the jargon) that
> *nobody* knows how to do it efficiently.  So any stupid-ass <wink> trick you
> can dream up is fair game.  A "stupid-ass trick" is known as a "heuristic"
> in the jargon, BTW, and finding good heuristics is a fascinating game.
>
> After playing with this for a few years <wink>, you might want to check out
> Bartosz Przydatek's 1998 subset-sum heuristic, available in a paper here:
>
>     http://www.cs.cmu.edu/~bartosz/subset/
>
> The ideas there are very simple (honest <wink>), yet at the time it appeared
> to be the best efficient approach known.  I don't know whether something
> better is known now.  You may discover one!
>
>
> _______________________________________________
> Tutor maillist  -  Tutor@python.org
> http://mail.python.org/mailman/listinfo/tutor
>