make-change.hx

static var coins = [4, 3, 1];
var computed = new Map(); // cache already-solved target amounts

// return the minimum number of coins needed to make change for the
// given target amount, using the list of coins above. Returns `None`
// for requests that don't make sense (target < smallest coin)
// break it into all possible sub-problems, and cache the result from computing those
// did i do it? is this dynamic programming?
function makeChange(target: Int, count: Int): Option<Int> {
  return switch computed.getOption(target) {
    case Some(v): v;
    case None if (target < 0): None; // not meaningful
    case None if (target == 0): Some(count);
    case None:
      var optimal = arrayMin(coins.filterMap(function (c) {
        return c > target ? None : makeChange(target - c, count + 1);
      }));
      computed.set(target, optimal);
      optimal;
  };
}

// returns the smallest Int in the array, or None if the array is empty
function arrayMin(arr: Array<Int>): Option<Int> {
  return arr.reduce(function (acc, curr) {
    return switch acc {
      case Some(v): v > curr ? Some(curr) : acc;
      case None: Some(curr);
    }
  }, None);
}

makeChange(6, 0); // should produce Some(2)