The purpose of this post is to show how a code is written with respect of the Test Driven Development using the Kotlin language and a functionnal approach. This kata is about applying discount on books according to the number of different kinds of book. You can find the description of this kata here.

From the void

We start with no code and only an unit test :

@Test
fun `price of one book`() {
    val price = computePrice(listOf(Pair(1, Tome1)))

    assertEquals(8.0, price)
}

Obviously, we got compilation errors ; let’s fix them with the simplest possible code :

fun computePrice(books: List<Pair<Int, BookId>>): Double = 0.0

enum class
BookId {
    Tome1, Tome2, Tome3, Tome4, Tome5
}

Now, the test fails. Good, always start with the red bar and write the minimum code to get the green bar :

fun computePrice(books: List<Pair<Int, BookId>>): Double = 8.0

Too easy and even sligthly stupid ! Thus, let’s add another test.

@Test
fun `price of the two same books`() {
    val price = computePrice(listOf(Pair(2, Tome1)))

    assertEquals(16.0, price)
}

Red bar, fix code, green bar, that’s the mantra of the Test Driven Development (TDD). Red. Try :

fun computePrice(books: List<Pair<Int, BookId>>): Double = 8.0 * books.size

Red again, try :

fun computePrice(books: List<Pair<Int, BookId>>): Double =
    books.map { it.first * 8.0 }.sum()

Green ! Don’t forget the edge case test :

@Test
fun `price of no book`() {
    val price = computePrice(listOf())

    assertEquals(0.0, price)
}

Discount

This new test failed :

@Test
fun `price of 2 different books`() {
    val price = computePrice(listOf(Pair(1, Tome1), Pair(1, Tome2)))

    assertEquals(16.0 * 0.95, price)

A new function will compute the discount to apply :

fun getDiscount(books: List<Pair<Int, BookId>>) : Double =
    when (books.size) {
        2 -> 0.95
        else -> 1.0
    }

Note about Kotlin : I use the when keyword as an expression and not as an instruction so that the Kotlin compiler can check the completeness of the cases inside the when. So the else branch is mandatory otherwise it’s a compilation error. Note about the approach : I haven’t written the other discount cases (3 books …) because the code must be written after a test has been written, ran and failed. Only after that, we are allowed to modify or write code in order to process a new use case, even a tiny instruction or expression ! By using the discount function, all the tests are green :

fun computePrice(books: List<Pair<Int, BookId>>): Double =
    books.map { it.first * 8.0 }.sum() * getDiscount(books)

Next, the others use case are added in the same way :

@Test
fun `price of 3 different books`() {
    val price = computePrice(
        listOf(
            Pair(1, Tome1), Pair(1, Tome2), Pair(1, Tome3)
        )
    )

    assertEquals(8.0 * 3 * 0.9, price)
}

Note : in the assertion, instead of putting the expected price, an explicit formula is used to facilite the understanding of the expected result.

Time to think a little

When we add a more complex use case, the result is not as expected :

    @Test
    fun `price of 2 same books and another different one`() {
        val price = computePrice(listOf(Pair(2, Tome1), Pair(1, Tome2)))

        assertEquals(8.0 + 8.0 * 2 * 0.95, price)
    }
}

The actual value is less than the expected one. Why ? Because the discount is applied on the total of books. In fact there are two axis : the number of kinds of book and the number of books given a kind of book. As the focus of the first tests is on the simplest use cases, these tests only check the computation regarding an axis. When the new test comes in play, the two axis must be concerned. Does it mean that all the code written is no more useful and we need to rewrite it ? What a waste of time ! No. First of all, we have some tests acting as no-regression tests. Furthermore the code is very simple and has been written in few minutes. Delete it should not be a problem. And it give use some clues on how we can rewrite it to color all tests in green ! Also, perhaps some parts of code can be reused or refactored. So, according to the tests, the expression in computePrice is correct when there is only one kind of book containing at least one book. On the other hand, the expression is also correct when there are one or more kinds of book with only one book. Conclusion : the initial list books must be splitted in subsets on which the computePrice function will be applied ; the sum of all these results give the expected result. Let’s define a new class Group which encapsulates a subset of books and move the getDiscount function inside this class :

class Group(val books: List<Pair<Int, BookId>>) {
    fun getDiscount() : Double =
        when (books.size) {
            2 -> 0.95
            3 -> 0.9
            4 -> 0.8
            5 -> 0.75
            else -> 1.0
        }
}

The price is calculated on each group :

fun computePrice(books: List<Pair<Int, BookId>>): Double {
    val groups: List<Group> = buildGroups(books)
    return groups.map {
        it.books.map {
            it.first * 8.0
        }.sum() * it.getDiscount()
    }.sum()
}

Split a list of books either in a list with 1 or more books of a uniq kind of book or a list of 1 book for each kind of book. Traditionnaly a recursive function is used : the biggest (in term of kind of book) group is built by picking a book in each kind of book and the remaining books in the initial list is passed to the recursive call. Note that there is no variable, no modification, no side effect.

