Skip to content

Instantly share code, notes, and snippets.

# KDCinfo/combination-coin-changer.js

Created January 16, 2018 05:10
Show Gist options
• Save KDCinfo/5bbec69b51d295b21aef8103e2b44033 to your computer and use it in GitHub Desktop.
JavaScript Combination Algorithm (determining proper coin change)
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
 // Codewars Kata [4 kyu] Vending Machine (JavaScript) // My 3-day (albeit 32-hour) Solution // Development history details at bottom. // I may be a bit slower than some, but I'm persistent :), and I pick up on many underlying nuances. // I got my (final) base model for the 'combination algorithm' from: // Code Review Stack Exchange: Answer: https://codereview.stackexchange.com/a/7042 // https://codereview.stackexchange.com/questions/7001/generating-all-combinations-of-an-array function VendingMachine(coins) { this.coins = coins; this.vendAmt = 0; for (let coin in coins) { this.vendAmt += parseInt(coin) * coins[coin]; } // This kata looked sooo much simpler than it turned out to be (4 days!?!?) } VendingMachine.prototype.vending = function(price, credit) { let credAmt = 0, balanceDue = 0, mostChangeBack = 0, returnCredit = {}; for (let cred in credit) { // Don't add if currency isn't already in the machine if (typeof(this.coins[cred]) !== 'undefined' && !isNaN(parseInt(cred, 10)) && parseInt(cred, 10) > 0) { credAmt += parseInt(cred) * credit[cred]; } } if (credAmt < price) { // Is credit less than price. returnCredit = credit; } else { // Balance owed: credAmt - price for (let cred in credit) { if (typeof(this.coins[cred]) === 'undefined') { returnCredit[cred] = credit[cred]; // Invalid key value; Give it back } else { this.coins[cred] += credit[cred]; } } balanceDue = credAmt - price; // \$ owed back let validCoins = [], validCombos = [], validComboRuns = new Map, curCombo= {'curChange': 0, 'curCoins': []}; for (var coinT in this.coins) { if (this.coins[coinT] > 0 && parseInt(coinT, 10) <= balanceDue) { let maxCoins = Math.floor(balanceDue / parseInt(coinT, 10)), maxQty = maxCoins < this.coins[coinT] ? maxCoins : this.coins[coinT]; validCoins.push(Array.from(Array(maxQty)).map( (e,i) => coinT)); } // console.log("coinT: ", coinT, this.coins[coinT]); } // Flatten inner arrays and sort in descending order (likely don't need to sort; was from initial phase). validCoins = validCoins.reduce((e,v) => e.concat(v), []).sort((a,b) => parseInt(a,10) < parseInt(b,10) ? 1 : -1); // console.log('balanceDue: ', balanceDue, validCoins); // 19 ["9", "9", "5", "5"] const powerset = (chars) => { // O(2^n) let result = []; let f = function(prefix, chars) { curCombo = {'curChange': 0, 'curCoins': []}; for (var i = 0; i < chars.length; i++) { if (result.indexOf(prefix + '-' + chars[i]) === -1) { curCombo.curChange += (prefix + '-' + chars[i]).split('-').slice(1).reduce((a,v)=>a+parseInt(v,10),0); curCombo['curCoins'] = (prefix + '-' + chars[i]).split('-').slice(1); result.push(prefix + '-' + chars[i]); if (curCombo.curChange > 0 && curCombo.curChange <= balanceDue && !validComboRuns.has(curCombo.curChange)) { validCombos.push(curCombo); validComboRuns.set(curCombo.curChange, curCombo.curCoins); } else if ( curCombo.curChange > 0 && curCombo.curChange <= balanceDue && (Math.max.apply(null, curCombo.curCoins) > Math.max.apply(null, validComboRuns.get(curCombo.curChange))) ) { // Another combination resulted in this same change, but with a higher denomination. validCombos[validCombos.findIndex(e => e.curChange === curCombo.curChange)].curCoins = curCombo.curCoins; validComboRuns.set(curCombo.curChange, curCombo.curCoins); } f(prefix + '-' + chars[i], chars.slice(i + 1)); } } } f('', chars); return result; }; powerset(validCoins); // Get ready for a winner! let winCredit = {}, winBalanceDue = balanceDue, winChange = 0; // Find out which combo is the best fit ('validCombos' is already in desc order) for (let thisComboKey in validCombos) { let thisCombo = validCombos[thisComboKey]; if (thisCombo.curChange <= winBalanceDue && thisCombo.curChange > winChange) { winCredit = thisCombo.curCoins.reduce( (a,v) => { a[v] = (typeof(a[v]) !== 'undefined') ? a[v] + 1 : 1; return a; }, {}); // { 9:1, 5:2 } winChange = thisCombo.curChange; } } balanceDue = winBalanceDue; for (var k in winCredit) { this.coins[k] -= winCredit[k]; returnCredit[k] = winCredit[k]; }; } return returnCredit; } /* Development History Details --------------------------- 2018-01-13 - Saturday -- 13+ hours @4:00 PM - Codewars - Vending Machine @2:50 AM - Thought I finally had it! {9: 2} "=== {5:2,9:1}" @3:40 AM Just found out there's another permutation I need to account for... verticals. I can't simply multiply each whole number I pass through times (*) its utmost potential quantity. I need to permutate each potential quantifiable whole number in subgroups. Now... wth did I just say??? I was doing 1(x1), 4(x2), 5(x1), 6(x3), etc. I need to do 1(x1), 4(x2), 4(x1), 5(x1), 6(x3), 6(x2), 6(x1), etc. But then there are permutations between each individual quantity permutations as well. Alright, let's try to permutate this son-gun. @5:15 AM - Flattened all the permutable values * quantities (3*3*2 === 18). - Have a flattened array of all the potential values (less any (that are) less than `balanceDue`). 2018-01-14 - Sunday -- 4 hours 201-01-15 - Monday -- 14.50 hrs @6:45 AM - Passed: 14 Failed: 3 Errors: 1 - Got the combinations down (only allowing qty * values under balanceDue (instead of all of them)) - Now it's failing on the order (higher value amts over smaller denominations; 6:1,2:1 > 4:2) @8:50 AM - Passed: 15 Failed: 2 Errors: 1 - The failure is it's still timing out. Looks like I'm gonna need another algorithm. :-| @6:30 PM - Passed: 17 Failed: 1 - Error is in last test run. Was able to recreate in CodePen. @7:05 PM - Think I figured out the issue. - Gonna need to refactor the combination algorithm to support 2-digit denominations. - Unsure why any '10'+ didn't fail...? Just caught this on a '20'. @7:40 PM - Tried converting `prefix` to an array, but browser crashed (only the 30th time today, fortunately I searched and found "&turn_off_js=true") - Gonna try to keep it as string, but identify ... what? Not sure what I can identify. Need to think on this a bit. @8:25 PM - Went back with string, but inserted '-' delimiter. Seems to be working. - Time: 477ms Passed: 18 Failed: 0 2018-01-13 - Saturday -- 13+ hours 2018-01-14 - Sunday -- 4 hours (maybe??) 201-01-15 - Monday -- 14.50 hrs === ~32 hours */
to join this conversation on GitHub. Already have an account? Sign in to comment