import Foundation
/// Greedy algorithm solution to the Minimum Coin Change problem.
///
/// - Parameters:
/// - value: The amount of change needed.
/// - coinDenomination: The coin denominations that are available.
/// - Returns: An array of "coins" that make up the change.
func greedyChange(for value: Int, coinDenominations: [Int]) -> [Int] {
// If value is 0 then just return an empty set (no coins).
guard value > 0 else {
return []
}
// Setup an array of coins.
var change = [Int]()
// Make a local copy of `value` so that it can be mutated.
var value = value
// Starting with the largest coin denomination, try to take as many of that coin as possible.
// When that denomination is larger than the remaining change, shift down to a smaller denomination.
for coin in coinDenominations {
while value - coin >= 0 {
change.append(coin)
value -= coin
}
}
// Return the array of coins (this is already "sorted" from largest denomination to smallest denomination).
return change
}
// A count that keeps track of the amount of recursive calls to innerDynamicChange(_:).
var recursiveCount = 0
/// Dynamic programming solution to the Minimum Coin Change problem.
///
/// - Note: What makes this "dynamic" is the cache; otherwise it is just a recursive solution.
/// With the cache the amount of recursive calls is DRASTICALLY reduced.
///
/// - Parameters:
/// - value: The amount of change needed.
/// - coinDenomination: The coin denominations that are available.
/// - useCache: If true (default) then use the cache, if false do not use the cache.
/// - Returns: An array of "coins" that make up the change.
func dynamicChange(for value: Int, coinDenominations: [Int], useCache: Bool = true) -> [Int] {
// If value is 0 then just return an empty set (no coins).
guard value > 0 else {
return []
}
// Create a cache to keep track of the coin sets for any given value.
var cache = [Int : [Int]]()
// Inner function for recursive calls.
func innerDynamicChange(for value: Int) -> [Int] {
// Count the number of times this function is called recursively.
recursiveCount += 1
// If value is 0 then just return an empty set (no coins).
guard value > 0 else {
return []
}
// If a cached value already exists then go ahead and return it; no more computation needed.
if useCache, let cached = cache[value] {
return cached
}
// Setup an array of potential coin sets.
var potentialChangeArray = [[Int]]()
// Starting with the largest coin denomination, try to take one.
// Then recursively call this function again, eventually getting the coin set with the minimum amount of coins.
for coin in coinDenominations {
// Ensure that the coin isn't too large at first.
if value - coin >= 0 {
// Setup a new potential change array with just the single coin.
var potentialChange = [coin]
// Recursively call this function again with the value reduced (by the amount of this coin) and append
// the result to the potential change array.
potentialChange.append(contentsOf: innerDynamicChange(for: value - coin))
// Append to the array of potential change sets.
potentialChangeArray.append(potentialChange)
}
}
// Get the coin set with the least amount of coins from the valid solutions.
// Note that `min(by:)` will return nil if the set is empty, hence the `if let` unwrap.
if let minimumChange = potentialChangeArray.min(by: { $0.count < $1.count }) {
cache[value] = minimumChange
return minimumChange
} else {
// If `potentialChangeArray` contains 0 elements, then return an empty array to rise up the recursive chain.
return []
}
}
// Return minimum coin change.
return innerDynamicChange(for: value)
}
// These are the "regular" U.S. coin denominations (i.e. quarter, dime, nickel, and penny).
// For the U.S. coin denominations the greedy algorithm will always work.
let usCoins = [25, 10, 5, 1]
// This is a made up set of coin denominations (maybe call them quad, tri, and uni?).
// With this set the greedy algorithm does not always give the optional solution, but the dynamic programming solution
// will always work here.
let madeUpCoins = [4, 3, 1]
// These will both give the correct solutions.
print(greedyChange(for: 99, coinDenominations: usCoins))
print(dynamicChange(for: 99, coinDenominations: usCoins))
// For this example, the greedy algorithm will give a solution that is not optimal (three coins needed).
// However, the dynamic programming solution will give the best answer (two coins needed).
print(greedyChange(for: 6, coinDenominations: madeUpCoins))
print(dynamicChange(for: 6, coinDenominations: madeUpCoins))
// This gives an example of how drastic a difference using a cache makes when solving the problem.
// With the cache the solution is that of a dynamic programming solution.
// Without the cache this is just a regular recursive solution.
recursiveCount = 0
print(dynamicChange(for: 25, coinDenominations: madeUpCoins, useCache: true))
print("With cache: \(recursiveCount)")
recursiveCount = 0
print(dynamicChange(for: 25, coinDenominations: madeUpCoins, useCache: false))
print("Without cache: \(recursiveCount)")