Project Euler Problem #30

February 14, 2010

Read the details of the problem here

Summary

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

Solution

I used a straightforward brute force approach. The highest number that can be attained with these criteria is at most going to be a 6-digit number as 7*95 = 413343 so that forms an upper bound for the search. The only real optimisation I made was pre-calculating the fifth powers.

def p5 = [:]
0.upto(9) { p5[it.toString()] = it ** 5 }

def answer = (2..(6*p5["9"])).findAll { n->
    n.toString().toList().sum { p5[it] } == n
}.sum()

This ran in 12.41 seconds so just inside my 15 second constraint. A more procedural approach, using an integer array for holding the fifth powers and a numerical approach to extracting the digits ran in a little over 4 seconds.

Conclusion

Again, I may have used an overly Groovy approach to this and sacrified a lot in terms of efficiency for use of the listop features. You can see that in terms of time-to-solution for questions like this, Groovy scores very well, as long as runtime performance isn’t an issue.

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: