There are four types of common coins in   US   currency:

   quarters   (25 cents)
   dimes   (10 cents)
   nickels   (5 cents),   and 
   pennies   (1 cent) 


There are six ways to make change for 15 cents:

   A dime and a nickel 
   A dime and 5 pennies
   3 nickels
   2 nickels and 5 pennies
   A nickel and 10 pennies
   15 pennies


Task

How many ways are there to make change for a dollar using these common coins?     (1 dollar = 100 cents).



Optional

Less common are dollar coins (100 cents);   and very rare are half dollars (50 cents).   With the addition of these two coins, how many ways are there to make change for $1000?

(Note:   the answer is larger than   232).



References

 an algorithm from the book Structure and Interpretation of Computer Programs.
 an article in the algorithmist.
 Change-making problem on Wikipedia.


 
var cache = new Map();
 
main() {
    var stopwatch = new Stopwatch()..start();
 
    // use the brute-force recursion for the small problem
    int amount = 100;
    list coinTypes = [25,10,5,1];
    print (coins(amount,coinTypes).toString() + " ways for $amount using $coinTypes coins.");
 
    // use the cache version for the big problem
    amount = 100000;
    coinTypes = [100,50,25,10,5,1];
    print (cachedCoins(amount,coinTypes).toString() + " ways for $amount using $coinTypes coins.");
 
    stopwatch.stop();
    print ("... completed in " + (stopwatch.elapsedMilliseconds/1000).toString() + " seconds");
}
 
 
coins(int amount, list coinTypes) {
    int count = 0;
 
    if(coinTypes.length == 1) return (1);   // just pennies available, so only one way to make change
 
    for(int i=0; i<=(amount/coinTypes[0]).toInt(); i++){                // brute force recursion
      count += coins(amount-(i*coinTypes[0]),coinTypes.sublist(1));     // sublist(1) is like lisp's '(rest ...)'
    }
 
    // uncomment if you want to see intermediate steps
    //print("there are " + count.toString() +" ways to count change for ${amount.toString()} using ${coinTypes} coins.");
    return(count);
  }
 
 
  cachedCoins(int amount, list coinTypes) {
      int count = 0;
 
      // this is more efficient, looks at last two coins.  but not fast enough for the optional exercise.
      if(coinTypes.length == 2) return ((amount/coinTypes[0]).toInt() + 1);
 
      var key = "$amount.$coinTypes";         // lookes like "100.[25,10,5,1]"
      var cacheValue = cache[key];            // check whether we have seen this before
 
      if(cacheValue != null) return(cacheValue);
 
      count = 0;
      // same recursion as simple method, but caches all subqueries too
      for(int i=0; i<=(amount/coinTypes[0]).toInt(); i++){
        count += cachedCoins(amount-(i*coinTypes[0]),coinTypes.sublist(1));     // sublist(1) is like lisp's '(rest ...)'
      }
 
      cache[key] = count;                     // add this to the cache
      return(count);
    }
 