Code Challenge: Change Dispenser
Friday, June 20th, 2008 • Related • Filed Under
I recently encountered a brain teaser that asked to take an amount of change and return the equivalent in dollars and coins.
Here's the five-minute solution I first came up with.
function makeChange (money) {
var i, num,
output = [],
coins = [
[100, "dollar", "dollars" ],
[25, "quarter", "quarters"],
[10, "dime", "dimes" ],
[5, "nickel", "nickels" ],
[1, "penny", "pennies" ]
];
money = money * 100; // avoid float precision issues
for (i = 0; i < coins.length; i++) {
num = Math.floor(money / coins[i][0]);
money -= num * coins[i][0];
if (num) {
output.push(num + " " + coins[i][num > 1 ? 2 : 1]);
}
}
return output.join(", ");
}
makeChange(0.37); // "1 quarter, 1 dime, 2 pennies"
I feel like I'm missing something, though. How would you improve this code to make it shorter, faster, or otherwise better?
Comment by DrSlump on 20 June 2008:
That’s the typical way I’ve seen these problems solved, like the ‘6 days 3 hours and 10 minutes ago’ style for dates.
I’ve been thinking a bit about it and I can’t think of any other way which doesn’t involve unrolling the loop.
Comment by DrSlump on 20 June 2008:
Well, the only minor improvement I can see is changing:
money -= num * coins[i][0];
for:
money %= coins[i][0];
Pingback by Darkness Productions’ Blog » Code Challenge: Change Dispenser on 20 June 2008:
[…] Flagrant Badassery blog posted a code challenge: make a javascript function, that displays the amount of change needed, in ‘text’. I […]
Comment by Rafael on 20 June 2008:
I also didn’t find a better way to do this. My improvement would be to replace Math.floor with
num = money / coins[i][0]|0;which seems to be a little faster. For positive numbers, both operations are equal.
Comment by Marc on 20 June 2008:
I’m not sure but I’m seeing an option of having the coins array being passed to the function and the function calling itself recursively.
That way you can pass different coin collections.
I’m not sure if that would be faster though…
(Oh… and I also would go with the modulus operator)
Comment by Travis Parker on 20 June 2008:
I don’t know how I did it, but I convinced myself that a recursive approach was a good idea. It was fun at least.
var coins = [ [100, 'dollar', 'dollars'], [25, 'quarter', 'quarters'], [10, 'dime', 'dimes'], [5, 'nickel', 'nickels'], [1, 'penny', 'pennies'] ]; function checkCoin(change, coin, accum) { if (coin >= coins.length) { return accum; } var num = Math.floor(change / coins[coin][0]); if (num) { accum.push(num + " " + coins[coin][num > 0 ? 2 : 1]); } return checkCoin(change % coins[coin][0], coin + 1, accum); } function makeChange(money) { return checkCoin(money * 100, 0, []).join(", "); }Comment by Steven Levithan on 20 June 2008:
@Travis Parker, it had to be done. 🙂
Nice tweaks, people. I guess I wasn’t too far off mark. You could also save a few characters by changing the order of the
coinschild arrays to e.g.['penny','pennies',1], because then you could change the plurality selector fromcoins[i][num > 1 ? 2 : 1]tocoins[i][num > 1].Comment by Da Scritch on 21 June 2008:
«
– Le compte est bon
– Pas mieux
»
(from “Des chiffres et des lettres”, original french game known as “coutdown” in UK)
Comment by Travis Parker on 21 June 2008:
careful with that different plurality selector – quick check with firebug console shows [‘f’, ‘t’][5 > 3] is undefined. Unfortunately it needs some extra coercion: [‘f’, ‘t’][Number(5 > 3)]
Comment by Steven Levithan on 21 June 2008:
Oh yeah, duh, it will try to access the “true” or “false” properties of the array unless you convert the boolean to a number. Thanks for correcting that.
Comment by Yoan on 22 June 2008:
The Ruby Quiz asked this question some months ago: http://rubyquiz.com/quiz154.html
I ended up with a min-max with alpha-beta pruning-like algorithm (except that you only have to care about the alpha and forget the beta).
Comment by mark on 23 June 2008:
This is way faster than using math.Floor:
num = ( money / coins[i][0] ) >> 0;
Comment by Maurice Schoenmakers on 23 June 2008:
Well my proposal is here.. 🙂
http://serious-javascript.blogspot.com/2008/06/code-challenge.html
Comment by mark on 24 June 2008:
I just give it a try. It isn’t very dynamic anymore but its shorter/faster 🙂
function makeChange(m) { var i x=[] c=[[100,"dollar"],[25,"quarter"],[10,"dime"],[5,"nickel"],[1,"penn"]] m*=100 for(i=0;i<5;i++){ p=c[i] n=m/p[0]>>0 m-=n*p[0] if(n)x.push(n+" "+p[1]+(n>1?(i<4?"s":"ies"):(i<4?"":"y"))) } return x.join(", ") } alert(makeChange(0.37)); // "1 quarter, 1 dime, 2 pennies"Comment by russ on 7 July 2008:
Here is an example of a general solution to what i call the atm machine problem. Formatted for readability, not speed. It basically separates the solution from any particular problem. Its not shorter or faster, but i believe its ‘better’ in the sense that it allows you to solve the problem in a real world situation. What happens if you dont have enought quarters? What would be the next solution?
function makeChange(n, kArray) { var s; function possible(n, i, solution) { if(n == 0) return result.push(solution); if(n > 0 && i < kArray.length) { s = solution.concat(); s[i] = s[i] ? s[i] + 1 : 1; possible(n - kArray[i], i, s); if(++i < kArray.length) possible(n, i, solution); } } var result = new Array(); possible(n, 0, []); return result; }To solve your particular problem:
This tells us that to solve our problem we should give the user 1×25,1×10, and 2×1.
The result has a length of 24 (so theres 24 possible solutions) which you can enumerate incase you dont have some of the required change – i.e. if you ‘machine’ is out of quarters just loop the results until you have a solution that doesn’t use them.
Results are in order of least amount of change to greatest amount.
For speed i would try to replace recursion with looping.
Pingback by atm machine problem on 9 July 2008:
[…] Simple illustrative solution to the ATM machine problem, in response to this. […]
Comment by g on 29 July 2008:
function changer(amt) { var coins = {100:'Dollar',25:'Quarter',10:'Dime',5:'Nickel',1:'Cent'}; var money = []; amt = amt * 100; for(var coin in coins) { var num = (amt / coin >> 0); if(num>0) money.push(num + " " + coins[coin] + (num>1?"s":"")); amt -= num * coin; } return money.join(", "); } changer(2.68);Comment by mark on 1 August 2008:
@g You used cents 🙂 thats way easier, but just smart, I guess.
Comment by Jannah on 6 August 2008:
hi, im jannah from philippines. please help me guys. all i need is a java code for change… please help me.. thanks a lot..
Comment by Jack on 30 December 2008:
This is coming in a bit late, but this is a well-known CS problem. The easiest solution involves using a greedy algorithm, but it may not yield the optimum solution (the least # of coins). The best solution involves dynamic programming which will always yield the optimum solution.
Comment by Jack on 30 December 2008:
Should be noted that for American coins greedy yields the optimum solution, but in general it doesn’t.
Comment by Ben on 19 January 2009:
“for(i=0;i>0
m-=n*p[0]
if(n)x.push(n+” “+p[1]+(n>1?(i<4?”s”:”ies”):(i<4?””:”y”)))
}”
Good lord, if I had a programmer give me code like that I’d beat them senseless.
Comment by David on 29 April 2009:
Ha, Ben, I completely agree — code should be formatted for human-readability and maintenance, not brevity/number of characters… Gave me a headache just looking at that solution.
Comment by John Vivenzio on 1 May 2009:
Here’s a quick 2 line recursive I threw together… in the name of silly frugality – I just put the names that won’t take an ‘s’ in the [2] part of the array. : )
var n = [
[10000, “Hundred”],
[ 5000, “Fifty”, “Fifties”],
[ 2000, “Twenty”, “Twenties”],
[ 1000, “Ten”],
[ 500, “Five”],
[ 200, “Two”],
[ 100, “Dollar”],
[ 25, “quarter”],
[ 10, “dime”],
[ 5, “nickel”],
[ 1, “penny”, “pennies”],
[ 0]
];
var output = [];
var i = 0, x = 0;
function makeChange(money) {
if (x = Math.floor(money / n[i][0]))
output.push(x + ” ” + (x <= 1 ? n[i][1] : !n[i][2] ? n[i][1] + “s” : n[i][2]));
return isNaN(n[i + 1]) ? makeChange(money % n[i++][0]) : output;
}
makeChange(123279.96 * 100).join(“\n”);
Comment by John Vivenzio on 1 May 2009:
Didn’t think about that but just saw the ATM problem – that can be solved by running a checkInventory(array) on the array which nulls out or flags any change not available (in the above recursive) so the algorithm is easily adaptable.
-John
Comment by John Vivenzio on 1 May 2009:
Looking at the length of the other solutions around on here and the web (didn’t see them before and never realized this is a famous problem) I think that code I just posted is
(c) 2009, John Vivenzio, All Rights Reserved
LOL
Great blog by the way!
Comment by John Vivenzio on 2 May 2009:
Last One… with inventory of bills and coins and shows remainder if can’t make exact change.
var b = [
// checkInventory to null out what’s not available (on hand is b[i][1])
[10000, 0, “Hundred”],
[ 5000, 1, “Fifty”, “Fifties”],
[ 2000, 0, “Twenty”, “Twenties”],
[ 1000, 0, “Ten”],
[ 500, 0, “Five”],
[ 200, 0, “Two”],
[ 100, 0, “Dollar”],
[ 25, 0, “quarter”],
[ 10, 0, “dime”],
[ 5, 0, “nickel”],
[ 1, 0, “penny”, “pennies”],
[ 0]
];
function makeChange(money) {
if (b[i][1] && (x = Math.floor(money / b[i][0])))
output.push(x + ” ” + (x <= 1 ? b[i][2] : !b[i][3] ? b[i][2] + “s” : b[i][3]));
return isNaN(b[i + 1]) ? makeChange(b[i][1] ? money % b[i++][0] : (i++, money)) :
output.push(“Remainder: $” + money / 100), output;
}
makeChange(123279.96 * 100).join(“\n”);
Comment by John Vivenzio on 2 May 2009:
Obscure bug?
When testing just now I found if you enter makeChange(279.96 * 100) – it rounds to 27995.9999 when multiplied by 100 – very bizarre. …using Firefox 3.5b4 – reminds me of the Pentium 59.999… days.
Comment by Prestaul on 8 March 2011:
Does shorter and no “var” statements == better? Probably not, but it was fun to slap together and I enjoy taking advantage of array methods whenever possible.
function makeChange(money) {
return [
[100, ‘dollar’],
[25, ‘quarter’],
[10, ‘dime’],
[5, ‘nickel’],
[1, ‘penny’, ‘pennies’]
].reduce(function(state, coin, cnt) {
if(cnt = (state.amount / coin[0]) ^ 0) {
state.change.push(cnt + ‘ ‘ + (cnt > 1 ? coin[2] || coin[1] + ‘s’ : coin[1]));
state.amount %= coin[0];
}
return state;
}, { amount: money * 100, change: [] }).change.join(‘, ‘);
}
Comment by NEX-C3 on 17 November 2011:
I’m impressed!!! Really informative blog post here my friend. I just wanted to comment u0026 say keep up the quality work.
Comment by lawrence on 13 December 2011:
i used the top method and it worked. thank you, i have been looking for this html code for a while.
Comment by Family History Oz on 3 May 2014:
The backend part of your company supports these profit centers.
In addition, many of the words used started to take on
slightly different meanings, depending on the context in which they are used.
The Unit is powered by the Main chip adopting the CORTEX A8 core Sam – Sung
S5PV210,and CPU frequency up to 1GHz, Memory
512MB, internal 2G memory space for TV and Internet integration.