Project Euler Problem #53

May 19, 2010

Read the details of the problem here

Summary

How many values of C(n,r), for 1 ≤ n ≤ 100, exceed one-million?

Solution

From the look of the question it appeared that it was going to require a lot of multiplication and division of the fairly non-performant BigIntegers as n! gets very large, very quickly. As per other problems of this nature it seemed that using log values might be better.

This would involve reformulating the combinations equation as
log(n!)-(log(r!)+log((n-r)!) so quite straightforward really. In order to reduce the time spent calculating factorials (and their logs) I just initialised them into an array up front rather than using any special memoization technique.

The actual summation was then easy to do with Groovy listops.

def MAXNUM = 100
def LIMIT = Math.log10(1e6)

def fact = new double[MAXNUM+1]
(0..1).each { fact[it] = Math.log10(1) }

for (i in 2..MAXNUM) {
  fact[i] = Math.log10(i) + fact[i-1]
}

def answer =
    (1..MAXNUM).sum { n ->
        (1..<n).findAll { r -> fact[n] - (fact[r] + fact[n-r]) > LIMIT }
               .size()
    }

This runs in just under 80 ms which seems quite reasonable given that it’s essentially a listop-based declarative solution.

Conclusion

Groovy’s features made the creation of this solution quite simple and was surprisingly performant.

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: