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
endok total (18 cases)
test result: ok. 18 passed, 0 failed
How it’s written
Section titled “How it’s written”- 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_sizesreads that off the differences between neighbouring counts withIter.zipandIter.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
totalprices 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_pricehas an arm per discounted size and_ -> 0for the rest, a single book.- The 18 canonical cases are one
subteststable named by the description column.