## Project Euler Problem #9

### January 25, 2010

Read the details of the problem here

**Summary**

Find the only Pythagorean triplet, {a, b, c}, for which a + b + c = 1000.

**Solution**

Straightforward, brute force approach but trying to avoid as much “complex” computation as possible in order to keep the performance up.

def answer = 0 for (a in 1..<500) { for (b in (a+1)..500) { def c = 1000 - (a + b) if ((c > b) && (c * c == a * a + b * b)) { answer = a * b * c break } } if (answer > 0) break }

This runs in 0.53 seconds. A Java equivalent runs in 5 ms – two orders of magnitude faster. The breaks on the loops are messy but clear enough given this limited context.

**Conclusion**

Groovy’s language features didn’t really play any part in this solution. It was just straightforward number crunching. It did originally use *<range>.each {}* closure constructs for the loops but didn’t like the way it was necessary to throw an exception to bale out when an answer was found. I don’t think that it made the solution any clearer or simpler to write in this particular scenario. Groovy maths performance was dire.

July 26, 2010 at 11:18

I think you should pay a little more attention to the limits of your for loops.

For a given a the minimum values of b and c are:

b=a+1 and c=a+2.

So for a given a the minimum value of a+b+c is 3a+3.

So the maximum value of a is (limit-3)/3 instead of 500.

Secondly after choosing a the amount left for b+c is limit-a.

As the minimum value of b+c=2b+1. So the maximum value of b is (limit-a-1)/2.

Setting proper limits will remove the need of breaks.

If Groovy slows down on a computed upper limit for b then you can precalculate this upper limit before entering the b-loop.

July 26, 2010 at 23:54

Hi Hans. You’re right, of course. When I was doing these earlier problems I was just hacking out very straightforward programmatic solutions without thinking too much of the maths involved unless I found that I needed to engage my brain a little more to beat the clock. As this ran so fast anyway I didn’t worry about doing any more analysis on the problem, opting rather for the obvious solution.