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.

Advertisements

2 Responses to “Project Euler Problem #9”

  1. Hans Says:

    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.

    • keyzero Says:

      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.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: