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#.
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 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 . 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 
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 ]
numberOfCombinations (4 – 1) [ 2; 3 ]
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.
A test case for this which is taxing on performance is as follows:
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:
The test case with the same input but using the memoized solution is below:
This now clocks in at 66 milliseconds.
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