Various solutions for finding number change possibilities and minimum number of change possibilitis

Change.swift

import Foundation

//
// Description; Various solutions for finding number change possibilities and minimum number of change possibilitis.
//
// Author: Paul Ossenbruggen
// Date: Nov 8, 2015
// Updated: June 8, 2020
// Language: Swift 5.3
// See comments below for problem statement.
//
// best run in a Playground
//


// memoized class to find all the change possibilities for a particular value
class ChangePossibilities {
    
    var memo: [String: Int] = [:]
    
    func changePossibilities( amountLeft: Int, denominationsLeft: [Int]) -> Int {
        var amountLeft = amountLeft
        let memoKey = "\(amountLeft) \(denominationsLeft)"
        if let memo = memo[memoKey] {
            print(memoKey)
            return memo
        }
        if amountLeft == 0 {
            return 1
        }
        if amountLeft < 0 {
            return 0
        }
        if denominationsLeft.count == 0 {
            return 0
        }
        
        let currentCoin = denominationsLeft[0]
        let restOfCoins = Array(denominationsLeft[1..<denominationsLeft.count])
        
        var numPossibilities = 0
        while amountLeft >= 0 {
            numPossibilities += changePossibilities(amountLeft: amountLeft, denominationsLeft: restOfCoins)
            amountLeft -= currentCoin
        }
        memo[memoKey] = numPossibilities
        return numPossibilities
    }
}

ChangePossibilities().changePossibilities(amountLeft: 100, denominationsLeft: [1,5,10,25])


// Dynamic programming approach to finding all the different ways of making change.

func changePossibilities(amount : Int, denoms: [Int]) -> Int {
    var waysOfDoingN = [Int](repeating: 0, count: amount + 1)
    waysOfDoingN[0] = 1
    for coin in denoms {
        for currentAmount in coin...amount {
            let remainder = currentAmount - coin
            waysOfDoingN[currentAmount] += waysOfDoingN[remainder]
        }
    }
    return waysOfDoingN[amount]
}
changePossibilities(amount: 200, denoms: [1, 5, 10, 25])
changePossibilities(amount: 372, denoms: [1, 5, 10, 25, 50, 100])
changePossibilities(amount: 100, denoms: [1, 2, 3, 4])


// greedy approach to finding change, does not find miniumim number of coins. So may not be useful.

func numCoinsForMakingChange(value: Int, coins: [Int]) -> Int {
    var current = value
    var count = 0
    for coin in coins {
        while current - coin >= 0 {
            current -= coin
            count += 1
        }
    }
    return count
}

let usCurrency = Array(Array(arrayLiteral: 1, 5, 10, 25, 50, 100).reversed())
let value = 372
print(numCoinsForMakingChange(value: value, coins: usCurrency))

// Slow non memoized approach for finding minimum number of coins
func minNumCoinsForMakingChange(value: Int, coins: [Int]) -> Int {
    if value == 0 {
        return 0 // base case
    }
    var result = Int.max
    for coin in coins {
        if coin <= value {
            result = min(result,  minNumCoinsForMakingChange(value: value - coin, coins: coins) + 1)
        }
    }
    return result
}

print(minNumCoinsForMakingChange(value: 6, coins: [1, 3, 4] ))


// Memoized version for finding minimum number of coins

class Changer {
    var memo:[Int : Int] = [:]
    
    func minNumCoinsForMakingChangeMemo(value: Int, coins: [Int]) -> Int {
        guard memo[value] == nil else {
            return memo[value]!
        }
        if value == 0 {
            return 0 // base case
        }
        var result = Int.max
        for coin in coins {
        if coin <= value {
            result = min(result, minNumCoinsForMakingChangeMemo(value: value - coin, coins: coins) + 1)
                memo[value] = result
            }
        }
        return result
    }
}

print(Changer().minNumCoinsForMakingChangeMemo(value: 372, coins: [1, 5, 10, 25, 50, 100] ))


// Dynamic programming approach for finding minimum number of coins.

func minNumCoinsForMakingChangeDP(value: Int, coins: [Int]) -> Int {
    var results = [Int](repeating: Int.max, count: value + 1)
    results[0] = 0
    for sum in 1...value {
        for coin in coins {
            let value = sum - coin
            if value >= 0 {
                results[sum] = min(results[sum], results[value] + 1)
            }
        }
    }
    return results[value]
}
print(minNumCoinsForMakingChangeDP(value: 6, coins: [1, 3, 4] ))
print(minNumCoinsForMakingChangeDP(value: 372, coins: [1, 5, 10, 25, 50, 100] ))