Exact Change: Program vs Real World

Hi everyone, I am a newbie.

Today I am working on the Exact Change program, I passed the test.
Although I have a question, it keeps confusing me, could you please help me?

IF:

  • I need to give 0.32 change to someone.
  • I have:
    ** 1 QUARTER = 0.25 x 1 = 0.25
    ** 3 DIME = 0.10 x 3 = 0.30
    ** 2 PENNY = 0.01 x 2 = 0.02

##Computer thinks

The function told me that I can not, because they will give this person 1 quarter first, 0.07 can’t be passed.

Human thinks

Give the person 3 Dimes and 2 Pennies.


Here’s the code from Forum Guide, I changed the test arguments, PLEASE HELP ME.

// Create an object which hold the denominations and their values
var denom = [
  { name: 'ONE HUNDRED', val: 100.00},
  { name: 'TWENTY', val: 20.00},
  { name: 'TEN', val: 10.00},
  { name: 'FIVE', val: 5.00},
  { name: 'ONE', val: 1.00},
  { name: 'QUARTER', val: 0.25},
  { name: 'DIME', val: 0.10},
  { name: 'NICKEL', val: 0.05},
  { name: 'PENNY', val: 0.01}
];

function checkCashRegister(price, cash, cid) {
  var change = cash - price;

  // Transform CID array into drawer object
  var register = cid.reduce(function(acc, curr) {
    acc.total += curr[1];
    acc[curr[0]] = curr[1];
    return acc;
  }, {total: 0});

  // Handle exact change
  if (register.total === change) {
    return 'Closed';
  }

  // Handle obvious insufficent funds
  if (register.total < change) {
    return 'Insufficient Funds';
  }

  // Loop through the denomination array
  var change_arr = denom.reduce(function(acc, curr) {
    var value = 0;
    // While there is still money of this type in the drawer
    // And while the denomination is larger than the change reminaing
    while (register[curr.name] > 0 && change >= curr.val) {
      change -= curr.val;
      register[curr.name] -= curr.val;
      value += curr.val;

      // Round change to the nearest hundreth deals with precision errors
      change = Math.round(change * 100) / 100;
    }
    // Add this denomination to the output only if any was used.
    if (value > 0) {
        acc.push([ curr.name, value ]);
    }
    return acc; // Return the current Change Array
  }, []); // Initial value of empty array for reduce

  // If there are no elements in change_arr or we have leftover change, return
  // the string "Insufficient Funds"
  if (change_arr.length < 1 || change > 0) {
    return "Insufficient Funds";
  }

  // Here is your change, ma'am.
  return change_arr;
}

// test here
checkCashRegister(19.68, 20.00, [["PENNY", 0.02], ["NICKEL", 0], ["DIME", 0.30], ["QUARTER", 0.25], ["ONE", 0], ["FIVE", 0], ["TEN", 0], ["TWENTY", 0], ["ONE HUNDRED", 0]]);

Sorry for my bad English.

I think you have answered your own question—the algorithm goes through the cash register array, which is sorted by denominations, only once. That’s why it can never fulfil the test case you have given even though there is enough change.

It looks like the example solution is actually wrong in this case. If it’s not already reported on GitHub it’s worthwhile creating an Issue for it since it’s also in the beta curriculum.

I hope that helps. :slight_smile:

1 Like

Thank you my friend to answer me. I know there’s problem, I am wondering how to fix, I tried to code by myself but failed. Is there a better way?

There are certainly many ways that you could approach this.

Without spending to much time thinking about it, the conceptually easiest method (and probably most expensive) is to go through the denominations in all possible permutations until you find a solution (if one exists). You certainly can cut down the number of permutations by checking the change left against the denominations left.

I decided to see if there is anything written about this and found this better approach if you don’t want to spend too much time coming with a solution—please note that there is code posted at the end of the post (in case you don’t want to see any, which I assume is not the case).

I hope that helps. :slight_smile:

1 Like

That sounds like a dynamic programming solution.

You essentially calculate all the possible changes you can make, by I guess, building up from each denomination, store the solution in an array, then just match the change to the array

1 Like

/Looking at the last line of the code in the link.
If you change the bottom line in the price to 19.95 it does not give an error. Which it should, since the change cannot be made with the change in the drawer.

/ Example of $0.30 with dimes and quarters
drawer(19.95, 20.00, [[“PENNY”, 0], [“NICKEL”, 0], [“DIME”, 0.50], [“QUARTER”, 0.50], [“ONE”, 0], [“FIVE”, 0], [“TEN”, 0], [“TWENTY”, 0], [“ONE HUNDRED”, 0]]);