1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
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}`);
}
}
|
