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.
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
let result = [
] // two twenties and a fifty
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...
namespace ``Concerning an automatic teller machine``
module ``When providing change in notes`` =
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 [
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() ->
let ``it fail if the input is higher than $2000``() =
should.failWith "The maximum withdrawal is $2000." (fun() ->
let ``it fail if the input is not a multiple of 10``() =
should.failWith "Please enter a multiple of $10." (fun() ->
I've also provided a possible implementation. I aimed to produce a solution that used recursion, without any mutable state...
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)
(amount % note)
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)