Flagrant Badassery

A JavaScript and regular expression centric blog

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?

There Are 19 Responses So Far. »

  1. 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.

  2. 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];

  3. 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 [...]

  4. 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.

  5. 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)

  6. 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(", ");
}

  7. 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 coins child arrays to e.g. ['penny','pennies',1], because then you could change the plurality selector from coins[i][num > 1 ? 2 : 1] to coins[i][num > 1].

  8. 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)

  9. 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)]

  10. 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.

  11. 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).

  12. Comment by mark on 23 June 2008:

    This is way faster than using math.Floor:
    num = ( money / coins[i][0] ) >> 0;

  13. Comment by Maurice Schoenmakers on 23 June 2008:

    Well my proposal is here.. :-)

    http://serious-javascript.blogspot.com/2008/06/code-challenge.html

  14. 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"

  15. 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:

    var result = makeChange(37, [100, 25, 10, 5, 1]);
alert(result[0]); // alerts [,1,1,,2]

    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.

  16. Pingback by atm machine problem on 9 July 2008:

    [...] Simple illustrative solution to the ATM machine problem, in response to this. [...]

  17. 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);

  18. Comment by mark on 1 August 2008:

    @g You used cents :) thats way easier, but just smart, I guess.

  19. 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..

Post a Response

If you are about to post code, please escape your HTML entities (&amp;, &gt;, &lt;).