10b.md

Day 10 - Adapter Array - Code

You're trying to power your game device, but the outlet has a rating of 0 jolts. You have a bunch of adapters that you can chain together to get the desired jolts.

An adapter takes some input joltage, and outputs another joltage. These adapters in your bag are rated with a number. E.g., 42. An adapter rated 42 produces an output joltage of 42, and it can only do that if the input is at most 3 lower than the rating. E.g., the input to this 42 rated adapter must be 39, 40, or 41.

Assume in your backpack you have the following adapters.

1
4
5
6
7
10
11
12
15
16
19

You could use all of these adapters to go from 0 jolts to 19 jolts!

You'll notice a couple of things. For starters, some of these adapters are unnecessary to get a max of 19 jolts. We don't need the 6 or 7 adapters, nor do we need the 11 adapter.

What we're interested for part B of this problem is determining how many different ways they can be arranged to still get your max jolt.

The example above has 8 different ways of getting the max jolts.

(0), 1, 4, 5, 6, 7, 10, 11, 12, 15, 16, 19
(0), 1, 4, 5, 6, 7, 10, 12, 15, 16, 19
(0), 1, 4, 5, 7, 10, 11, 12, 15, 16, 19
(0), 1, 4, 5, 7, 10, 12, 15, 16, 19
(0), 1, 4, 6, 7, 10, 11, 12, 15, 16, 19
(0), 1, 4, 6, 7, 10, 12, 15, 16, 19
(0), 1, 4, 7, 10, 11, 12, 15, 16, 19
(0), 1, 4, 7, 10, 12, 15, 16, 19

Consider this example (adapters aren't sorted, so you'll have to sort them first):

28,
33,
18,
42,
31,
14,
46,
20,
48,
47,
24,
23,
49,
45,
19,
38,
39,
11,
1,
32,
25,
35,
8,
17,
7,
9,
4,
2,
34,
10,
3,

which has 19,208 different ways to getting the max jolts out.

For your input, how many different ways are there of getting the max jolts?

Solution

The first part in recognizing that this could be a DP solution is knowing that this is a combinatorics problem. The second clue is trying to play with a much smaller input and working backwards.

• Note: if working backwards isn't apparent at first, follow the 4 step process. Come up with a recursive solution, memoize it, reverse it, and then remove the cache layer.

Let's work through the first example above.

1
4
5
6
7
10
11
12
15
16
19

If the adapters were just 11 12 15 16 19, there would only be 1 configuration, because all of these are necessary. As sooon as we get to 10, we can either include 11 or not because 10 can jump to 12.

So we look at the number of ways to get to 12, and the number of ways to get to 11, and add them up. Since both of those are 1, the number of ways to configure 10 + {originalSet} is now 2.

It stays that way until we get to 5 because all the ones proceeding it are necessary in that order. If originalSet = {6,7,10,11,12,15,16,19}, then we can do either {5} + originalSet or {5} + (originalSet - {6}) because the set {6} is optional now. Notice that originalSet - {6} is just {7,10,...}, so we just sum the number of ways to get to 6 and number of ways to get to 7. Both of those are equal to 2, so now we have a total of 4 ways to get to 5.

The fibonnaci formula should be apparent now. If g(i) is the adapter value at i, and f(i) is the number of ways to get to adapter i, then

f(i) = f(i + 1)
        + IF(g(i + 2) - g(i) <= 3, f(i + 2))
        + IF(g(i + 3) - g(i) <= 3, f(i + 3))

Just make sure to prefix the list of adapters with 0 because we ultimately start there. This will make a differenc if you have 1 and 2 and 3 adapter, since some of those will be optional.

Here's the code:

function countAdapterConfigurations({ adapters }: Simulation) {
  const dp = [] as number[];
  // we need to add the outlet of 0 jolts to it.
  const sortedAdapters = [...adapters, 0].sort((a, b) => a - b);

  for (let i = sortedAdapters.length - 1; i >= 0; i--) {
    const curr = sortedAdapters[i];
    // the prev one has to fewer than 3 jolts away.
    dp[i] = dp[i + 1] ?? 1;

    if (sortedAdapters[i + 2] - curr <= 3) {
      dp[i] += dp[i + 2];
    }
    if (sortedAdapters[i + 3] - curr <= 3) {
      dp[i] += dp[i + 3];
    }
  }
  return dp[0];
}

Pigeonhole Principle Counting

Let's look at the larger example above (second example) and put them in a single row:

1 2 3 4 7 8 9 10 11 14 17 18 19 20 23 24 25 28 31 32 33 34 35 38 39 42 45 46 47 48 49

Let's group all the optional numbers, and add 0 at the end.

0 [1 2 3] 4 7 [8 9 10] 11 14 17 [18 19] 20 23 [24] 25 28 31 [32 33 34] 35 38 39 42 45 [46 47 48] 49

• Let's look at the first group [1 2 3]. If we consider them as 3 bits, then we have 2^3 = 8 choices for choosing them. The only one we can't choose is 000, i.e., the choice that selects none of them. This gives us 2^8 - 1 = 7 choices in the first group.
• Same for the second group [8 9 10]. We have 7 options. We're at a total of 7*7 choices now.
• For [18 19], we can choose to select none of them. 17 and 20 would still connect. This gives us 4 choices, total of 7*7*4.

• For [24], we have 2 choices: either pick 24 or not pick 24. 7*7*4*2.
• For [32 33 34], 7 choices. 7*7*4*2*7.
• Finally, [46 47 48], 7 choices here as well: 7*7*4*2*7*7 = 19,208.

Done!

Google Sheets

This could also be solved in Google Sheets fairly quickly:

1. Copy the input in column A.
2. Add a new row above the first column and set cell A0 to 0.
3. Sort column A.
4. Manually determine the last few values of our DP in column B. This will be our base case.
5. In column B, for the remaining rows, copy this formula:

=B2 + IF(A3-A1<=3, B3, 0) + IF(A4-A1<=3, B4, 0)