Project Euler Problem #56

May 21, 2010

Read the details of the problem here

Summary

Considering natural numbers of the form, ab, finding the maximum digital sum.

Solution

Very easy to create a brute force solution with Java’s BigInteger support. I guessed that the answer would be found up in the high end of the range specified and only searched there.

BigInteger.metaClass.digitSum() { ->
  delegate.toString()*.toInteger().sum()
}

def answer = 0

(90G..99G).each { a ->
  (90G..99G).each { b ->
    answer = [ answer, a.pow(b).digitSum() ].max()
  }
}

Run time is 95 milliseconds.

Conclusion

Groovy’s transparent integration with the Java BigInteger class made this a snap to put together. The listops, spread operator and metaClass extensions made for a clean syntax.

It’s actually possible to do the calculation as Groovy “one-liner” which has the same run time.

def answer =
    ([(90G..99G).toList()]*2).combinations()
                             .collect { it[0].pow(it[1]).digitSum() }
                             .max()

Not sure if I like this or not.

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: