Project Euler Problem #31

June 16, 2010

Read the details of the problem here

Summary

Investigating combinations of English currency denominations.

Solution

Solved this one ages ago, but hadn’t written it up yet, so just playing catch up! It was a straightforward enough problem. The choice was between an accumulating array for the coin combinations or a nested loop for each coin value. The former would create less code and, using Groovy listops would be quite neat too, so that’s the approach I took.

def ( total, coins ) =
    [ 200, [ 1, 2, 5, 10, 20, 50, 100, 200 ] ]

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

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

def answer = nways[total]

This runs in 43 ms, so well within my 15 second limit.

Conclusion

Groovy made this a terse solution, and performance was quite adequate too even using Groovy a list rather than an array.

Advertisements

2 Responses to “Project Euler Problem #31”


  1. […] 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 […]


  2. […] 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 […]


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: