## 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

September 4, 2010 at 20:07

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

September 4, 2010 at 22:53

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