Skip to content

Instantly share code, notes, and snippets.

@KDCinfo
Created January 16, 2018 05:10
Show Gist options
  • Save KDCinfo/5bbec69b51d295b21aef8103e2b44033 to your computer and use it in GitHub Desktop.
Save KDCinfo/5bbec69b51d295b21aef8103e2b44033 to your computer and use it in GitHub Desktop.
JavaScript Combination Algorithm (determining proper coin change)
// 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
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment