Counting Change Again?

Problem 76 at Project Euler is really just the "change counting" problem: how many ways can you count out 100 cents if you have coins in denominations from 1 to 99? However, when I plug those values into my previous implementations of the change counting algorithm, it runs forever...well, maybe not forever, but for hours and hours, while using 100% of my RAM. OK, so that's not going to work. At first I thought that the problem was simply that too many of the answers were in memory (i.e. sequences of coins), so I changed the implementation, simply to count possible answers:

let rec countChange =
    match coins, amount with
    ¦ _, 0 -> 1L
    ¦ [], _ -> 0L
    ¦ h::t, _ -> [ 0..h..amount ]
                 ¦> List.map (fun amt' -> countChange t (amount - amt'))
                 ¦> Seq.fold1 (+)

Let's review this. How many ways are there to make 0 in change, whatever the available coins? There's 1 way. How many ways are there to make some other quantity in change if you have no coins? 0. Finally, how many ways are there to make C in change if you have a a list of coins h::t? Partition the problem thus: use the coin h to pay out a partition of C (obviously you can use coin h up to C/h times), then make up the remaining partition of C with the rest of the list. If, to solve each subproblem, you're dividing C by the denomination of a coin, then the size of the problem space is exponential in the number of denominations: (C/denomination₁) * (C/denomination₂) * ... * (C/denomination_n) = O(Cⁿ). You can't exactly tell from this example, but the rate of growth here is clearly superpolynomial:

> countChange [ 4; 5 ] 20;;
val it : int64 = 2L
> countChange [ 3; 4; 5 ] 20;;
val it : int64 = 6L
> countChange [ 3; 4; 5; 6 ] 20;;
val it : int64 = 11L
> countChange [2;  3; 4; 5; 6 ] 20;;
val it : int64 = 47L
>

Anyway, it should be clear why there's no point in waiting for the solution to countChange [ 1..99 ] 100. However, I can memoize the change counting algorithm, since it's deterministic: for a given amount, and a given set of coins, the answer is always the same (commerce would be hopeless otherwise). This turns out to be fairly easy, notwithstanding the two arguments to the function. Here's my answer:

open System.Collections.Generic;;

let memoize f =
    let cache = Dictionary<_,>()
    fun x y ->
        if cache.ContainsKey((x, y)) then cache.[(x, y)]
        // Remember that f will always consult the memo
        // for subproblems.
        else let result = f x y
             cache.[(x, y)] <- result              
             result  

let rec countChange =   
  // Turn this into a function that returns a function.   
  // The *returned* function will be evaluated over the arguments.   
  let countChange' coins amount =      
    match coins, amount with     
    ¦ _, 0 -> 1L     
    ¦ [], _ -> 0L     
    ¦ h::t, _ -> [ 0..h..amount ]                   
                 ¦> List.map (fun amt' -> countChange t (amount - amt'))
                 ¦> Seq.fold1 (+)
  memoize countChange'

The answer shows up in a few seconds. Since F# lists are immutable, they can easily be compared for reference equality, rather than in O(n²) time. That is, the initial list [ 99..(-1)..1 ] is a 99 prepended to the list [ 98..(-1)..1 ], and so on. We partition the problem into subproblems corresponding to the head and tail of the list, but no additional lists are created beyond the argument to the function (there's only one list beginning with 50, ever, and it's the tail of the list beginning with 51). Microsoft.FSharp.Collections.List<_>.CompareTo() sees literally the same lists again and again when called from memoize(). Hence the lickety-split performance.

Perhaps this could all be done imperatively, though I don't how OOP is at all applicable to this sort of classic optimization problem (what could justify a Coin class here)? If you haven't read Daniel Friedman's "The Role of the Study of Programming Languages in the Education of a Programmer," here's your chance. As my buddy George Paci puts it, "The title is clearly written by a professor; a marketing guy would have called it something like, 'Holy Crap! It's Amazing What You Can Do with Program Transformations!'"