Solution for change-making problem (a.k.a. vending machine change problem)

change.swift

import Foundation

// Change making problem https://en.wikipedia.org/wiki/Change-making_problem.

// Solution for change-making problem (a.k.a. vending machine change problem).

// Greedy algorythm going from bigger denominations.
// Fails for changeGreedy(60, from: [50:10, 20:10])
// More tests on bottom.

func changeGreedy(_ sum: UInt, from: [UInt: UInt]) -> [UInt: UInt]? {
    var change = [UInt: UInt]()
    var sum = sum
    from.lazy
        .sorted { $0.key > $1.key }
        .forEach { value, count in
            let give = min(count, sum / value)
            sum -= give * value
            if give > 0 {
                change[value] = give
            }
        }
    return sum == 0 ? change : nil
}

// Search with rollbacks.
// Succeeds where greedy fails.
// TODO: not guaranteed to find a way to give a change.
// TODO: Change given isn't optimal in sense of number of coins given.

func change(_ initialSum: UInt, from: [UInt: UInt]) -> [UInt: UInt]? {
    var change = [UInt: UInt]()
    var sum = initialSum
    var from = from.sorted { $0.key < $1.key }
    while !from.isEmpty {
        from
        .lazy
        .forEach { value, count in
            let give = min(count, sum / value)
            sum -= give * value
            if give > 0 {
                change[value] = give
            }
        }
        if sum == 0 {
            return change
        } else {
            from.removeLast()
            sum = initialSum
            change = [:]
        }
    }
    return nil
}

assert(changeGreedy(0, from: [100:1]) == [:])
assert(changeGreedy(50, from: [50:10]) == [50:1])
assert(changeGreedy(40, from: [50:10]) != [:])
assert(changeGreedy(60, from: [50:10, 20:10]) == [20:3]) // This assert should fire

assert(change(0, from: [100:1]) == [:])
assert(change(50, from: [50:10]) == [50:1])
assert(change(40, from: [50:10]) != [:])
assert(change(60, from: [50:10, 20:10]) == [20:3])