Pythagoras and lambdas…..

August 23rd, 2008 · 7 Comments · Mathematics, python

Here is the first bit of code I’ve ever written at college (on my own computer though, I’ve concentration problems in the lab). I was solving problem 39 of the project euler problem set (and I am ashamed of my work). So the question is:

If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.

{20,48,52}, {24,45,51}, {30,40,50}

For which value of p 1000, is the number of solutions maximised?

So, I decided that I could look for Pythagorean triplets using the following snippet:

def checkCond(a, b, c): #c is the bloody hypotenuse and a<b
if c ** 2 == a ** 2 + b ** 2 and a + b + c < 1000:
return True
else:
return False

for c in xrange(1000):
for b in xrange(c):
for a in xrange(b+1):
if checkCond(a, b, c):
if peri_count.has_key(a+b+c):
peri_count[a+b+c] += 1
else:
peri_count[a+b+c] = 1
else:
continue

That gives us a dictionary whose (key, value) pairs are (perimeter, count). We need the max count and then pick the corresponding perimeter. I hence wrote a small function (which was very inefficient) to make the value the keys and the keys the values. I think it is the second time I used “lambda”:

def flip(dict_name):
”‘Flip the dictionary’s (key, value) pairs to (value, key)”‘
return dict(map(lambda item: (item[1], item[0]), dict_name.items()))

and finally, to complete the script:

peri_count = flip(peri_count)

max_no = max(peri_count.keys())
print peri_count[max_no]

So, here are the rather shameful execution stats:

$ time python euler39.py
840

real    3m15.140s
user    0m0.046s
sys     0m0.015s

I suggest you throw a glance at the awesome header that http://desk.stinkpot.org:8080/blog/ has.

Happy Coding.

Tags:

7 Comments so far ↓

Seth // Aug 23, 2008 at 11:51 pm

I’d be remiss as a Python nerd if I didn’t point out that you could speed things up and avoid the lambda/map if you used a list comprehension.

dict([(item[1], item[0]) for item in dict_name.items()])

Keep up the good work!
Seth // Aug 24, 2008 at 12:20 am

Also, a little poking showed that reversing the conditions in checkCond saves a substantial amount of time.

a + b + c < 1000 and c ** 2 == a ** 2 + b ** 2

It’s often a good idea to be very deliberate about arranging conditions in an AND statement. Sometimes you want the most likely to be violated, other times you want the one that’s cheapest to evaluate. Python (and many other languages) won’t test later conditions in an AND after one fails.

I’ll stop poking at your code now. Hope my tips are useful to you.

Jim Meier // Aug 24, 2008 at 1:34 am

Of course, a better solution is to reduce the problem from an O(n^3) to O(n^2) with minimal constant factors:

from math import sqrt, ceil

def solve(p):
    max_unique_hyp = int(ceil(p/2))
    for hyp in xrange(1, max_unique_hyp):
        hyp2 = hyp ** 2
        for x in xrange(1, hyp):
            y = sqrt(hyp2 - x**2)
            if y == int(y) and x+y+hyp  most_solutions[1]:
            most_solutions = (p, len(s))
    return solutions, most_solutions

print most_solutions(1000)

I’m not sure how that’ll show up formatted as a comment, sorry.

The results:

$ time python peri.py
(840.0, 8)

real	0m0.198s
user	0m0.180s
sys	0m0.013s

Shriphani // Aug 24, 2008 at 1:43 am

@seth: Thanks for pointing out the improvement in efficiency by using a list comprehension instead of the lambda+map thingy. And yeah, I should’ve seen that a+b+c< 1000 is easier to evaluate than the other condition.
Shriphani // Aug 24, 2008 at 1:47 am

@Jim Meier: Thanks for your solution as well.
rgz // Aug 25, 2008 at 4:03 am

The real speedup would be using a generator. And while we are at it let’s use argument unpacking and the built-in iteritems.

dict((v,k) for k, v in d.iteritems())
jmoney // Aug 25, 2008 at 1:32 pm

I recommend cutting your looping down.
p hyp 1000)

Just ideas… brute force helps clarify the problems, allowing much more elegant solutions.

Shriphani Palakodety

In Pursuit Of Truth and Beauty