ATM withdrawal algorithm

Question

How does an ATM withdrawal algorithm work?

The code to get money from the ATM should work like this:

// count of nominals in ATM
let limits = {
  1000: 5,
  500: 2,
  100: 5,
  50: 100,
  30: 6
}

let getMoney = (amount, limits) => {
  ...
};

console.log(getMoney(1000, limits)); // {1000: 1}
console.log(getMoney(230, limits)); // {} | i need {100: 2, 30: 1}
console.log(getMoney(200, limits)); // {100: 2}
console.log(getMoney(150, limits)); // {50: 3} | i need {100: 1, 50: 1}
console.log(getMoney(120, limits)); // {30: 4}

I tried, and made this:

let getMoney = (am, lm) => {
  Object.keys(lm).map( k => {
    if(lm[k] && am / k >= 1 && am % k === 0)
      if(lm[k] > am / k)
        r[k] = am / k;
  });
};

...but the result is not correct:

console.log( getMoney(1000, limits) ); // {1000: 1}
console.log( getMoney(230, limits) ); // {} | i need {100: 2, 30: 1}
console.log( getMoney(200, limits) ); // {100: 2}
console.log( getMoney(150, limits) ); // {50: 3} | i need {100: 1, 50: 1}
console.log( getMoney(120, limits) ); // {30: 4}

How can I make it work?

Answer 1

Your algorithm assumes that if there is a solution, then that solution will take the most of the highest available denomination that still fits the remaining amount. This would work for some sets of denominations, like the common one (1000, 500, 200, 100, 50, 20, 10, 5, 2, 1), but not for the one in your example.

This is a variant of the change making problem and is a "hard" problem, in that you must potentially try a huge number of combinations. One way is to at least give precedence to attempts that take a lot of the higher valued denominations, and only try alternatives when those do not lead to a solution.

You could code it like this:

let getMoney = (amount, limits) => {
    let recur = (amount, nominals) => {
        if (amount == 0) return {}; // success
        if (!nominals.length) return; // failure
        let nominal = nominals[0];
        let count = Math.min(limits[nominal], Math.floor(amount / nominal));
        for (let i = count; i >= 0; i--) {
            let result = recur(amount - i*nominal, nominals.slice(1));
            if (result) return i ? { [nominal]: i, ...result } : result;
        }
    }
    return recur(amount, Object.keys(limits).map(Number).sort((a,b) => b - a));
};

// count of nominals in ATM
let limits = { 1000: 5, 500: 2, 100: 5, 50: 100, 30: 6 }

console.log(getMoney(1000, limits)); // {1000: 1}
console.log(getMoney(230, limits)); // {30: 1, 100: 2}
console.log(getMoney(200, limits)); // {100: 2}
console.log(getMoney(150, limits)); // {50: 1, 100: 1}
console.log(getMoney(120, limits)); // {30: 4}