Project Euler Problem #39

April 30, 2010

Read the details of the problem here

Summary

If p is the perimeter of a right angle triangle, {a, b, c}, which value, for p ≤ 1000, has the most solutions?

Solution

Straightforward, brute-force solution. Just run through a combination of lengths for two sides and calculate the hypotenuse. For hypotenuses that are of integer length, check that the perimeter is within the limit set and, if so, increment a count for that length keeping track of the maximum element as it goes along.

def LIMIT = 1000
def ( c, max, answer ) = [ [0]*LIMIT, 0, 0 ]

for (i in 1..<LIMIT.intdiv(2)) {
  for (j in 1..<LIMIT-i) {
    def hyp = ((i * i) + (j * j)) ** 0.5
    if ((int)hyp == hyp) {
      def p = i + j + hyp
      if (p < LIMIT) {
        c[p]++
        if (c[p] > max) ( max, answer ) = [ c[p], p ]
      }
    }
  }
}

This runs in 0.59 seconds.

Conclusion

Groovy made for a terse syntax but nothing that couldn’t have easily been done in Java. Interestingly, replacing the pythonic syntax of the square root (n ** 0.5) with the traditional Java library call to Math.sqrt(n) the run-time drops to 0.27 seconds. In this case p needs to be forced to an int when being used as an index into c[]. This change in performance is quite astonishing.

Advertisements

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: