JavaScript Challenge: Dispense Change

posted by Jonah Dempcy

This challenge is to write a function that takes an amount of change and returns a String Array with the coins to dispense.

Examples:

.25 returns ['quarter']
.26 returns ['quarter', 'penny']
.30 returns ['quarter', 'nickel']
1.01 returns ['dollar', 'penny']
1.16 returns ['dollar', 'dime', 'nickel', 'penny']

One of the requirements is that this returns the least amount of units of currency as possible. In other words, you can't return 100 pennies or even 4 quarters when 1 dollar would suffice. This is modeled after how real-life vending machines work.

Land of the Vending Machines By gullevek

If you want to attempt to solve this challenge yourself, read no further! The rest of the article will go on to describe my solution to this problem and some of the issues I encountered along the way.

Using MooTools' round() Method

I originally wrote my solution to this challenge without the use of JavaScript libraries. However, I ran into a common problem when dealing with dollar values, which is that I needed to round them to the 2nd decimal place. Without rounding to the 2nd place, you end up with subtle flaws in the data.

For instance, I was using an if() statement to check if the change remaining to dispense is greater than or equal to 0.1 (one cent). Before I added the code to round to the 2nd decimal place, the if() statement wouldn't evaluate to true when there should be a penny left to dispense. The change remaining should have been .1, but it wasn't entering the if(changeToDispense >= 0.1) statement. How could this be? Well, I was subtracting the change, but upon closer inspection, some of the values were not what I expected. When I subtract .25 from .48, I ended up with 0.22999999999999998 for instance.

Of course, I should have ended up with 0.23, not .022999 (repeating). But, without rounding the number, it ended up slightly less than the correct amount, introducing subtle bugs into the code. Since the full amount wasn't being subtracted, the last penny would never be dispensed because there wasn't a whole penny left (it was something like 0.09999999999999998). Thus, I rounded to the second decimal place and it solved the problem.

Using core JavaScript methods, it's possible to work around this problem. It involves multiplying by 100, rounding and then dividing by 100. But, since most of the projects I work on use JavaScript libraries and nearly all of them have round() functions in some form or another, I decided to get a little help from a library. Specifically, I use the MooTools round() method for solving this problem.

The round() method takes how many places after the decimal to round to, so by calling round(2), a number like 0.0999 (repeating) is converted to 0.1.

Vending Machine - Japan By rytc

Note that as the method is added to the prototype of the Number object (i.e. base class), it is called as an instance method of the number you want to round, not as a method of the Math object as with core JS methods. Compare:

Core JS: Math.round(1.8);
MooTools: 1.8.round();

Designing a Solution

My idea for the solution is to store a hash of the coin values keyed by their name, and then iterate over them checking if each value is higher than the amount of remaining change to dispense. For this to work, I need to iterate over them in order from highest to lowest. Otherwise, if I start in random order, it will break one of the requirements: This must return the least units of currency as possible. If I start at the penny, then it would keep dispensing pennies until there was no change left, and never get on to the other units of currency.

Therefore, the loop needs to iterate over the currency values in order of highest to lowest: dollar, quarter, dime, nickel, penny. Here is the hash object that I created to represent the currency values, and then we'll discuss how to iterate over them in order:

 var money =
     'dollar': 1.00,
     'quarter': 0.25,
     'dime': 0.10,
     'nickel': 0.05,
     'penny': 0.01                                 
 };

You might think it's as easy as using a for/in loop, but unfortunately, browser compatibility issues prevent it from being this simple. Using a for/in loop will iterate over the items but there is no guarantee of the order. Internet Explorer and Firefox use the correct order (the order of declaration) as far as I know, but Safari in particular does not follow this. So, it's not as simple as:

function dispenseChange(changeToDispense) {
 var result = new Array();
 for (var unit in money) {
     if (money[unit] > changeToDispense) result.push(unit);
 }
 return result;
}

It would be nice if it were this simple, and indeed in most browsers it is. But due to obscure quirks with the order of iteration over objects of properties, we need to store the order in its own array.

Asahi Beer Vending Machine: Komatsu By jpellgen

A Working Solution

I've changed the money object to now contain two properties, a values hash and an order array.

 var money = {
     values: {
         'dollar': 1.00,
         'quarter': 0.25,
         'dime': 0.10,
         'nickel': 0.05,
         'penny': 0.01                                 
     },
     order: ['dollar', 'quarter', 'dime', 'nickel', 'penny']
 };

Now I can iterate over the order array and use that to key the values hash. It's one extra step in the process but it doesn't add too much bloat to the code, and it actually works (at least, in the browsers I've tested):

function dispenseChange(changeToDispense) {         
 var result = new Array();
 while (changeToDispense.round(2) >= 0.01) {
     for (var i = 0; i < money.order.length; i++) {
         var value = money.values[money.order[i]]; // Number, e.g. 1.00
         if (changeToDispense.round(2) >= value) {
             result.push(money.order[i]); // String, e.g. "dollar"
             changeToDispense -= value;
             break;                      
         }
     }
 }
 return result;
}

You can test the function with logging statements:

window.addEvent('domready', function() {
 var tests = [.01, .05, .11, .27, .74, 1.08, 1.99, 2.07];
 tests.each(function(testValue) {
     console.log(testValue.toString() +
                 ': ' +
                 dispenseChange(testValue)
     );
 });
});

Improving the Implementation

One area for improvement is the nested for() loop inside the while() loop. Right now it isn't ideal, since it will waste iterations checking for currency amounts higher than the current currency. To explain what I mean, let's look at the loop again:

 while (changeToDispense.round(2) >= 0.01) {
     for (var i = 0; i < money.order.length; i++) {
         // ...
         if (changeToDispense.round(2) >=
             money.values[money.order[i]) {
             // dispense unit of currency
             break;                      
         }
     }
 }

I commented out some of the implementation details so we can focus on the structure. The reason that this is sub-optimal is that after each unit of currency is dispensed, the for() loop breaks and the while() loop starts it over again. Say there is less than a dollar remaining to dispense-- for each unit of currency dispensed, the for() loop will still check for a dollar.

To optimize this code, we'd have to only iterate over the order array once. This means the for() loop would be outside the while() loop, and for each unit of currency, the while() loop would continue to dispense change of that unit until the change remaining is less than the unit's value. It would be optimized to n (see Big O notation for details) at that point.

Optimized Code

Here is the new and improved code with the optimized loops:

var money = {
 values: {
     'dollar': 1.00,
     'quarter': 0.25,
     'dime': 0.10,
     'nickel': 0.05,
     'penny': 0.01                                 
 },
 order: ['dollar', 'quarter', 'dime', 'nickel', 'penny']
};
function dispenseChange(changeToDispense) {
  
 var result = new Array();
 money.order.each(function(unit, i) {
     var value = money.values[unit]; // Number, e.g. 1.00
     while (changeToDispense.round(2) >= value) {
         result.push(unit); // String, e.g. "dollar"
         changeToDispense -= value;
     }
 }); 
 return result;
}
  
window.addEvent('domready', function() {
 var tests = [.01, .05, .11, .27, .74, 1.08, 1.99, 2.07];
 tests.each(function(testValue) {
     console.log(testValue.toString() +
                 ': ' +
                 dispenseChange(testValue)
     );
 });
});

An observant reader will notice that I changed the for() loop to use MooTools' each() method. The reason I did this is that we no longer need to break out of the for() loop, and I prefer the each() notation. (Thanks for recommending it, Lowell!)

As always, feel free to post your own solutions to this challenge in the comments.