F# Coin Change Kata with Property-Based Testing

Introduction

The one way to become an expert in something is to practice; and Programming Katas are a very good approach to keep practicing your programming skills.

In this post, I will solve the Coin Change Kata with F# and use Property-Based Testing (with FsCheck) to drive the design.
For me, this was a lesson in writing properties and not so much solving the kata. It was a fun exercise. I thought it would be useful to share my code with you.
If you haven’t any experience with Property-Based Testing or F#, I recommend you look first at those topics.

Coin Change Kata

Description

Ok, there are several different descriptions of this Kata; so, I’ll show you what I want to accomplish first.

“Given an amount and a series of Coin Values, give me the best possible solution that requires the least amount of Coins and the remaining value if there is any”

So, by looking at the definition of the Coin Kata; I need two inputs and two outputs:

Signature

The first thing I did before describing my properties, is defining my signature of my function. My first mistake was I thought I could use integers all over the place. Something like this:

int list -> int -> int * int list

But we can’t have negative coin values, so I started with making a coin type. In the Kata, there are several amounts they use so I chose to use the same:

Note that, by describing the coin values in this way, I have restricted the input values of the coins. This makes Illegal States Unpresentable (from Yaron Minsky).

And so my signature, after type interference, is the following:

Coin list -> int -> int * Coin list

Strictly speaking this is not the right signature, because we are still handling negative amounts, but for the sake of this exercise; I will leave this as an exercise for you.

Properties

First Property: Ice Breaker

So, let’s start coding. The first property should be some kind of Ice Breaker property. I came up with the following:

“Change amount with nothing to change gives back the initial amount”

This is the property when we do not have any coin values, so we just get back the same amount as remaining value. Note that I use ‘byte’ as a input value so I make sure I have a positive value, and for the sake of this exercise. The maximum byte value is enough for this demonstration.

We can easily implement this:

We can play the Devil’s Advocate and intentionally use a fake implementation, for example:

Which will still pass.

Second Property: Boundaries

The next property I wrote was the other way around: what if I haven’t got any amount to change?

“Change zero amount result in original coin values”

Note that we have FsCheck to generate us the random list of our Coins. We don’t care what coins we’re about the use for the change and that’s why we can use FsCheck to generate some for us.

I think this is a good implementation example of how Test Ignorance can be accomplished with Property-Based Testing.

And our implementation:

Now we can’t fill the list so we’re back with the first implementation which makes the two properties pass.

Third Property: Find the Constants

I’m not quite sure this is a proper example of this; because you could state this property for other values as well with some effort and it’s possibly also covered with a latter property. Although, this was the next property I wanted to write because it drives me more in the actual implementation of the function and it’s a constant in this implementation.

“Change is always One if there’s no other coin values”

We can implement this property (and respect the others) with this implementation:

When I have only ‘One’ coins, the change for a random amount is always a list of ‘One’ coins that has the same length of the initial amount to-be changed. I can of course play the Devil’s advocate and change the remaining amount to 42 for example (because 42 is the answer to life):

And so, we can stricken our property to also assert on the remaining amount:

Because of FsCheck this is hardly an issue. I added some Labels (from FsCheck) to clearly state in the output WHAT failed in the property. This is good thing for Defect Localization.

Also note that playing the Devil’s Advocate makes sure that I implement the right implementation and that my properties this state in the most strictly solution.

Fourth Property: Some Things Never Change

For the fourth property, I thought even further about the result and came up with this property. The constant that I found was that whatever I change into coins, the initial to-be-changed amount should always be the sum of the remaining change and the changed coins.

“Sum of changed coins and remaining amount is always the initial to-be-changed amount”

What this property needs, is a non-empty list of coins because we otherwise re-testing the already written property of the empty coins. This is also no issue for FsCheck, with Conditional Properties we can easily define this with the List.length coins <> 0 ==> lazy expression.

This will make sure that the other part of the function only gets evaluated, and so verified if the condition is met.

The rest of the function is the mapping of all the coins into values, sum this and add the remaining amount to this. All this together should be the same as the initial amount.

This is the first time I need to get the actual value of coins, so a made a function for this:

