Project Euler Problem #76

September 4, 2010

Read the details of the problem here

Summary

How many different ways can one hundred be written as a sum of at least two positive integers?

Solution

Simple to solve using the solution to Problem #31 as a base by just assuming that coins with face values of 1-99 are available (as at least two integers are required). Strictly speaking, of course, it’s not necessary to use the coins array here as all values are present and a simple loop would be adequate – however doing it like this, given I had the previous solution available, shows the similarity between that problem and this one (and appealed to my laziness).

 
def ( total, coins ) = [ 100, (1..<100) ]

def nways = [1] + [0]*total

coins.each { coin ->
  coin.upto(total) { nways[it] += nways[it - coin] }
}

def answer = nways[total]

This runs in 54 ms. A Java version, which doesn’t use a coins array, runs in 220 microseconds – that’s 245 times faster.

After gaining access to the Project Euler forum for this problem, I found that there is a way to solve it in a much more time-efficient manner using partitions. This would provide a far more scalable solution for solving this kind of puzzle for far larger number ranges.

Conclusion

Groovy features made the loops terse to write but not fundamentally different to a normal Java solution.

Advertisements

One Response to “Project Euler Problem #76”


  1. […] and quick to solve using the solutions to Problem #31 and Problem #76 as a starter. The values of primes just replace the values of coins from Problem #31. It’s a […]


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: