Progress with InterviewCake's coin problem

I'm writing a function that returns the total number of ways a cashier can make
change given the `amount` of change that the customer needs and an array of
`coins` from which to create the change.

My solution conceptually works but it actually does not return the results I am
expecting because I cannot create a Set of Map<A, B> in JavaScript. I'm also
somewhat sure that InterviewCake is expecting a less computationally expensive
answer.

1 files changed, 102 insertions, 0 deletions

diff --git a/scratch/deepmind/part_two/coin.ts b/scratch/deepmind/part_two/coin.ts
new file mode 100644
index 000000000000..8aa8de8bb87a
--- /dev/null
+++ b/scratch/deepmind/part_two/coin.ts
@@ -0,0 +1,102 @@
+// The denomination of a coin.
+type Coin = number;
+
+// The amount of change remaining.
+type Amount = number;
+
+// Mapping of Coin -> Int
+type CoinBag = Map<Coin, number>;
+
+function createCoinBag(coins: Coin[]): CoinBag {
+  const result = new Map();
+
+  for (const coin of coins) {
+    result.set(coin, 0);
+  }
+
+  return result;
+}
+
+// This algorithm should work conceptual, but it does not actually
+// work. JavaScript uses reference equality when constructing a Set<Map<A,B>>,
+// so my result.size returns a higher number than I expect because it contains
+// many duplicate entries.
+//
+// Conceptually, I'm not sure this solution is optimal either -- even after I
+// can dedupe the entries in `result`.
+function changePossibilities(amt: Amount, coins: Coin[]): number {
+  if (amt === 0) {
+    return 1;
+  }
+  const result: Set<CoinBag> = new Set();
+
+  const q: [Coin, Amount, CoinBag][] = [];
+
+  for (const coin of coins) {
+    const bag = createCoinBag(coins);
+    bag.set(coin, 1);
+    q.push([coin, amt - coin, bag]);
+  }
+
+  while (q.length > 0) {
+    const [coin, amt, bag] = q.shift();
+
+    console.log([coin, amt, bag]);
+
+    if (amt === 0) {
+      result.add(bag);
+    } else if (amt < 0) {
+      continue;
+    } else {
+      for (const c of coins) {
+        const bagCopy = new Map(bag);
+        const value = bagCopy.get(c);
+        bagCopy.set(c, value + 1);
+        q.push([c, amt - c, bagCopy]);
+      }
+    }
+  }
+  console.log(result);
+  return result.size;
+}
+
+// Tests
+let desc = "sample input";
+let actual = changePossibilities(4, [1, 2, 3]);
+let expected = 4;
+assertEqual(actual, expected, desc);
+
+desc = "one way to make zero cents";
+actual = changePossibilities(0, [1, 2]);
+expected = 1;
+assertEqual(actual, expected, desc);
+
+desc = "no ways if no coins";
+actual = changePossibilities(1, []);
+expected = 0;
+assertEqual(actual, expected, desc);
+
+desc = "big coin value";
+actual = changePossibilities(5, [25, 50]);
+expected = 0;
+assertEqual(actual, expected, desc);
+
+desc = "big target amount";
+actual = changePossibilities(50, [5, 10]);
+expected = 6;
+assertEqual(actual, expected, desc);
+
+// I think InterviewCake designed this assertion to be computationally
+// expensive.
+desc = "change for one dollar";
+actual = changePossibilities(100, [1, 5, 10, 25, 50]);
+expected = 292;
+assertEqual(actual, expected, desc);
+
+function assertEqual(a, b, desc) {
+  if (a === b) {
+    console.log(`${desc} ... PASS`);
+  } else {
+    console.log(`${desc} ... FAIL: ${a} != ${b}`);
+  }
+}