After having read and done Matt Hamilton's Coin Change Kata, I thought I would share one of my solutions to the kata and also some refinements to the kata itself.

I split the kata over two scenarios, the intention being that I start with the first scenario for a given language / approach and then move on to including the second scenario as I feel comfortable.

As a bit of fun I thought I'd share how I use fspec to drive out the algorithm. Fspec is a small experiment I started for writing specifications. Its very much a WIP, but I'm keen to get some feedback on its use[less|ful]ness, especially from fellow F# developers.

Goal

As per Matt's original idea, the goal is to simply return a viable set of coins or notes for a given amount. You need to return the least amount of coins or notes possible to achieve that amount.

Scenario one - basic ATM

1. Our basic ATM is only capable of dispensing $20 & $50 notes.
2. It can only accept positive integer amounts, multiples of 10, no less than $40, no greater than $2000.

Your output should be a list of tuples (denomination x qty)

E.G. in F# - For an amount of $90

[sourcecode language="fsharp"]

let result = [
(20, 2);
(50, 1);
] // two twenties and a fifty

[/sourcecode]

HINT: Perhaps start by writing a specification that ensures that a zero dollar amount returns an empty list.

Scenario Two - coping with changing requirements:

1. ATM v2 has been released and is now capable of dispensing coin change. You need to adapt your program accordingly.
2. Denominations = 0.2, 0.5, 1, 2, 5, 10, 20, 50
3. Only accept positive numbers, multiples of 0.2, no less than 0.4, and no greater than $2000.00

How I approached the problem

Here are some  specifications in F# to satisfy the first scenario. Hopefully readable enough for anybody to grok...

[sourcecode language="fsharp"]
namespace ``Concerning an automatic teller machine``

open FSpec

module ``When providing change in notes`` =
open TellerMachine.ChangeProvider

let ``it return a non result when given a zero amount``() =
getNotesFor 0 |> should.equal []

let ``it return the least amount of notes for a small amount``() =
getNotesFor 40 |> should.equal [ (20, 2); ]

let ``it return the least amount of notes for a medium amount``() =
getNotesFor 200 |> should.equal [ (50, 4) ]

let ``it return the least amount of notes for a large amount``() =
getNotesFor 1890 |> should.equal [
(20, 2);
(50, 37);
]

let ``it fail if the input is lower than $40 or lower``() =
should.failWith "Please enter a multiple of $10 no less than $40." (fun() ->
getNotesFor 30
)

let ``it fail if the input is higher than $2000``() =
should.failWith "The maximum withdrawal is $2000." (fun() ->
getNotesFor 2010
)

let ``it fail if the input is not a multiple of 10``() =
should.failWith "Please enter a multiple of $10." (fun() ->
getNotesFor 19
)
[/sourcecode]

I've also provided a possible implementation. I aimed to produce a solution that used recursion, without any mutable state...

[sourcecode language="fsharp"]
namespace TellerMachine

module ChangeProvider =
let denominations = [ 20; 50; ]

let rec calculateQuantities amount notes results =
match notes with
| [] -> results
| _ ->
let note = notes.Head
let result = (note, amount / note)
calculateQuantities
(amount % note)
(notes.Tail)
(List.Cons(result, results))

let getNotesFor (amount:int)  =
match amount with
| 0 -> []
| i when not(i % 10 = 0) ->
failwith("Please enter a multiple of $10.")
| i when i < 40 ->
failwith("Please enter a multiple of $10 no less than $40.")
| i when i > 2000 ->
failwith("The maximum withdrawal is $2000.")
| _ ->
calculateQuantities amount (denominations |> List.rev)[]
|> List.filter(fun (a, b) -> b > 0)
[/sourcecode]