Cash Register Challenge

Cash Register Challenge
0

#1

Hello, I’ve been picking away at the Cash Register challenge for a few weeks, now, and I’m royally stuck. I’ve had a pair-programming session that allowed me to logically get to where I am now, but I’m having a difficult time composing the algorithm that I need to loop through the existing Cash In Drawer (cid) array to subtract the correct amount of cash to create a new array that I can return.

So far, I’ve factored out the “easy” scenarios:

  • amt in drawer is less than the change that is needed
  • amt in drawer is equal to the change that is needed

I wasn’t sure how to subtract the correct denominational increments from the existing cid array, so I created an array of objects to store each denomination and what it’s worth. However, I’m stuck on how to marry these two together into a for loop or some sort of reduce or map function.

JS Bin on jsbin.com

function checkCashRegister(price, cash, cid) {
  // initialize change variable to store the current change
  var change = cash - price;

  // initialize function response with an empty object
  var response = { status: "", change: [] }
  
  // initialize cidAmt to store the total amout of cash
  // currently in the drawer
  var cidAmt = cid.reduce( function (accumulator, current) {
    return accumulator + current[1];
  }, 0);
  
  // handle easy scenarios first
  // amt in drawer is less than the change that is needed
  if ( cidAmt < change ) {
    response.status = "INSUFFICIENT_FUNDS";
    return response;
  }
  
  // amt in drawer is equal to the change that is needed
  if ( cidAmt === change ) {
    response.status = "CLOSED";
    response.change = cid;
    return response;
  }
  
  // need an array that contains the various denominations and their values
  var denomValue = [
    {bill: "ONE HUNDRED", val: 100},
    {bill: "TWENTY", val: 20},
    {bill: "TEN", val: 10},
    {bill: "FIVE", val: 5},
    {bill: "ONE", val: 1},
    {bill: "QUARTER", val: 0.25},
    {bill: "DIME", val: 0.10},
    {bill: "NICKEL", val: 0.05},
    {bill: "PENNY", val: 0.01}
  ];
  
  // need to reverse the cid array to loop in reverse order
  var cidDesc = cid.reverse(); // order the cid array from largest to smallest
  
  for ( i = 0; i <= denomValue.length; i += 1 ) {
    if ( cidDesc[i][1] > change ) {
      change -= denomValue[i].val
    } else {
      return "else block";
    }
  }
  
  // test area
    
  // end test area
  
  // Here is your change, ma'am.
  return change;
}

// Example cash-in-drawer array:
// [["PENNY", 1.01],
// ["NICKEL", 2.05],
// ["DIME", 3.1],
// ["QUARTER", 4.25],
// ["ONE", 90],
// ["FIVE", 55],
// ["TEN", 20],
// ["TWENTY", 60],
// ["ONE HUNDRED", 100]]

checkCashRegister(19.5, 20, [["PENNY", 1.01], ["NICKEL", 2.05], ["DIME", 3.1], ["QUARTER", 4.25], ["ONE", 90], ["FIVE", 55], ["TEN", 20], ["TWENTY", 60], ["ONE HUNDRED", 100]]);

#2

Well if you are going for deducting approach. The following must happen at each step of iteration.

  1. Determine if current bill type can be used and you have remaining change.
  2. If yes, compute the maximum amount of change that can fit into given change. Here you must consider the type of bill, change, and available amount.
  3. Deduct the computed amount
  4. Update the output array.

Note that

  • in step 2) you must come up with a formula.
  • you don’t need to reverse cid. denomValue is already sorted in desc order.
  • it is easier to build output array than to modify cid
  • Beaware of floating point arithmetic, which will likely to give you incorrect result for each iteration.

Also, the given data is in an unpleasant shape to work with. It is optional, but polishing the data before the actual computation makes writing code more enjoyable.


#3

Thank you for laying that out so well, @gunhoo93! Is there a simpler approach to this algorithm that I’m missing?


#4

I don’t think there is a simpler approach. The alternative way is to add up the change like what most people do in real life. However, translating that to code won’t be any simpler than deducting method because one is just the inverse of another. But, I find adding up method clearer than deducting.

What makes this problem slightly more complicated is that you have to keep jumping here and there to get the data you want. For example, how would you get the available amount of money for a specific type of bill with its unit value?

I dislike reading expressions that looks like obj[ arr[i][j] ] bla bla... If you have to keep mentioning some data this way, you will probably get lost in your code. The end result is also not that readable. If you can find a way to avoid referring data this way, then it will probably make writing code easier.


#5

You could probably do this with recursion if you wanted to. However, I think you’ll find it easier to count the money.


#6

@gunhoo93, now that you mention it, I think I’m getting lost in my data references because they look like the form you wrote above. Every time I try to refactor the algorithm, it gets uglier, and syntax errors pop-up because of the 2D arrays and nested objects.

@joker314, I’m sure there’s a recursive solution to this, but it’s beyond my reasoning ability, right now. I’m struggling just to get any solution that works :frowning_face:


#7

I made some more progress on this problem, but I’m getting stuck in the while loop that’s nested in the for loop. I can’t seem to get the correct conditional so that the pennies calculate correctly. All of the higher-order denominations are counting correctly.

I would appreciate any assistance to get over this ‘hurdle.’

All of the tests except this one are passing:

checkCashRegister(3.26, 100, [
    ["PENNY", 1.01], 
    ["NICKEL", 2.05], 
    ["DIME", 3.1],
    ["QUARTER", 4.25],
    ["ONE", 90], 
    ["FIVE", 55], 
    ["TEN", 20], 
    ["TWENTY", 60], 
    ["ONE HUNDRED", 100]
]);

Code on jsbin

function checkCashRegister(price, cash, cid) {
  // initialize change variable to store the current change
  var change = cash - price;

  // initialize function response with an empty object
  var response = { status: "", change: [] }
  
  // initialize cidAmt to store the total amout of cash
  // currently in the drawer
  var cidAmt = cid.reduce( function (accumulator, current) {
    return accumulator + current[1];
  }, 0);
  
  // handle easy scenarios first
  // amt in drawer is less than the change that is needed
  if ( cidAmt < change ) {
    response.status = "INSUFFICIENT_FUNDS";
    return response;
  }
  
  // amt in drawer is equal to the change that is needed
  if ( cidAmt === change ) {
    response.status = "CLOSED";
    response.change = cid;
    return response;
  }
  
  // need an array that contains the various denominations and their values
  var denomValue = [
    {denom: "ONE HUNDRED", val: 100},
    {denom: "TWENTY", val: 20},
    {denom: "TEN", val: 10},
    {denom: "FIVE", val: 5},
    {denom: "ONE", val: 1},
    {denom: "QUARTER", val: 0.25},
    {denom: "DIME", val: 0.10},
    {denom: "NICKEL", val: 0.05},
    {denom: "PENNY", val: 0.01}
  ];
  
  // loop through the denomValue array of objects, incrementally subtracting
  // the value from the change variable
  var newCidArray = [];
  var currVal = 0;
  var i = 0;
  for ( i = 0; i < denomValue.length; i += 1 ) {
    while ( change >= denomValue[i].val && currVal < cid[ 8 - i ][1] ) {
      change -= denomValue[i].val;
      currVal += denomValue[i].val;
    }
    
    if ( currVal > 0 ) {
      newCidArray.push([denomValue[i].denom, currVal]);
    }
    currVal = 0; // reset current value (currVal) to zero after the loop has completed
  }
  
  if ( change > 0 ) {
    response.status = "INSUFFICIENT_FUNDS";
    response.change = [];
    return response;
  }
  
  
  // Here is your change, ma'am.
  response.status = "OPEN";
  response.change = newCidArray;
  return response;
}

// Example cash-in-drawer array:
// [["PENNY", 1.01],
// ["NICKEL", 2.05],
// ["DIME", 3.1],
// ["QUARTER", 4.25],
// ["ONE", 90],
// ["FIVE", 55],
// ["TEN", 20],
// ["TWENTY", 60],
// ["ONE HUNDRED", 100]]

checkCashRegister(3.26, 100, [["PENNY", 1.01], ["NICKEL", 2.05], ["DIME", 3.1], ["QUARTER", 4.25], ["ONE", 90], ["FIVE", 55], ["TEN", 20], ["TWENTY", 60], ["ONE HUNDRED", 100]]);

#8

Your logic is correct, but there is a floating point computation problem. For example, try

console.log(0.1 + 0.2)

The overall margin of error tends to accumulate as more floating point computations are done without correcting the error. You need to find a point where this error accumulates and correct it by treating the initial computation as integer then converting the result back to float. For example,

Math.trunc( (0.1 + 0.2) * 10 ) / 10 // === 0.3
// i.e. only keep the significant digits.

You can also use round() depending on how you treat the small margin of error.

Also, there is a simpler formula that does all the work done by your while loop. Hint: think about the remainder operator.


#9

I finally tracked down the floating point rounding error :tada:

Thanks to @gunhoo93 and @joker314 for your help!

It feels good to finally arrive at the solution after so much work :sweat:


#10

This is how I did Cash Register challenge

function checkCashRegister(price, cash, cid) {
    var change = cash - price;
    var response = { status: "", change: [] };

    var cidAmount = cid.reduce( function (accumulator, current) {
        return accumulator + current[1];
    }, 0);

    if ( cidAmount < change ) {
        response.status = "INSUFFICIENT_FUNDS";
        return response;
    }

    else if ( cidAmount === change ) {
        response.status = "CLOSED";
        response.change = cid;
        return response;
    }

    else{
        cid = cid.reverse();
        let moneyTable = [];

        let amounts = [100, 20, 10, 5, 1, 0.25, 0.1, 0.05, 0.01];

        for(let i = 0; i < cid.length; i++){
            let item = {};
            item["name"] = cid[i][0];
            item["amount"] = amounts[i];
            item["totalAmount"] = cid[i][1];
            moneyTable.push(item);
        }

        for(let i = 0; i < moneyTable.length; i++){
            let ele = [];

            if(change >= moneyTable[i].amount && change > 0 && moneyTable[i].totalAmount > 0){
                ele.push(moneyTable[i].name);
                let money = Math.floor(change / moneyTable[i].amount) * moneyTable[i].amount;
                if(money > moneyTable[i].totalAmount){
                    money = moneyTable[i].totalAmount;
                }
                ele.push(money);
                change -= money;
                change = +change.toFixed(2);
                console.log(change);
                response.change.push(ele);

            }
            if(change === 0){
                break;
            }
        }
        console.log(change);
        if(change === 0){
            response.status = "OPEN";
        }
        else{
            response.status = "INSUFFICIENT_FUNDS";
            response.change =[];
        }
    }
    console.log(response.status);
    console.log(response.change);
    // Here is your change, ma'am.
    return response;
}