Project Euler Problem #34

February 23, 2010

Read the details of the problem here

Summary

Find the sum of all numbers which are equal to the sum of the factorial of their digits.

Solution

I initially used a brute-force approach to this, running through the numbers up to 9,999,999 (as 7*9! < 107), summing the pre-calculated factorials of their digits and checking for a match. However, using this method, I was unable to get down below 15 seconds. Although a Java version would run in 2.97 seconds, a Groovy implementation was taking 161 seconds.

After some more thought, I decided that it might be better to essentially walk through a chain of numbers that were potential matches, cutting off when the maximum value would be exceeded by the sum of the digits for that chain. As well as reducing the number of numbers being checked, it would greatly reduce the effort in the sum of factorials for each number as there would be no need to re-work the sum for any preceding numbers by just adding the factorial for the digit being appended each time.

def fact = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]

def solve34(n, sum, fact) {
    def total = ((n > 9) && (n == sum)) ? n : 0
    if (n * 10 <= sum + fact[9]) {
        def s = (n == 0) ? 1 : 0
        for (i in s..9)
            total += solve34(n * 10 + i, sum + fact[i], fact)
    }
    return total
}

def answer = solve34(0, 0, fact)

This worked surprisingly well and runs in 2.06 seconds, checking just 559,590 numbers (less than 6% of the original version). A Java version ran in under 20 ms.

Note that I’ve used a for-in loop at the heart of this, using (s..9).each {} pushes the runtime out to 5.50 seconds…a 160%+ overhead.

Conclusion

Groovy made this a challenge. If I had been using Java as the implementation language the coding was very straightforward and ran in an acceptable time. However, by forcing me to think about the problem and potential solutions I got a much improved algorithm — two orders of magnitude better in runtime and the code was still quite clear.

Groovy loops with the each{}syntax that create Closures of the loop body have an enormous overhead compared with the for-in loops which keep the code in-line. Unless they are being used to execute a Closure that has been passed in, I doubt their efficacy in inner loops in production code.

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: