Skip to content

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
end
  • The answer is dynamic programming over the amounts from 0 to the target. Iter.reduce builds a Vector whose entry at each amount is the fewest coins that make it, or None when none do; best reads the entries for amount - coin for each coin that fits, adds the coin, and keeps the shortest with Iter.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 is target × coins steps, 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 Error enum, NegativeTarget and CannotMakeTarget, rather than the canonical message strings. A negative target returns early, before the table, since 1..=target would be empty and return the 0 entry.
  • The 13 canonical cases are one subtests table named by the description column. The first error row names the enum, Err(Error.CannotMakeTarget), and the rows after it write Err(.CannotMakeTarget), so the table needs no annotation.