Change Calculator Simple Algorithm
Simple Change Possibilities Calculator Warning: This is not an optimized version. Long totals and changes may block the event loop Time controlled yelding solutions should be introduced Please refer to: https://www.coderecipes.org/snippets/5c69b5eb99453f09094d661a Known bug: If you pass over an array with the same repeated coin, it will not give correct results as the exit condition is if last coin matches the coin on the loop. // So the trivia is: // First element on the array is always 1, for when difference between iteration and coin is zero, counts as one (static accumulator) [ 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1 ] COIN 5 (scan until max 15, if its odd, increment that position, with the difference to total count) [ 1, 0, 0, 0, 1, 0, 0, 0, 0, 2, 0, 0, 0, 0, 2 ] COIN 10 (scan until max 15, if its odd, increment that position, with the difference to total count)
1const floodArray = (arr, positions, value) => {
2 for (let i = 0; i <= positions; i++) {
3 arr[i] = value;
4 }
5 return arr;
6}
7// Phase 5 of Event Loop Stack
8const unblockWithSetImmediatePromise = () => {
9 // return new Promise((resolve) => {
10 // setImmediate(() => resolve());
11 // });
12};
13
14const removeUselessCoins = (coins) => {
15 coins = coins.filter(coin => {
16 return coin <= amount;
17 })
18}
19
20const sortCoins = (coins) => {
21 return coins.sort( (a, b) => {
22 return a - b;
23 });
24}
25
26const countChange = (amount, coins) => {
27 coins = sortCoins(coins);
28 coins = removeUselessCoins(amount, coins);
29 if (amount <= 0 || coins.length === 0){
30 return 0;
31 }
32 var combinations = [];
33 combinations = floodArray(combinations, amount, 0);
34 // combinations = [0,0,0,0,0,0,... ]
35
36 // Default
37 combinations[0] = 1;
38
39 // Iterator for each coin
40 for (let index = 0; index < coins.length; index++) {
41 const coin = coins[index];
42
43 // Start on the first coin - lowest
44 for (let coinPointer = coin; coinPointer <= amount; coinPointer++) {
45 const differenceToTotal = coinPointer - coin;
46 console.log('differenceToTotal', coinPointer)
47 combinations[coinPointer] += combinations[differenceToTotal];
48 // Finished return the accumulated value
49 if(coinPointer === amount && coin === coins[coins.length - 1]) {
50 return combinations[amount];
51 }
52 }
53 }
54}
55
56var coins = [5, 10, 20, 50, 100, 200, 500];
57var amount = 300;
58const total = countChange(amount, coins);
59console.log('TOTAL', total)
60Created on 2/27/2019