Project Euler Problem #74

May 21, 2010

Read the details of the problem here

Summary

Determine the number of factorial chains that contain exactly sixty non-repeating terms.

Solution

Quite a straightforward programming problem, nothing really mathematical in nature, just a matter of being able to do the processing in a sufficiently efficient manner to meet the 15 second deadline.

My initial attempt just used an array to record which numbers had been seen in the chain (by recording the current number being inspected) but this was taking around 18.3 seconds. As I’d seen on earlier problems Groovy seems to have adverse performance when handling large arrays (more investigation necessary) and it had to be quite large at 6*362880*4 = 8.3+MB (not including overheads) to handle the possible digital sums. Using a native Java method to carry out the summing of the digit factorial reduced the time down to 14.1 seconds but I felt that a better implementation of the chaining algorithm might allow the job to be done wholly in Groovy.

I reimplemented the algorithm building a list of the numbers seen in the chain and this ran fast enough to be acceptable. It used the same technique of caching chain lengths for previous results so that, should that number be seen again, the length of the partial chain can just be appended to the current one.

Integer.metaClass.sumDigitFactorials { ->
  def factorials = [ 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880 ]
  def sum = 0
  def str = delegate.toString()
  for (i in str) {
    sum += factorials[i.toInteger()]
  }
  sum
}

def cache = new int[6 * 362880 + 1]
def answer = 0

for (i in 1..<1000000) {

  def len = 0

  if (cache[i] != 0) {
    len = cache[i]
  }
  else {
    def chain = [i]
    def n = i.sumDigitFactorials()

    while ((cache[n] == 0) && !chain.contains(n)) {
      chain << n
      n = n.sumDigitFactorials()
    }

    len = chain.size()
    if (cache[n] != 0) len += cache[n]
    cache[i] = len
  }

  if (len == 60) answer++
}

This runs in 8.3 seconds. A Java equivalent, which uses more usual moddiv functions to calculate the sum of digits runs in around 230 milliseconds (36x faster) and a Java version of the original array-based solution ran in only 270 ms so doesn’t seem to have the odd pathological behaviour of Groovy’s performance with large arrays.

As a matter of record, the sumDigitFactorials() method is called around 1.32 million times during processing so it’s efficiency is important. I tried memoizing the results but it actually had a slight detrimental effect on the run time, so I’m guessing that the cache was relatively sparse and the maintenance overhead outweighed the benefits.

Conclusion

Groovy was slooooow but had some nice language features around the processing of lists that made the solution relatively simple to put together.

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: