10.md

Day 10

Part 1

What is the number of 1-jolt differences multiplied by the number of 3-jolt differences?

Because the input contains only 1-jolt and 3-jolt differences, Part 1 is straightforward:

const numbers = input.split('\n').sort((a, b) => a - b)

const prev = (i) => numbers[i - 1] || 0

const ones = numbers.filter((n, i) => n - prev(i) === 1).length
const threes = numbers.length - ones + 1
console.log('Ones:  ', ones)
console.log('Threes:', threes)
console.log('Part 1:', ones * threes)

The + 1 at the end of the threes declaration is needed because "your device's built-in joltage adapter [is] 3 higher than the highest-rated adapter," i.e. 3 higher than the largest input number.

Flems link in Part 2.

Part 2

What is the total number of distinct ways you can arrange the adapters to connect the charging outlet to your device?

Part 2 was very challenging! I tried to come up with a mathematic formula for this, but failed miserably. More on this in the What did I learn? section.

I did realize quite right from the beginning that when there are 3 or more consecutive numbers, i.e. 3 or more 1-jolt differences in a row, we have to use multiplication. For example, this input:

0 · · 3 4 5 6 · · 9

...can be arranged in these 4 ways:

0 · · 3 4 5 6 · · 9
0 · · 3 · 5 6 · · 9
0 · · 3 · · 6 · · 9
0 · · 3 4 · 6 · · 9

...meaning that when we encounter 4 consecutive numbers, we have to multiply our number of possible arrangements by 4.

Okay, let's take a step back. How do we know what numbers to use for the multiplications? Let's first check the length of the longest sequence of consecutive numbers:

const { max } = numbers.reduce(
  (sequences, n, i) => {
    if (n - prev(i) === 1) sequences.current++
    else sequences.current = 1

    sequences.max = Math.max(sequences.current, sequences.max)

    return sequences
  },
  { current: 1, max: 0 }
)
console.log('\nMax sequence:', max) //=> 5

The longest sequence is 5 consequtive numbers, at least with my puzzle input. We can manually map the possible arrangements of sequences of different lengths. The crucial thing is that the difference between any two numbers must not exceed 3. Here's the mapping:

// 1 consequtive number:
0 · · 3 · · 6
// → 1 arrangement

// 2 consequtive numbers:
0 · · 3 4 · · 7
// → 1 arrangement

// 3 consequtive numbers:
0 · · 3 4 5 · · 8
0 · · 3 · 5 · · 8
// → 2 arrangements

// 4 consequtive numbers:
0 · · 3 4 5 6 · · 9
0 · · 3 · 5 6 · · 9
0 · · 3 · · 6 · · 9
0 · · 3 4 · 6 · · 9
// → 4 arrangements

// 5 consequtive numbers:
0 · · 3 4 5 6 7 · · 10
0 · · 3 · 5 6 7 · · 10
0 · · 3 · · 6 7 · · 10
0 · · 3 4 · 6 7 · · 10
0 · · 3 4 · · 7 · · 10
0 · · 3 4 5 · 7 · · 10
0 · · 3 · 5 · 7 · · 10
// → 7 arrangements

If you find the above mapping hard to grasp, see the What did I learn? section. It has more mappings in a slightly different style.

Here's visual proof using one of the sample inputs that when the input contains a sequence of 4 consequtive numbers (→ 4 arrangements) and a sequence of 3 consequtive numbers (→ 2 arrangements), the total number of possible arrangements is 1 * 4 * 2 = 8:

// Input:
1 · · 4 5 6 7 · · 10 11 12 ·· ·· 15 16 ·· ·· 19

// Arrangements from the sequence of 4 consequtive numbers:
1 · · 4 · 6 7 · · 10 11 12 ·· ·· 15 16 ·· ·· 19
1 · · 4 · · 7 · · 10 11 12 ·· ·· 15 16 ·· ·· 19
1 · · 4 5 · 7 · · 10 11 12 ·· ·· 15 16 ·· ·· 19
//    ^^^^^^^

// Arrangement from the sequence of 3 consequtive numbers:
1 · · 4 5 6 7 · · 10 ·· 12 ·· ·· 15 16 ·· ·· 19
//                ^^^^^^^^

// Arrangements from both sequences:
1 · · 4 · 6 7 · · 10 ·· 12 ·· ·· 15 16 ·· ·· 19
1 · · 4 · · 7 · · 10 ·· 12 ·· ·· 15 16 ·· ·· 19
1 · · 4 5 · 7 · · 10 ·· 12 ·· ·· 15 16 ·· ·· 19
//    ^^^^^^^     ^^^^^^^^

// → Total of 8 possible arrangements

Notice how the input also contains a sequence of 2 consequtive numbers, but since it can be arranged only in one way, it doesn't affect the total number of possible arrangements.

With these things in mind, solving the puzzle is not that hard:

const multipliers = {
  1: 1,
  2: 1,
  3: 2,
  4: 4,
  5: 7,
}
const { arrangements } = numbers.reduce(
  (acc, n, i) => {
    if (n - prev(i) === 1) {
      acc.sequence++
    } else {
      acc.arrangements *= multipliers[acc.sequence]
      acc.sequence = 1
    }

    // In case the last number is part of a sequence of consequtive numbers
    if (i === numbers.length - 1) acc.arrangements *= multipliers[acc.sequence]

    return acc
  },
  { arrangements: 1, sequence: 1 }
)
console.log('Part 2:', arrangements)

Try out the final code on flems.io

What did I learn?

Nothing concrete, but finding a valid strategy for Part 2 was very challenging.

I didn't try a brute force approach because I think the puzzle hinted that it wouldn't be the best way:

You glance back down at your bag and try to remember why you brought so many adapters; there must be more than a trillion valid ways to arrange them! Surely, there must be an efficient way to count the arrangements.

I then manually mapped (sketched) the possible arrangements of sequences of different lengths. Where I went wrong is that I didn't check the length of the longest sequence, so I ended up doing unnecessary mappings:

Mappings

⬛ = number
⬜ = gap

E.g. this:
  ⬛⬜⬜⬛⬛⬛⬛⬜⬜⬛⬛⬛⬜⬜⬛⬛⬜⬜⬛
...is the representation of this:
  1 · · 4 5 6 7 · · 10 11 12 ·· ·· 15 16 ·· ·· 19

***

Sequence length: 1
⬛
→ Arrangements: 1

Sequence length: 2
⬛⬛
→ Arrangements: 1

Sequence length: 3
⬛⬛⬛
⬛⬜⬛
→ Arrangements: 2

Sequence length: 4
⬛⬛⬛⬛ = e.g. 1 2 3 4
⬛⬜⬛⬛        1 · 3 4
⬛⬜⬜⬛        1 · · 4
⬛⬛⬜⬛        1 2 · 4
→ Arrangements: 4

Sequence length: 5
⬛⬛⬛⬛⬛
⬛⬜⬛⬛⬛
⬛⬜⬜⬛⬛
⬛⬛⬜⬛⬛
⬛⬛⬜⬜⬛
⬛⬛⬛⬜⬛
⬛⬜⬛⬜⬛
→ Arrangements: 7

Sequence length: 6
⬛⬛⬛⬛⬛⬛
⬛⬜⬛⬛⬛⬛
⬛⬜⬜⬛⬛⬛
⬛⬛⬜⬛⬛⬛
⬛⬛⬜⬜⬛⬛
⬛⬛⬛⬜⬛⬛
⬛⬛⬛⬜⬜⬛
⬛⬛⬛⬛⬜⬛
⬛⬜⬛⬜⬛⬛
⬛⬜⬛⬜⬜⬛
⬛⬜⬛⬛⬜⬛
⬛⬜⬜⬛⬜⬛
⬛⬛⬜⬛⬜⬛
→ Arrangements: 13

Sequence length: 7
⬛⬛⬛⬛⬛⬛⬛
⬛⬜⬛⬛⬛⬛⬛
⬛⬜⬜⬛⬛⬛⬛
⬛⬛⬜⬛⬛⬛⬛
⬛⬛⬜⬜⬛⬛⬛
⬛⬛⬛⬜⬛⬛⬛
⬛⬛⬛⬜⬜⬛⬛
⬛⬛⬛⬛⬜⬛⬛
⬛⬛⬛⬛⬜⬜⬛
⬛⬛⬛⬛⬛⬜⬛
⬛⬜⬛⬜⬛⬛⬛
⬛⬜⬛⬜⬜⬛⬛
⬛⬜⬛⬛⬜⬛⬛
⬛⬜⬛⬛⬜⬜⬛
⬛⬜⬛⬛⬛⬜⬛
⬛⬜⬜⬛⬜⬛⬛
⬛⬜⬜⬛⬜⬜⬛
⬛⬜⬜⬛⬛⬜⬛
⬛⬛⬜⬛⬜⬛⬛
⬛⬛⬜⬛⬜⬜⬛
⬛⬛⬜⬛⬛⬜⬛
⬛⬛⬜⬜⬛⬜⬛
⬛⬛⬛⬜⬛⬜⬛
⬛⬜⬛⬜⬛⬜⬛
→ Arrangements: 24

Sequence length: 8
⬛⬛⬛⬛⬛⬛⬛⬛
⬛⬜⬛⬛⬛⬛⬛⬛
⬛⬜⬜⬛⬛⬛⬛⬛
⬛⬛⬜⬛⬛⬛⬛⬛
⬛⬛⬜⬜⬛⬛⬛⬛
⬛⬛⬛⬜⬛⬛⬛⬛
⬛⬛⬛⬜⬜⬛⬛⬛
⬛⬛⬛⬛⬜⬛⬛⬛
⬛⬛⬛⬛⬜⬜⬛⬛
⬛⬛⬛⬛⬛⬜⬛⬛
⬛⬛⬛⬛⬛⬜⬜⬛
⬛⬛⬛⬛⬛⬛⬜⬛
⬛⬜⬛⬜⬛⬛⬛⬛
⬛⬜⬛⬜⬜⬛⬛⬛
⬛⬜⬛⬛⬜⬛⬛⬛
⬛⬜⬛⬛⬜⬜⬛⬛
⬛⬜⬛⬛⬛⬜⬛⬛
⬛⬜⬛⬛⬛⬜⬜⬛
⬛⬜⬛⬛⬛⬛⬜⬛
⬛⬜⬜⬛⬜⬛⬛⬛
⬛⬜⬜⬛⬜⬜⬛⬛
⬛⬜⬜⬛⬛⬜⬛⬛
⬛⬜⬜⬛⬛⬜⬜⬛
⬛⬜⬜⬛⬛⬛⬜⬛
⬛⬛⬜⬛⬜⬛⬛⬛
⬛⬛⬜⬛⬜⬜⬛⬛
⬛⬛⬜⬛⬛⬜⬛⬛
⬛⬛⬜⬛⬛⬜⬜⬛
⬛⬛⬜⬛⬛⬛⬜⬛
⬛⬛⬜⬜⬛⬜⬛⬛
⬛⬛⬜⬜⬛⬜⬜⬛
⬛⬛⬜⬜⬛⬛⬜⬛
⬛⬛⬛⬜⬛⬜⬛⬛
⬛⬛⬛⬜⬛⬜⬜⬛
⬛⬛⬛⬜⬛⬛⬜⬛
⬛⬛⬛⬜⬜⬛⬜⬛
⬛⬛⬛⬛⬜⬛⬜⬛
⬛⬜⬛⬜⬛⬜⬛⬛
⬛⬜⬛⬜⬛⬜⬜⬛
⬛⬜⬛⬜⬛⬛⬜⬛
⬛⬜⬛⬜⬜⬛⬜⬛
⬛⬜⬛⬛⬜⬛⬜⬛
⬛⬜⬜⬛⬜⬛⬜⬛
⬛⬛⬜⬛⬜⬛⬜⬛
→ Arrangements: 44

Sequence length: 9
⬛⬛⬛⬛⬛⬛⬛⬛⬛
⬛⬜⬛⬛⬛⬛⬛⬛⬛
⬛⬜⬜⬛⬛⬛⬛⬛⬛
⬛⬛⬜⬛⬛⬛⬛⬛⬛
⬛⬛⬜⬜⬛⬛⬛⬛⬛
⬛⬛⬛⬜⬛⬛⬛⬛⬛
⬛⬛⬛⬜⬜⬛⬛⬛⬛
⬛⬛⬛⬛⬜⬛⬛⬛⬛
⬛⬛⬛⬛⬜⬜⬛⬛⬛
⬛⬛⬛⬛⬛⬜⬛⬛⬛
⬛⬛⬛⬛⬛⬜⬜⬛⬛
⬛⬛⬛⬛⬛⬛⬜⬛⬛
⬛⬛⬛⬛⬛⬛⬜⬜⬛
⬛⬛⬛⬛⬛⬛⬛⬜⬛
⬛⬜⬛⬜⬛⬛⬛⬛⬛
⬛⬜⬛⬜⬜⬛⬛⬛⬛
⬛⬜⬛⬛⬜⬛⬛⬛⬛
⬛⬜⬛⬛⬜⬜⬛⬛⬛
⬛⬜⬛⬛⬛⬜⬛⬛⬛
⬛⬜⬛⬛⬛⬜⬜⬛⬛
⬛⬜⬛⬛⬛⬛⬜⬛⬛
⬛⬜⬛⬛⬛⬛⬜⬜⬛
⬛⬜⬛⬛⬛⬛⬛⬜⬛
⬛⬜⬜⬛⬜⬛⬛⬛⬛
⬛⬜⬜⬛⬜⬜⬛⬛⬛
⬛⬜⬜⬛⬛⬜⬛⬛⬛
⬛⬜⬜⬛⬛⬜⬜⬛⬛
⬛⬜⬜⬛⬛⬛⬜⬛⬛
⬛⬜⬜⬛⬛⬛⬜⬜⬛
⬛⬜⬜⬛⬛⬛⬛⬜⬛
⬛⬛⬜⬛⬜⬛⬛⬛⬛
⬛⬛⬜⬛⬜⬜⬛⬛⬛
⬛⬛⬜⬛⬛⬜⬛⬛⬛
⬛⬛⬜⬛⬛⬜⬜⬛⬛
⬛⬛⬜⬛⬛⬛⬜⬛⬛
⬛⬛⬜⬛⬛⬛⬜⬜⬛
⬛⬛⬜⬛⬛⬛⬛⬜⬛
⬛⬛⬜⬜⬛⬜⬛⬛⬛
⬛⬛⬜⬜⬛⬜⬜⬛⬛
⬛⬛⬜⬜⬛⬛⬜⬛⬛
⬛⬛⬜⬜⬛⬛⬜⬜⬛
⬛⬛⬜⬜⬛⬛⬛⬜⬛
⬛⬛⬛⬜⬛⬜⬛⬛⬛
⬛⬛⬛⬜⬛⬜⬜⬛⬛
⬛⬛⬛⬜⬛⬛⬜⬛⬛
⬛⬛⬛⬜⬛⬛⬜⬜⬛
⬛⬛⬛⬜⬛⬛⬛⬜⬛
⬛⬛⬛⬜⬜⬛⬜⬛⬛
⬛⬛⬛⬜⬜⬛⬜⬜⬛
⬛⬛⬛⬜⬜⬛⬛⬜⬛
⬛⬛⬛⬛⬜⬛⬜⬛⬛
⬛⬛⬛⬛⬜⬛⬜⬜⬛
⬛⬛⬛⬛⬜⬛⬛⬜⬛
⬛⬛⬛⬛⬜⬜⬛⬜⬛
⬛⬛⬛⬛⬛⬜⬛⬜⬛
⬛⬜⬛⬜⬛⬜⬛⬛⬛
⬛⬜⬛⬜⬛⬜⬜⬛⬛
⬛⬜⬛⬜⬛⬛⬜⬛⬛
⬛⬜⬛⬜⬛⬛⬜⬜⬛
⬛⬜⬛⬜⬛⬛⬛⬜⬛
⬛⬜⬛⬜⬜⬛⬜⬛⬛
⬛⬜⬛⬜⬜⬛⬜⬜⬛
⬛⬜⬛⬜⬜⬛⬛⬜⬛
⬛⬜⬛⬛⬜⬛⬜⬛⬛
⬛⬜⬛⬛⬜⬛⬜⬜⬛
⬛⬜⬛⬛⬜⬛⬛⬜⬛
⬛⬜⬜⬛⬜⬛⬜⬛⬛
⬛⬜⬜⬛⬜⬛⬜⬜⬛
⬛⬜⬜⬛⬜⬛⬛⬜⬛
⬛⬜⬜⬛⬜⬜⬛⬜⬛
⬛⬜⬜⬛⬛⬜⬛⬜⬛
⬛⬛⬜⬛⬜⬛⬜⬛⬛
⬛⬛⬜⬛⬜⬛⬜⬜⬛
⬛⬛⬜⬛⬜⬛⬛⬜⬛
⬛⬛⬜⬛⬜⬜⬛⬜⬛
⬛⬛⬜⬛⬛⬜⬛⬜⬛
⬛⬛⬜⬜⬛⬜⬛⬜⬛
⬛⬛⬛⬜⬛⬜⬛⬜⬛
⬛⬜⬛⬜⬛⬜⬛⬜⬛
→ Arrangements: 79

The longest sequence (9 consequtive numbers) produces 79 arrangements. I did those mappings by hand. 😅

Doing the mappings was difficult (until I found a good strategy for that) and unnecessarily time consuming. And error-prone – I'm not even sure if 79 is the correct amount of arrangements for 9-number sequences.

I then tried to come up with a mathematical formula for the numbers: 1 → 1 → 2 → 4 → 7 → 13 → 24 → 44 → 79. Doesn't seem logical, so I don't have a formula to give to you. (Addendum: It looks like Tribonacci numbers, except that the 79 should be 81. Maybe I have missed two cases from the mapping.)

I'm not sure what my point is. Anyway, I did unnecessary work because I didn't stop to think what is useful and needed for solving the puzzle. Doing those looong mappings was unnecessary.