Project Euler Problem #4

November 7, 2009

Read the details of the problem here

Summary

Find the largest palindrome made from the product of two 3-digit numbers.

Solution

An obvious brute force solution completes in 1.14 seconds. The only simple optimizations I made were to count down rather than up for the two numbers and to put a guard condition on the expensive functions.

String.metaClass.isPalindrome = { ->;
    delegate == delegate.reverse()
}

def answer = 0

for (i in 999..100) {
    for (j in 999..100) {
       def p = i * j
       if ((p > answer)  && (p.toString().isPalindrome())) answer = p
    }
}

As they say, “‘Nuff Said!”

Conclusion

The ability to extend to the String metaclass with an “isPalindrome()” method leads to quite a nice syntax but isn’t much different to just defining a support method. (I could also have put the function into the Integer class directly and hidden the String conversion in that.)

The solution ran well within my 15 second limit but still felt slow for what it was doing. An equivalent Java version runs in 137 ms. That’s around 8x faster.

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: