Skip to content

Instantly share code, notes, and snippets.

@demipixel
Last active August 7, 2016 19:49
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save demipixel/a2737f6ae111b2139461 to your computer and use it in GitHub Desktop.
Save demipixel/a2737f6ae111b2139461 to your computer and use it in GitHub Desktop.
Exact Change Solution by DemiPixel
function drawer(price, cash, cid) { // cid == denominations array
price *= 100; cash *= 100; // Convert to pennies
// Really we're just trying to get the coins for cash-price
var vals = [1,5,10,25,100,500,1000,2000,10000]; // How much each denomation is worth (in pennies)
var cidHave = cid.map(x=>Math.round(x[1]*100)); // Convert each denomination we have into pennies (e.g. $1.05 in nickels to 105)
var cidAmts = cidHave.map((x,i)=>Math.floor(x/vals[i])); // e.g. 105 pennies worth in nickels to 21 nickels or 20000 pennies worth in quarters to 80 quarters
var best = [[0,0,0,0,0,0,0,0,0]]; // Start with $0.00 = 0 of each coin
var bestScoreList = [0]; // # of coins for $0.00 is 0
for (var i = 1; i <= cash-price; i++) { // For $0.00 to amt
best[i] = [...Array(cid.length)].map(x=>0); // Empty array of denominations
var bestScore = i+1; // Start just above the max amount in coins (all pennies + 1)
for (var c = 0; c < cid.length; c++) { // For each denomination
if (vals[c] > i || best[i-vals[c]][c] >= cidAmts[c]) continue; // If denomination is too high or we don't have enough, continue
var bestIndex = i-vals[c]; // Index in "best" of the lower coin we're accessing. (e.g. dime and $0.25 would give $0.15 or index 15)
var score = 0;
if (bestScoreList[bestIndex] != 0 || bestIndex == 0) { // Make sure we don't have bestScore[bestIndex] being 0 coins AND bestIndex not being $0.00
score = bestScoreList[bestIndex]+1; // We're adding a coin... this denomation
}
if (score < bestScore) { // Better score than another denomation? Heck yeah, change it!
bestScore = score;
best[i] = best[bestIndex].slice(0);
best[i][c] += 1;
}
}
bestScoreList[i] = bestScore; // Set best score and continue to next iteration
}
// "finish" converts it to the correct format (name and into dollars) in highest to lowerest denomination, e.g. [["QUARTER", 1.25], ["DIME", 0.3]]
var finish = best[cash-price].map((x,i)=>{ return [cid[i][0], x*vals[i]/100]; }).filter(x=>x[1]!=0).reverse();
if (!finish.length) return 'Insufficient Funds'; // Make sure we have coins
else if (finish.reduce((a,b)=>a+b[1],0) == cidHave.reduce((a,b)=>a+b/100, 0)) return 'Closed'; // Can't be left with no coins (for some reason, I didn't design the problem)
else return finish; // Yes!!
}
// Example of $0.30 with dimes and quarters
drawer(19.70, 20.00, [["PENNY", 0], ["NICKEL", 0], ["DIME", 0.50], ["QUARTER", 0.50], ["ONE", 0], ["FIVE", 0], ["TEN", 0], ["TWENTY", 0], ["ONE HUNDRED", 0]]);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment