Instantly share code, notes, and snippets.

# demipixel/change.js

Last active August 7, 2016 19:49
Show Gist options
• Save demipixel/a2737f6ae111b2139461 to your computer and use it in GitHub Desktop.
Exact Change Solution by DemiPixel
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
 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]]);