Change
Find the fewest coins, from an unlimited supply of given values, that add up to an amount of change.
Adapted from Exercism’s problem specification (MIT). Listed under Collections & Algorithms.
// FILE: change.nomi
//# The fewest coins that make a given amount of change.
/// Why no change can be given.
pub enum Error
NegativeTarget
CannotMakeTarget
end
/// The fewest `coins` that add up to `target`, smallest first. Each value in
/// `coins` may be used any number of times.
pub fn find_fewest_coins(coins: List<Int>, target: Int) -> Result<List<Int>, Error>
if target < 0 then return Err(.NegativeTarget)
fewest =
1..=target
|> Iter.reduce(Vector[Some([])], fn table, amount ->
Vector.push(table, best(table, coins, amount))
end)
Vector.get(fewest, target)!
|> Maybe.map(Iter.sort)
|> Maybe.to_result(.CannotMakeTarget)
end
/// The fewest coins that make `amount`, given `table`, which holds the
/// fewest coins for every smaller amount, or `None` where none make it.
fn best(table: Vector<Maybe<List<Int>>>, coins: List<Int>, amount: Int) -> Maybe<List<Int>>
coins
|> Iter.filter(&(&1 <= amount))
|> Iter.flat_map(fn coin ->
Vector.get(table, amount - coin)! |> Maybe.map(fn rest -> [coin, ..rest])
end)
|> Iter.min_by(Iter.count)
end
// FILE: change_test.nomi
import change.{self, Error}
test "find fewest coins"
[
("change for 1 cent", [1, 5, 10, 25], 1, Ok([1])),
("single coin change", [1, 5, 10, 25, 100], 25, Ok([25])),
("multiple coin change", [1, 5, 10, 25, 100], 15, Ok([5, 10])),
("change with Lilliputian Coins", [1, 4, 15, 20, 50], 23, Ok([4, 4, 15])),
("change with Lower Elbonia Coins", [1, 5, 10, 21, 25], 63, Ok([21, 21, 21])),
(
"large target values",
[1, 2, 5, 10, 20, 50, 100],
999,
Ok([2, 2, 5, 20, 20, 50, 100, 100, 100, 100, 100, 100, 100, 100, 100]),
),
(
"possible change without unit coins available",
[2, 5, 10, 20, 50],
21,
Ok([2, 2, 2, 5, 10]),
),
(
"another possible change without unit coins available",
[4, 5],
27,
Ok([4, 4, 4, 5, 5, 5]),
),
("a greedy approach is not optimal", [1, 10, 11], 20, Ok([10, 10])),
("no coins make 0 change", [1, 5, 10, 21, 25], 0, Ok([])),
(
"error testing for change smaller than the smallest of coins",
[5, 10],
3,
Err(Error.CannotMakeTarget),
),
("error if no combination can add up to target", [5, 10], 94, Err(.CannotMakeTarget)),
("cannot find negative change values", [1, 2, 5], -5, Err(.NegativeTarget)),
]
|> subtests (description, coins, target, expected), description
assert change.find_fewest_coins(coins, target) == expected
end
endok find fewest coins (13 cases)
test result: ok. 13 passed, 0 failed
How it’s written
Section titled “How it’s written”- The answer is dynamic programming over the amounts from 0 to the target.
Iter.reducebuilds aVectorwhose entry at each amount is the fewest coins that make it, orNonewhen none do;bestreads the entries foramount - coinfor each coin that fits, adds the coin, and keeps the shortest withIter.min_by(Iter.count). A greedy pass is wrong for the canonical case[1, 10, 11]making 20, and a search over combinations grows with the target; the table istarget × coinssteps, about 7,000 for the largest case. - Each entry is the coin list itself, not a count with a back pointer, so the answer needs no reconstruction pass. The lists share their tails, since each is a coin consed onto an earlier entry.
- The answer is sorted at the end with
Iter.sort, smallest coin first, as the canonical data lists it. - The two canonical errors are an
Errorenum,NegativeTargetandCannotMakeTarget, rather than the canonical message strings. A negative target returns early, before the table, since1..=targetwould be empty and return the 0 entry. - The 13 canonical cases are one
subteststable named by the description column. The first error row names the enum,Err(Error.CannotMakeTarget), and the rows after it writeErr(.CannotMakeTarget), so the table needs no annotation.