Last active
September 5, 2020 14:41
-
-
Save valeriyvan/4b69a78f2e4718b8cbeae596f9040ec2 to your computer and use it in GitHub Desktop.
Solution for change-making problem (a.k.a. vending machine change problem)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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]) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment