Potter Kata

Yesterday evening I was running Arolla’s Code Jam, and I suggested that we practice on the Potter Kata. This kata is a tricky one, which seems pretty simple at first, but shows its challenges after a few minutes, and it is very easy to get it wrong. In order to prepare the Jam and improve my level in F#, I practiced the kata this week, and I wanted to share my thoughts about it.

You can read the original problem description on codingdojo.org. I’ll just recap the pricing rules here for reference:

The rules are then followed by some clues:

You’ll find that this Kata is easy at the start. You can get going with tests for baskets of 0 books, 1 book, 2 identical books, 2 different books… and it is not too difficult to work in small steps and gradually introduce complexity.

However, the twist becomes apparent when you sit down and work out how much you think the sample basket above should cost. It isn’t 5*8*0.75+3*8*0.90. It is in fact 4*8*0.8+4*8*0.8. So the trick with this Kata is not that the acceptance test you’ve been given is wrong. The trick is that you have to write some code that is intelligent enough to notice that two sets of four books is cheaper than a set of five and a set of three.

You will have to introduce a certain amount of clever optimization algorithm. But not too much! This problem does not require a fully-fledged general purpose optimizer. Try to solve just this problem well in order to share it. Trust that you can generalize and improve your solution if and when new requirements come along.

It is clear here that the goal of this kata is not to write a general-purpose solver. I must agree that a general-purpose solver is not the best solution to the problem, as most probably You Aren’t Gonna Need It.

So I first tackled the kata, trying to do the bare minimum required to handle the requirements. In F#, my implementation goes down to 20 lines of code. The trick is that a greedy grouping of books (the “most intuitive” solution) is correct, except for the corner case where a group of 5 five books and a group of 3 books is actually more expensive than two groups of 4 books.

Disclaimer: I’m going to show an implementation of the kata here. If you’ve never tried it before, I suggest that you practice on your own first, because the solution in itself is really not as valuable as the path to get there.

I’ll use some of the test cases provided in the original kata, plus the ones we came up with last night. In F#, I get these kinds of tests:

[<TestMethod>]
member x.``1 book (each kind)`` () = 
    Assert.AreEqual(8.0M, price [1])
    Assert.AreEqual(8.0M, price [2])
    Assert.AreEqual(8.0M, price [3])
    Assert.AreEqual(8.0M, price [4])
    Assert.AreEqual(8.0M, price [5])

[<TestMethod>]
member x.``2 same books`` () = 
    Assert.AreEqual(16.0M, price [1;1])
    Assert.AreEqual(24.0M, price [2;2;2])

[<TestMethod>]
member x.``2 distinct books`` () = 
    Assert.AreEqual(15.2M, price [1;2])

[<TestMethod>]
member x.``3 distinct books`` () = 
    Assert.AreEqual(21.6M, price [1;2;3])

[<TestMethod>]
member x.``4 distinct books`` () = 
    Assert.AreEqual(25.6M, price [1;2;3;4])

[<TestMethod>]
member x.``5 distinct books`` () = 
    Assert.AreEqual(30.0M, price [1;2;3;4;5])

[<TestMethod>]
member x.``Simple discount`` () = 
    Assert.AreEqual(29.6M, price [1;2;1;3])

If we read the test cases carefully, nothing forces us to have a notion of “discount” in our implementation. In fact, pricing a group of distinct books is almost a single-liner:

let priceGroup = function | 1 -> 8.0M | 2 -> 15.2M | 3 -> 21.6M
                          | 4 -> 25.6M | 5 -> 30.0M | _ -> failwith "What ? A 6th book ?"

Now, this obviously doesn’t work when we try to buy the same book more than once. In order to consume the previously defined function, we have to build groups of books. A greedy grouping seems accurate at first:

let greedyGroup books = 
    // we count how many books there are of each type and sort them
    let types = books |> Seq.countBy id |> Seq.map snd |> Seq.sort |> Seq.toList
    // then we recursively compute how many groups of books we can build
    let rec countGroups types used =
        match types with
        | [] -> []
        | head :: tail -> head - used :: countGroups tail head
    countGroups types 0 |> List.rev

I’m pretty happy with function. The first expression get en ordered list from the books: a list of books [1;1;2;2;3;4] produces a list of of types of books [1;1;2;2], that can be read as “a type with a single book, a type with a single book, a type with 2 books, a type with 2 books”. The recursive function counts how many groups of distinct books can be built from these type. Here, the output is [0;1;0;1] which means “0 group of 1 books, 1 group of 2 books, 0 group of 3 books, 1 group of 4 books”.

Now, we combine our functions into a price function:

let price books =
    books
    |> greedyGroup
    |> Seq.mapi (fun i nb -> priceGroup (i+1) * decimal nb)
    |> Seq.sum

We’re almost there. This code is incorrect for the edge case we identified before. But do we have to break everything and build a general-purpose solver? No. We just have to handle the edge case and adjust the grouping:

let adjust = function 
    | [a; b; c; d; e] ->
        let shift = min c e
        [a; b; c-shift; d+2*shift; e-shift]
    | l -> l

Basically, this adjust function replaces every pair of 5 distinct books and 3 distinct books by a 2 groups of 4 distinct books, which are cheaper.

Finally, the pricing function with the adjustment becomes:

let price books =
    books
    |> greedyGroup
    |> adjust
    |> Seq.mapi (fun i nb -> priceGroup (i+1) * decimal nb)
    |> Seq.sum

And that’s done.

Bonus: F# brings you such a nice type inference that without changing any line in my previous code, I can use the book titles instead of their numbers (or anything that has equality comparison!).

let test_generic_1 = price ["Harry Potter and the Philosopher's Stone";
                            "Harry Potter and the Chamber of Secrets";
                            "Harry Potter and the Prisoner of Azkaban";
                            "Harry goes to Hollywood";
                            "Harry Rabienkirira - ledernier"]

let test_generic_2 = price [typedefof<System.Collections.ArrayList>;
                            typedefof<System.String>;
                            typedefof<System.Int32>]

Of course, building a general purpose solver for the same problem is too appealing to be ignored. That will be the subject of the next post, featuring tail-recursion and memoization!

(For those of you who wonder where the “Pattern-matching” series has gone, it’s coming back soon)