How do we know how much coins we get in a given amount? That’s a division of the amount by that coin value. We need several coin values and so we must also do the division by the other coin values; so, we need the remaining value of the division. That’s a modulo of the amount by that coin value.

We need to do this for all the different coins we have.

Does this pattern sounds familiar?

We have an initial value, we need to loop over a list, and do something with a given value that can be passed to the next loop iteration.

In an imperative language, that’s the for-loop we’re stating:

Something like this (sort of).

But, we’re in a functional language now; so, what’s the alternative? Fold!

Here is some implementation using fold:

One of the things I like to do is to specify the different arguments on its own instead of inlining them (in this case into the List.fold function). I think this increases Readability and shows more the Code’s Intent: that the core and return value is the result of a List.fold operation.

This reminds me of the Formatting Guidelines I described in a previous post that the return value of a method should be placed on a different line to increase readability and highlights “The Plot” of the method.

This is very similar; we want to show the what we’re doing as “The Plot” of the function by specifying the argumented-functions on separate.

Also note that we can use the function valueOfCoin that we needed in our Property. People not familiar with TDD and the Test-First mindset sometimes say that they don’t like to see if the test is the only place where some functionality is used; but if you use TDD the test is the first client that will use those functionalities!

Fifth Property: Final Observation

We’re almost there; there’s just one last thing we didn’t do right in our implementation. The Kata stated that we must find “the best possible solution” for the amount in change. We now have an implementation that finds “some” solution but not the “best” solution. Why? Because we don’t use the order in which the different coin values are passed in; we just loop over them. We need the best solution for the least amount of coins.

How do we get from “some” solution to the “best” solution? Well, we need to check first with the highest coin values and then gradually to the least coin value.

How do we specify this in a Property? I must admit that it did not come to me very fast, so I think this was a good exercise in Property-Based Testing for me. This was the Property I came up with:

“Non-One Coin value is always part of the change when the amount is that Coin value”

Why do we need a non-one Coin value? Why do we need a non-empty Coin list? Because we otherwise testing an already specified property.

That’s why we use the Conditional expression: (nonOneCoin <> One && List.length coins <> 0) ==> lazy.

Now, the other part of the Property. We need to check if the given random list of coins (with a non-one Coin in it) result that the non-one Coin is part of the change we get if the amount to-be-changed is the value of the non-one Coin.

That’s seems reasonable. If I want the change the value 50 in coins and I have the Coin value 50, I want that as return value. That would be the solution if I need the least amount of coins. I don’t care if a have Coins of 50 and 25 for example, the order of the different Coin values doesn’t matter; just give me the change with the least amount of coins.

Note that we first use the Gen.shuffle function to shuffle the random list of coins with the non-One Coin. After that, we’re sure that we have a list with a non-One coin. If I would specify this condition inside the Conditional expression of FsCheck, I would have a lot of tests cases that are skipped because the condition wouldn’t be met. If I set the condition on a signal Coin value; I will have a lot more test cases.

The chance that I get a Coin that isn’t One is much higher than I get a list that contains a non-One coin I guess. But not only that; I get more Code’s Intent in my Property if I state my non-one Coin value like this I guess.

We finally pipe into the snd function that gives us the second element of the tuple so we can use it in our assertion to check if the nonOneCoin value exists in the resulted list of coins.

How do we implement this?

We sort the Coins by their Coin value. Note how we again can use the already defined valueOfCoin function.

Conclusion

As I said before: this wasn’t exactly an exercise in solving the Coin Change Kata but rather in specifying Properties to drive this implementation. I noticed that I must think on a higher level about the implementation instead of hard-coding the test values.

I don’t know which values FsCheck will provide me and that’s OK; I don’t need to know that. I just need to constrain the inputs so that I can predict the output without specifying exactly what that output should look like. Just specifying some Properties about the output.

Hopefully you found this a nice read and have enjoyed the way we write Properties in this example. Maybe now you’re inspired to write Properties for your own implementations. The full code can be found at my GitHub.

FsCheck can also be used from a C# environment instead of F# so you don’t have to be a F# expert to write Properties. It’s a concept of looking at tests and how we constrain inputs to predict outputs.

Thank you.