JavaScript Combination Algorithm (determining proper coin change)

combination-coin-changer.js

// Codewars Kata [4 kyu] Vending Machine (JavaScript)

// My 3-day (albeit 32-hour) Solution
// Development history details at bottom.
// I may be a bit slower than some, but I'm persistent :), and I pick up on many underlying nuances.

// I got my (final) base model for the 'combination algorithm' from:
// Code Review Stack Exchange: Answer: https://codereview.stackexchange.com/a/7042
// https://codereview.stackexchange.com/questions/7001/generating-all-combinations-of-an-array

function VendingMachine(coins) {
  this.coins = coins;
  this.vendAmt = 0;
  for (let coin in coins) { this.vendAmt += parseInt(coin) * coins[coin]; }
  // This kata looked sooo much simpler than it turned out to be (4 days!?!?)
}

VendingMachine.prototype.vending = function(price, credit) {
  let credAmt = 0,
      balanceDue = 0,
      mostChangeBack = 0,
      returnCredit = {};

  for (let cred in credit) { // Don't add if currency isn't already in the machine
    if (typeof(this.coins[cred]) !== 'undefined' && 
        !isNaN(parseInt(cred, 10)) && parseInt(cred, 10) > 0) {
      credAmt += parseInt(cred) * credit[cred];
    }
  }
  if (credAmt < price) {     // Is credit less than price.
    returnCredit = credit;
  } else {                   // Balance owed: credAmt - price
    for (let cred in credit) {
      if (typeof(this.coins[cred]) === 'undefined') {
        returnCredit[cred] = credit[cred]; // Invalid key value; Give it back
      } else {
        this.coins[cred] += credit[cred];
      }
    }
    balanceDue = credAmt - price; // $ owed back

    let validCoins = [],
        validCombos = [],
        validComboRuns = new Map,
        curCombo= {'curChange': 0, 'curCoins': []};

    for (var coinT in this.coins) {
      if (this.coins[coinT] > 0 && parseInt(coinT, 10) <= balanceDue) {
        let maxCoins = Math.floor(balanceDue / parseInt(coinT, 10)),
            maxQty = maxCoins < this.coins[coinT] ? maxCoins : this.coins[coinT];
        validCoins.push(Array.from(Array(maxQty)).map( (e,i) => coinT));
      } // console.log("coinT: ", coinT, this.coins[coinT]);
    }

    // Flatten inner arrays and sort in descending order (likely don't need to sort; was from initial phase).
    validCoins = validCoins.reduce((e,v) => 
                                   e.concat(v), []).sort((a,b) => 
                                                         parseInt(a,10) < parseInt(b,10) ? 1 : -1);
    // console.log('balanceDue: ', balanceDue, validCoins); // 19 ["9", "9", "5", "5"]

    const powerset = (chars) => { // O(2^n)
      let result = [];

      let f = function(prefix, chars) {
        curCombo = {'curChange': 0, 'curCoins': []};

        for (var i = 0; i < chars.length; i++) {

          if (result.indexOf(prefix + '-' + chars[i]) === -1) {
            curCombo.curChange += (prefix + '-' + chars[i]).split('-').slice(1).reduce((a,v)=>a+parseInt(v,10),0);
            curCombo['curCoins'] = (prefix + '-' + chars[i]).split('-').slice(1);
            result.push(prefix + '-' + chars[i]);

            if (curCombo.curChange > 0 && curCombo.curChange <= balanceDue && !validComboRuns.has(curCombo.curChange)) {
              validCombos.push(curCombo);
              validComboRuns.set(curCombo.curChange, curCombo.curCoins);
            } else if ( curCombo.curChange > 0 && 
                        curCombo.curChange <= balanceDue &&
                (Math.max.apply(null, curCombo.curCoins) > Math.max.apply(null, validComboRuns.get(curCombo.curChange)))
              ) {
              // Another combination resulted in this same change, but with a higher denomination.
              validCombos[validCombos.findIndex(e => e.curChange === curCombo.curChange)].curCoins = curCombo.curCoins;
              validComboRuns.set(curCombo.curChange, curCombo.curCoins);
            }
            f(prefix + '-' + chars[i], chars.slice(i + 1));
          }
        }
      }
      f('', chars);
      return result;
    };
    powerset(validCoins);

    // Get ready for a winner!
    let winCredit = {},
        winBalanceDue = balanceDue,
        winChange = 0;

    // Find out which combo is the best fit ('validCombos' is already in desc order)
    for (let thisComboKey in validCombos) {
      let thisCombo = validCombos[thisComboKey];
      if (thisCombo.curChange <= winBalanceDue && thisCombo.curChange > winChange) {
        winCredit = thisCombo.curCoins.reduce( (a,v) => {
          a[v] = (typeof(a[v]) !== 'undefined') ? a[v] + 1 : 1;
          return a;
        }, {}); // { 9:1, 5:2 }
        winChange = thisCombo.curChange;
      }
    }
    balanceDue = winBalanceDue;

    for (var k in winCredit) {
      this.coins[k] -= winCredit[k];
      returnCredit[k] = winCredit[k];
    };
  }
  return returnCredit;
}
/*
Development History Details
---------------------------
2018-01-13 - Saturday -- 13+ hours

    @4:00 PM - Codewars - Vending Machine

@2:50 AM - Thought I finally had it!
    {9: 2} "=== {5:2,9:1}"

@3:40 AM
    Just found out there's another permutation I need to account for... verticals.
    I can't simply multiply each whole number I pass through times (*) its utmost potential quantity.
    I need to permutate each potential quantifiable whole number in subgroups.
    Now... wth did I just say???
    I was doing 1(x1), 4(x2), 5(x1), 6(x3), etc.
    I need to do 1(x1), 4(x2), 4(x1), 5(x1), 6(x3), 6(x2), 6(x1), etc.
    But then there are permutations between each individual quantity permutations as well.
    Alright, let's try to permutate this son-gun.

@5:15 AM
    - Flattened all the permutable values * quantities (3*3*2 === 18).
    - Have a flattened array of all the potential values (less any (that are) less than `balanceDue`).

2018-01-14 - Sunday -- 4 hours

201-01-15 - Monday --  14.50 hrs

@6:45 AM
    - Passed: 14 Failed: 3 Errors: 1
    - Got the combinations down
        (only allowing qty * values under balanceDue (instead of all of them))
    - Now it's failing on the order
        (higher value amts over smaller denominations; 6:1,2:1 > 4:2)

@8:50 AM
    - Passed: 15 Failed: 2 Errors: 1
    - The failure is it's still timing out.
        Looks like I'm gonna need another algorithm. :-|

@6:30 PM
    -  Passed: 17 Failed: 1
    - Error is in last test run. Was able to recreate in CodePen.

@7:05 PM
    - Think I figured out the issue.
    - Gonna need to refactor the combination algorithm to support 2-digit denominations.
    - Unsure why any '10'+ didn't fail...? Just caught this on a '20'.

@7:40 PM
    - Tried converting `prefix` to an array, but browser crashed
        (only the 30th time today, fortunately I searched and found "&turn_off_js=true")
    - Gonna try to keep it as string, but identify ... what?
        Not sure what I can identify. Need to think on this a bit.
@8:25 PM
    - Went back with string, but inserted '-' delimiter. Seems to be working.
    - Time: 477ms Passed: 18 Failed: 0

    2018-01-13 - Saturday -- 13+ hours
    2018-01-14 - Sunday -- 4 hours (maybe??)
    201-01-15 - Monday --  14.50 hrs
=== ~32 hours
*/