fun buildGroups(books: List<Pair<Int, BookId>>): List<Group> {
    if (books.size <= 1)
        return books.map { Group(listOf(it)) }
    val newBooks = books.flatMap {
        if (it.first == 1) {
            listOf()
        } else
            listOf(Pair(it.first - 1, it.second))
    }
    val group = Group(books.map { Pair(1, it.second) })
    return listOf(group) + buildGroups(newBooks)
}

Three more tests :

@Test
fun `price of 3 same books and another different one`() {
    val price = computePrice(listOf(Pair(3, Tome1), Pair(1, Tome2)))

    assertEquals(8.0 * 2 + 8.0 * 2 * 0.95, price)
}

@Test
fun `price of 2 books of a kind and 2 books on another one`() {
    val price = computePrice(listOf(Pair(2, Tome1), Pair(2, Tome2)))

    assertEquals(2 * 8.0 * 2 * 0.95, price)
}

@Test
fun `price of 1 of the first kind 2 of the second one and 3 of the third one`() {
    val price = computePrice(listOf(Pair(1, Tome1), Pair(2, Tome2), Pair(3, Tome3)))

    assertEquals(8.0 * 3 * 0.90 + 8.0 * 2 * 0.95 + 8.0, price)
}

Right, all tests are green.

Refactoring

Hide the implementation.

typealias BookQuantity = Pair<Int, BookId>

Add constraints so that only valid group of objects can be created. First, by using a sealed class a group can no more be built directly with a list of pairs because only subclasses can be instancied. More over, the hierarchy can’t be extended outside the file. In this base class, the internal representation is made hidden and two new public properties are added.

sealed class Group(private val bookQuantities: List<Pair<Int, BookId>>) {
    val numberOfBook = bookQuantities.sumBy { it.first }
    val numberOfDifferentBook = bookQuantities.size
}

and secondly, by defining 2 subclasses for 2 possible kinds of group :

class GroupSameBook(count: Int, bookId: BookId) : Group(listOf(Pair(count, bookId))) {
    constructor(pair: Pair<Int, BookId>) : this(pair.first, pair.second)
}

class GroupDifferentBook(vararg bookIds: BookId) : Group(bookIds.map { Pair(1, it) }) {
    constructor(bookIds: List<BookId>) : this(*bookIds.toTypedArray())
}

Make the code more self-documented. At first glance, it’s no obvious how the computePrice function do to compute the price : there are two nested maps and so two sum function calls ; also, the use of the internal representation of a group (books, first) doesn’t help to understand the code quickly. Compare with the new refactored method below :

fun computePrice(bookQuantities: List<BookQuantity>): Double =
    buildGroups(bookQuantities).map { group: Group ->
        group.numberOfBook * 8.0 * getDiscount(group.numberOfDifferentBook)
    }.sum()

Note that the method getDiscount no longer belongs to the Group class (single responsability principle) and the semantic is now explicit by changing the parameter : no comment is needed.

fun getDiscount(numberOfDifferentBook: Int): Double =
    when (numberOfDifferentBook) {
        2 -> 0.95
        3 -> 0.9
        4 -> 0.8
        5 -> 0.75
        else -> 1.0
    }

As for computePrice function, the buildGroups needs a refactoring to be more readable. Apart using the type alias and the group subclasses, the process of pick a book in each kind of book, decrease its  counter and remove a group with no remaining book is made more explicit by the use of some declarations and many helper functions to hide the implementation and auto-document the code :

fun buildGroups(bookQuantities: List<BookQuantity>): List<Group> =
    if (bookQuantities.size <= 1) {
        bookQuantities.map { GroupSameBook(it) }
    } else {
        val selectedBooks = selectBooks(bookQuantities)
        val remainingBookQuantities = bookQuantities
            .map { if (it isIn selectedBooks) removeOne(it) else it }
            .filter(BookQuantity::notEmpty)
        listOf(GroupDifferentBook(selectedBooks)) + buildGroups(remainingBookQuantities)
    }

private fun selectBooks(books: List<Pair<Int, BookId>>) = books.map { it.second }
private fun removeOne(pair: Pair<Int, BookId>) = Pair(pair.first - 1, pair.second)
private infix fun Pair<Int, BookId>.isIn(bookIds: List<BookId>) = bookIds.contains(this.second)
private fun BookQuantity.notEmpty() = this.first > 0

Needless to say that every change during the refactoring must not break the tests. Green bar, always !

The return of the red bar

Is it the end ? No. The goal is to compute the best discount for a set of books. And a new test shows that is not the case.

computePrice(listOf(Pair(2, Tome1), Pair(2, Tome2),Pair(2, Tome3), Pair(1, Tome4), Pair(1, Tome5)))

The result is 51.6 with 2 groups :  {Tome1, Tome2, Tome3, Tome4, Tome5} and {Tome1, Tome2, Tome3} that give 5 * 8 * 0.75 + 3 * 8 * 0.9 = 51.6 But there is a better solution, for example : {Tome1, Tome2, Tome3, Tome4} and {Tome1, Tome2, Tome3, Tome5} that give 4 * 8 * 0.8 + 4 * 8 * 0.8 = 51.2 We use a greedy algorithm that makes locally optimal choice by building a group with the highest discount namely a group with the more different kinds of book. Depending on the discount values, this is not always the optimal overall solution, it’s just a heuristic. We need a new algorithm may be by trying all solutions. To be continued …