kodeco.com Forums

Swift Algorithm Club: June Digest 2017

The Swift Algorithm Club is happy to introduce three new algorithms this month: Minimum Coin Change, Minimum Spanning Tree, and Dijkstra's Algorithm!


This is a companion discussion topic for the original entry at https://www.raywenderlich.com/554-swift-algorithm-club-june-digest-2017

Hi, I am looking at the dynamic programming algorithm for the minimum coin problem which I feel can be improved.

First you don’t have to do recursion to do dynamic programming.

Second you can treat this particular case as a shortest path and as a data structure store as an array of what was the last coin used to reach that value.

public func noRecursion(_ value: Int) throws -> [Int] {
    
    guard value > 0 else { return [] }
    var foundMoneyValues  = Array(repeating: 0, count: value+1)
    var currentSet:[Int] = []
    
    for coin in sortedCoinSet {
        if coin < value {
            foundMoneyValues[coin] = coin
            currentSet.append(coin)
        } else if coin == value {
            return [coin]
        }
    }
    
    while !(currentSet.isEmpty) {
        var nextSet:[Int] = []
        for reachedAmount in currentSet {
            
            for coin in sortedCoinSet {
                
                let nextAmount = reachedAmount + coin
                if nextAmount < value {
                    
                    if foundMoneyValues[nextAmount] < 1 {
                        foundMoneyValues[nextAmount] = coin
                        nextSet.append(nextAmount)
                    }
                    
                } else if nextAmount == value {
                    var listOfCoinsToReturn = [coin]
                    var remaingValue = reachedAmount
                    while remaingValue > 0 {
                        let coinUsed = foundMoneyValues[remaingValue]
                        listOfCoinsToReturn.append(coinUsed)
                        remaingValue -= coinUsed
                    }
                    return listOfCoinsToReturn
                }
            }
        }
        currentSet = nextSet
        
    }
    
    throw MinimumCoinChangeError.noRestPossibleForTheGivenValue
    
}

}