Skip to content

Book Store

Price a basket of books from a five-book series, where each group of different titles earns a discount that grows with the group, choosing the groups that cost least.

Adapted from Exercism’s problem specification (MIT). Listed under Collections & Algorithms.

// FILE: book_store.nomi
//# The cheapest price of a basket of books from a five-book series, where
//# groups of different books get a discount.

/// The lowest price, in cents, of `basket`, a list of the books in it by
/// their number in the series, 1 to 5. The largest groups are the cheapest
/// but for one exchange: two groups of four cost less than a group of five
/// and one of three, so each such pair is priced as two fours.
pub fn total(basket: List<Int>) -> Int
    groups = group_sizes(basket)
    swaps = Int.min(groups_of(groups, 5), groups_of(groups, 3))
    saving = group_price(5) + group_price(3) - 2 * group_price(4)

    full =
        groups
        |> Iter.map(fn (size, count) -> count * group_price(size))
        |> Iter.sum()

    full - swaps * saving
end

/// How many groups of each size the largest groups make: with the copies of
/// each title counted, largest count first, as many groups of five as the
/// fifth title has copies, then groups of four for the fourth title's
/// extra copies, and so on.
fn group_sizes(basket: List<Int>) -> Map<Int, Int>
    copies =
        basket
        |> Iter.frequencies()
        |> Map.values()
        |> Iter.sort(.Descending)

    next = [..Iter.drop(copies, 1), 0]

    Iter.zip(copies, next)
    |> Iter.with_index()
    |> Iter.map(fn (index, (these, fewer)) -> (index + 1, these - fewer))
    |> Iter.to_map()
end

fn groups_of(groups: Map<Int, Int>, size: Int) -> Int
    Map.get(groups, size) |> Maybe.with_default(0)
end

/// The price, in cents, of a group of `size` different books.
fn group_price(size: Int) -> Int
    discount = case size
        2 -> 5
        3 -> 10
        4 -> 20
        5 -> 25
        _ -> 0
    end

    size * 800 * (100 - discount) / 100
end

// FILE: book_store_test.nomi
import book_store

test "total"
    [
        ("Only a single book",    [1],             800),
        ("Two of the same book",  [2, 2],          1600),
        ("Empty basket",          [],              0),
        ("Two different books",   [1, 2],          1520),
        ("Three different books", [1, 2, 3],       2160),
        ("Four different books",  [1, 2, 3, 4],    2560),
        ("Five different books",  [1, 2, 3, 4, 5], 3000),
        (
            "Two groups of four is cheaper than group of five plus group of three",
            [1, 1, 2, 2, 3, 3, 4, 5],
            5120,
        ),
        (
            "Two groups of four is cheaper than groups of five and three",
            [1, 1, 2, 3, 4, 4, 5, 5],
            5120,
        ),
        (
            "Group of four plus group of two is cheaper than two groups of three",
            [1, 1, 2, 2, 3, 4],
            4080,
        ),
        (
            "Two each of first four books and one copy each of rest",
            [1, 1, 2, 2, 3, 3, 4, 4, 5],
            5560,
        ),
        ("Two copies of each book", [1, 1, 2, 2, 3, 3, 4, 4, 5, 5], 6000),
        (
            "Three copies of first book and two each of remaining",
            [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 1],
            6800,
        ),
        (
            "Three each of first two books and two each of remaining books",
            [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 1, 2],
            7520,
        ),
        (
            "Four groups of four are cheaper than two groups each of five and three",
            [1, 1, 2, 2, 3, 3, 4, 5, 1, 1, 2, 2, 3, 3, 4, 5],
            10240,
        ),
        (
            "Check that groups of four are created properly even when there are more groups of three than groups of five",
            [1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 4, 5, 5],
            14560,
        ),
        (
            "One group of one and four is cheaper than one group of two and three",
            [1, 1, 2, 3, 4],
            3360,
        ),
        (
            "One group of one and two plus three groups of four is cheaper than one group of each size",
            [1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5],
            10000,
        ),
    ]
    |> subtests (description, basket, expected), description
        assert book_store.total(basket) == expected
    end
end
  • Prices are whole cents in Int, as the canonical data gives them. Every group’s price is a whole number of cents (5 × 800 × 75 / 100), so the integer division is exact.
  • The groups come from the copies of each title, most copies first: [6, 6, 6, 2, 2] makes two groups of five (as many as the fifth title has copies) and four groups of three (the extra copies of the first three titles). group_sizes reads that off the differences between neighbouring counts with Iter.zip and Iter.with_index.
  • Taking the largest groups is cheapest except for one exchange: a group of five and one of three cost 3000 + 2160 = 5160 cents, and two groups of four 5120. Each other exchange of one book between two groups costs more (a five and a two against a four and a three, 4520 against 4720, and so on down the table), so total prices the largest groups and takes off 40 cents for each five-and-three pair. A search over every grouping is also right, but it branches at every group it takes and needs a memo table, threaded through the recursion, to stay fast on the 22-book basket.
  • group_price has an arm per discounted size and _ -> 0 for the rest, a single book.
  • The 18 canonical cases are one subtests table named by the description column.