Memoizing Counting Change in F#

One of my favorite programming koans is the counting change problem. Its a good one for practicing solving a problem in a new language or just refreshing myself on some recursive algorithmic reasoning.

I’ve been coding in F# for almost a year now professionally and just over a year in my spare time coding. Previously, I had completed this koan in Scala but, until recently, I hadn’t tried it in F#. It came up as a challenge on hackerrank so I thought I’d give it a go in F#.

spoiler alert

the rest of this blog will contain code and links to my full solution on github so you might want to try it out yourself first if you’ve never done this coding koan before.

I went about solving the problem recursively and this was enough to make some of the hackerrank test pass but the solution timed out for a lot of tests – coming in at about 2 minutes for some test cases just didn’t cut it. To make it faster, I used memoization to store up any previously computed values so that I wasn’t duplicating work. This sped up the execution a lot – from around 2 minutes for some test cases to about 60 milliseconds!

The Problem

The problem is as follows:
Given an amount and a list of coin denominations, how many ways can the coin denominations be combined to make up the amount. A combination can use coin denominations more then once.
So, for example:
Amount is 4
Coin denominations are [ 1; 2; 3 ]

The answer is 4 combinations because the coins can be combined as follows:
[ 1; 1; 1; 1 ]
[ 1; 1; 2 ]
[ 1; 3 ]
[ 2; 2 ]

Solving the problem

I came up with a solution using recursion without memoization initially.

So lets say we have a function numberOfCombinations that gets the number of combinations for an amount, amount, out of denominations, denoms.

The numberOfCombinations function works as follows, taking our earlier example:

We take the first denominator – lets call this “main denominination” and subtract that from the amount 4 to get 1. So now we are trying to find the number of combinations that make up 1 from the rest of the denominators [ 2; 3 ]. However, in order to do that, we have to call our numberOfCombinations function recursively on amount, 1 and denoms [ 2; 3 ] – this starts off a recursion as this will itself continue on subtracting 2 from 1 and calling numberOfCombinations for amount -1 on denoms [3]. When we hit negative number, this inner recursive path stops and we return a 0 number of combinations back up the recursive calls.

Meanwhile back in the first numberOfCombinations call (the call we made for numberOfCombinations 4 [ 1; 2; 3 ]), we need to continue subtracting the denominator, 1 so we subtract 1 from 3 and get 2 and so on until we hit a 0 or negative number.

There is also a second recursion too. As we move through the denominations, each one gets a go at becoming the “main denomination” and a go at being the denomination that gets subtracted through a recursive run of the numberOfCombinations function.

All this means is that, we also start off recursive calls for
numberOfCombinations 2 [3]
and number of combinations 3 []

So how do we reach a point where we know we have hit a combination?

Well lets follow one path through the recursion starting with
numberOfCombinations 4 [ 1; 2; 3 ]
giving

numberOfCombinations (4 – 1) [ 2; 3 ]
giving

numberOfCombinations (3 – 2) [ 3 ]
giving -2 [ ]

but numberOfCombinations 3 [ 2; 3] also gives
numberOfCombinations (3 – 3) [] when 3 becomes the “main denominator”

So here we detect a combination because we have reached the amount, 0. the combination detected is [ 1; 3 ].

Below is the algorithm expressed in F# without any memoization optimization.

let rec private numberOfCombinationsNoMemoization (amount:int) (denominations: int list)  =
        match denominations with 
        | [] ->
            0L
        | d :: ds ->
            if amount = 0 then
                1L 
            elif amount < 0 then
                0L
            else 
                (numberOfCombinationsNoMemoization (amount - d) denominations) + 
                (numberOfCombinationsNoMemoization amount ds) |> int64
                

let countChangeNoMemoization (amount:int) (denominations: int list) =
    numberOfCombinationsNoMemoization amount denominations 

A test case for this which is taxing on performance is as follows:

[<Fact>]
let ``no memoization - number of combinations for amount 219 and denominations 36 10 42 7 50 1 49 24 37 12 34 13 39 18 8 29 19 43 5 44 28 23 35 26 should be 168312708`` () =
    countChangeNoMemoization 219 [ 36; 10; 42; 7; 50; 1; 49; 24; 37; 12; 34; 13; 39; 18; 8; 29; 19; 43; 5; 44; 28; 23; 35; 26 ] |> should equal 168312708L

This individual test clocks in at 2 minutes and 2 seconds.

What’s with this memoization stuff?!

Memoization is a way of storing the results of calls to a function for previous parameter values. With the recursive algorithm being used, there is a lot of duplicated work especially when there is a larger number of denominations as in the test case shown above. This is because with all the different paths through the recursion, the recursive function can be called multiple times for the same value for amount and denominations. So there is wasted work. Using memoization, we can store up all the results of previous calls to the recursive function in a Dictionary. So, each time it is called we can look up the Dictionary to see if we have already calculated a result for the amount and denominations in question.

In the new solution below, I have added in this mechanism:

let rec private numberOfCombinations (amount:int) (denominations: int list) (prevCalculatedSolutions:Dictionary<int * Set<int>, int64>) =
    if prevCalculatedSolutions.ContainsKey((amount, Set.ofList denominations)) then 
        prevCalculatedSolutions.[(amount, Set.ofList denominations)]
    else
        match denominations with 
        | [] ->
            0L
        | d :: ds ->
            if amount = 0 then
                1L 
            elif amount < 0 then
                0L
            else 
                let solution = 
                    (numberOfCombinations (amount - d) denominations prevCalculatedSolutions) + 
                    (numberOfCombinations amount ds prevCalculatedSolutions) |> int64
                
                prevCalculatedSolutions.Add((amount, Set.ofList denominations), solution) |> ignore
                solution

let countChange (amount:int) (denominations: int list) =
    numberOfCombinations amount denominations (new Dictionary<int * Set<int>, int64>())

The test case with the same input but using the memoized solution is below:

[<Fact>]
let ``number of combinations for amount 219 and denominations 36 10 42 7 50 1 49 24 37 12 34 13 39 18 8 29 19 43 5 44 28 23 35 26 should be 168312708`` () =
    countChange 219 [ 36; 10; 42; 7; 50; 1; 49; 24; 37; 12; 34; 13; 39; 18; 8; 29; 19; 43; 5; 44; 28; 23; 35; 26 ] |> should equal 168312708L

This now clocks in at 66 milliseconds.

Conclusion

Memoization is a great technique to dramatically increase performance especially in these sort of path finding recursive type problems. With F#’s pragmatic approach, it is quite straight forward to add in a simple memoization mechanism using a .NET Dictionary that can be mutated in place. To make this slightly more pure, an immutable map could be used which would need to be updated passed through all the recursions. However, as the recursive function, numberOfCombinations, is private and quite small, I believe controlled mutation is perfectly fine and a very effective mechanism for memoization.

The full solution with tests is available on my github here

Leave a Reply

Your email address will not be published. Required fields are marked *