Skip to content

Exact Change wiki guide not completely correct #7289

Closed
demipixel opened this Issue · 2 comments

2 participants

@demipixel

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:

drawer(19.70, 20.00, [["PENNY", 0.00], ["NICKEL", 0.00], ["DIME", 0.50], ["QUARTER", 0.50], ["ONE", 0.00], ["FIVE", 0], ["TEN", 0], ["TWENTY", 0], ["ONE HUNDRED", 0]]);

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

@demipixel

Improved the code a bit. I believe it's O(money*typesOfMoney) now.

@raisedadead
Free Code Camp member

/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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.