Change Generator in Javascript

As a child I was fascinated by vending machines. The idea that you could pop in a few shiny coins and be presented with a chocolate bar was great. As an adult I wondered what logic was used to determine how a vending machine gave out change.

It would have to factor in what coins were available as well as what the best combination of coins to return would be. Ideally it would degrade gracefully based on the number and type of coins in the machine at any time. Thinking about a problem only gets you so far and in my case I had a sudden itch to see what a solution would look like.

A first attempt yielded the code below. Copy and paste into Firebug to run.

The Javascript Solution

function copier (arrMaps) {
var arrCopy = [];
for (var nSlot = 0; nSlot < arrMaps.length; ++nSlot)
arrCopy[nSlot] = {label: arrMaps[nSlot].label,
value: arrMaps[nSlot].value,
count: arrMaps[nSlot].count};
return arrCopy;
}

function monies () {
return [{label: "20p", value: 20, count: 2},
{label: "10p", value: 10, count: 3},
{label: "5p", value: 5, count: 2},
{label: "2p", value: 2, count: 4},
{label: "1p", value: 1, count: 12}];
}

function filter (arrMaps, nChange) {
var arrCopy = copier (arrMaps)
for (var nSlot = arrCopy.length - 1; nSlot >= 0; --nSlot) {
if (arrCopy[nSlot].value > nChange) {
arrCopy.splice(nSlot, 1);
} else {
var nCount1 = arrCopy[nSlot].count;
var nCount2 = parseInt (nChange / arrCopy[nSlot].value);
arrCopy[nSlot].count = Math.min (nCount1, nCount2);
}
}
return arrCopy;
}

function expand (arrMaps, nChange) {
function expand1 (mapDenom) {
var arrMaps = [];
for (var nSlot = mapDenom.count; nSlot >= 0; --nSlot)
arrMaps.push({label: mapDenom.label, value: mapDenom.value, count: nSlot});
return arrMaps;
}
var arrArrMaps = [];
for (var nSlot = 0; nSlot < arrMaps.length; ++nSlot)
arrArrMaps.push(expand1(arrMaps[nSlot]));
return arrArrMaps;
}

function total (arrMaps) {
var nTotal = 0;
for (var nSlot = 0; nSlot < arrMaps.length; ++nSlot)
nTotal += (arrMaps[nSlot].count * arrMaps[nSlot].value);
return nTotal;
}

function combos(arrCombos, nChange) {
function findCombos(arrCombos, arrSols, arrTemp, nChange, nFrom, nUpto) {
if (nFrom < nUpto) {
for (var nSlot = 0; nSlot < arrCombos[nFrom].length; ++nSlot) {
arrTemp.push(arrCombos[nFrom][nSlot]);
findCombos(arrCombos, arrSols, arrTemp, nChange, nFrom + 1, nUpto);
arrTemp.pop();
}
}
else {
if (total(arrTemp) == nChange)
arrSols.push(copier(arrTemp));
}
return arrSols;
}
return findCombos(arrCombos, [], [], nChange, 0, arrCombos.length);
}

function stdout (arrArrMaps) {
for (var nRow = 0; nRow < arrArrMaps.length; ++nRow){
var strBuf = (nRow + 1) + ": ";
for (var nCol = 0; nCol < arrArrMaps[nRow].length; ++nCol) {
if (arrArrMaps[nRow][nCol].count > 0) {
strBuf += arrArrMaps[nRow][nCol].label;
strBuf += "*";
strBuf += arrArrMaps[nRow][nCol].count;
if (nCol < arrArrMaps[nRow].length - 1)
strBuf += ", ";
}
}
console.log(strBuf);
}
}

function main() {
var nPayment = 50;
var nCost = 18;
var nChange = nPayment - nCost;
var arrMonies = monies();
var arrCopied = copier(arrMonies);
var arrFilter = filter(arrCopied, nChange);
var arrExpand = expand(arrFilter, nChange);
var arrCombos = combos(arrExpand, nChange);
stdout(arrCombos);
}