Pythagoras and lambdas…..

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.

About this entry

You’re currently reading “Pythagoras and lambdas…..,” an entry on Shriphani Palakodety

Published:: 08.23.08 / 10pm

Category:: Mathematics, python

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)

About

Hello

I am Shriphani Palakodety – an undergraduate in Purdue’s CS department. My interests in computing involve:

Machine Learning
Natural user interfaces
Machine Translation
Information Retrieval

I recently finished an internship with Microsoft in Redmond, WA with the Productivity Search team and my work involved Machine Translation and Cross-Lingual Search. I also code in my spare time and you can find snippets on this blog or in my public repos : http://github.com/shriphani

Other Links:

Seth 08.23.08 / 11pm

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 08.24.08 / 12am

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 08.24.08 / 1am

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

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 08.24.08 / 1am

@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.

@Jim Meier: Thanks for your solution as well.

rgz 08.25.08 / 4am

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 08.25.08 / 1pm

I recommend cutting your looping down.
p hyp 1000)

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

Shriphani Palakodety

Pythagoras and lambdas…..

About this entry

7 Comments

Have your say

About

Hello

Recently

Categories