Exact Change wiki guide not completely correct #7289
demipixel
commented
/cc @Rafase282 and @SaintPeter
This one is lying around for a while, not sure but you are probably the best person to address whether we can take advanced solutions as this.
@demipixel I do have an idea although, which might be a win win as well not daunting for newbies.
I urge you to write a article on medium.com with this solution.
Maybe we can feature it too?
Closing for now. But feel free to comment and continue the discussion. If others agree for a better guide then please open a PR on the wiki repo.
raisedadead
closed this
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Alright, so last night I was doodling around because someone challenged me to do Exact Change and I was like "what the hell, why not", but they also challenged me to support this test case:
$0.30 with $0.50 in quarters and $0.50 in dimes
Essentially, the algorithm on the wiki does past all the tests, however a test like this does not get passed. I'm worried, however, that the correct algorithm may be a bit daunting for newcomers, so whether it really should go on the wiki is a matter of judgement for you guys. Maybe we should put it in a "bonus" section?
The issue code:
Here's the Wiki Guide
Here's my code
My code is O(money*types^2) however that is because of the score function. If that could be improved (which I think it can), it would become O(money*types). Also, in no way is my code fully optimized or pretty, however it does work against the test cases and the extra I put above.
Suppose-To-Be-Short-But-Ended-Up-Longer Summary (Read if you choose)
The algorithm splits the whole thing into sub-problems. First, it looks at how much it would take to get $0.01, which is one penny. Then it looks at $0.02 and it says "It would take one penny + how much it took to get $0.01" which is two pennies, and that get's saved. Then at $0.03 it says "It would take one penny + how much it took in $0.02". Once it gets to $0.05, there are two options. Either "one penny + $0.04" or "a nickel + $0.05". The nickel wins because of the scoring algorithm I wrote which guarantees that this latter array of coins wins. This means at $0.05 we now have a nickel. The important part to note is that if we don't have pennies (like the trick problem), then $0.00-$0.09 will be empty. When the quarter is at $0.30, it looks at $0.05 (which has a total of 0 coins) and using the scoring algorithm, 1 quarter is technically higher than 3 dimes. However, I immediately bring the score to 0 if there's 0 coins and you're not trying to access $0.00. Essentially, it thinks "quarter + $0.05" but since $0.05 has 0 coins, the score is 0. Then, when it thinks "dime + $0.20", its score is no longer 0.
Thanks for reading