Project Euler Problem #36

May 3, 2010

Read the details of the problem here

Summary

Find the sum of all numbers less than one million, which are palindromic in base 10 and base 2.

Solution

Straightforward brute-force solution using Java library calls to check for palindromes and get the binary representation. Only slight optimization was to quickly eliminate numbers ending in zero and even numbers (so the LSb was 0) rather before checking for palindromic properties.

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

def answer =
    (1..<1000000).findAll {
                    ((it % 10 != 0) && ((it & 1) == 1)
                     && it.toString().isPalindrome()
                     && Integer.toBinaryString(it).isPalindrome())
                  }.sum()

This runs in 3.12 seconds. Not particularly fast, but OK for this solution. A Java version runs in 116 ms – 26x faster – not so much a discrepancy as usual as a lot of the work is being done within the Java runtime libraries.

Conclusion

Groovy makes it possible to write fairly declarative code using listops, although in this case the Java version is just as simple. Runtime performance is wanting, as always, but time-to-solution is very good. I used metaClass extensions to add the isPalindrome() method to strings to improve readability (perhaps?) and performance was comparable to just using a method call.

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: