Adapter Array
Tags: adventofcode, algorithms, computerscience, programming
Published: 2022-04-06 12:26:30

## [Advent of Code 2020 Day 10](https://adventofcode.com/2020/day/10)

## [Try the simulator for Part 2 using NullDev's algorithm](https://aocadapterarray.rmion.repl.co/)
![Simulator of NullDev's Part 2 algorithm](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/crqoc2vv3r5mz04bg505.gif)

## Task: Solve for `X` where `X =`
1. The product of the count of 1- and 3-integer differences between sorted jolt measures
2. The total number of distinct ways you can arrange the adapters

### Example input
```
16
10
15
5
1
11
7
19
6
12
4
```

It represents:
- A collection of adapters
- Each of their output joltage

## Part 1
1. Confusion, then clarity, then confidence
2. Writing a working algorithm

### Confusion, then clarity, then confidence
- Confusion: The introductory sentences of this puzzle made me concerned that I'd have no idea where to begin
- Clarity: The walkthrough using the example input helped me understand what the rules of this puzzle were
- Confidence: I knew immediately how I would solve it algorithmically - and thankfully my algorithm worked!

### Writing a working algorithm
```
Process the input into a sorted array of numbers

Insert two values: one at the beginning and another at the end

Accumulate a 3-element array representing tallies for each 1-, 2- and 3-integer difference between each subsequent value

Return the product of the integers tallying all 1- and 3-integer differences
```

Here's a visualization of my algorithm:
![Part 1 algorithm visualization](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/la6nyuyldu0gaiynyt5p.gif)

## Part 2
1. I should have seen that coming
2. I thought I figured it out
3. I knew it was that simple!
4. I had to see how it worked

### I should have seen that coming
- When Part 1 feels easy - to me! - it is often a sign that Part 2 is a test of speed...which I'm often unequipped to solve
- Given the 1, 2 and 3-integer differences, it should have been clear that Part 2 would be a test of 'how many possible arrangements?'

### I thought I figured it out
Using the first example input as reference, the numbers in order are:
```
1, 4, 5, 6, 7, 10, 11, 12, 15, 16, 19
```

My faulty logic followed this path toward a solution:
```
Legend:
0 numbers in-between = 1
1 number in-between  = 2
2 numbers in-between = 4

1 - 4:   0 -> 1
4 - 7:   2 -> 4
7 - 10:  0 -> 1
10 - 12: 1 -> 2
12 - 15: 0 -> 1
15 - 16: 0 -> 1
16 - 19: 0 -> 1

1 * 4 * 1 * 2 * 1 * 1 * 1
4 * 2
8
```

Sadly, using this formula on the second example produced ~2000, not 19208.

### I knew it was that simple!
Thankfully, my go-to JavaScript solver, NullDev, wrote an elegant, sub-5-line solution that I felt compelled to fully understand...using simulation!

```
Create step, a 1-element array containing the value 1
For i from 0 to the maximum value in the sorted array of numbers from the input
  Set j to i + 1
  While the number at location j in the sorted array is less than or equal to i + 3
    Set the item at location j in step equal to the sum of the item at location i in step and either the item at location j in step or 0
    Increment j
Return the last value in step
```

I was confused about how NullDev's algorithm worked when reasoning about it in my head.

Even after using `console.log` at the end to show the filled `step` array, I still didn't see what it was doing in each iteration.

I knew I needed to simulate each iteration.

### I had to see how it worked
- Re-factoring NullDev's code into `if...else` clauses instead of combination of `for` and `while` loops wasn't too difficult
- The result is a simulator that renders a list which grows taller and always shows the last value at the top
- It finally helped me realize how NullDev's algorithm goes '3 steps forward, 2 steps back' in a way to continually double each value

[Try the simulator for Part 2 using NullDev's algorithm](https://aocadapterarray.rmion.repl.co/)
![Simulator of NullDev's Part 2 algorithm](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/crqoc2vv3r5mz04bg505.gif)

Seeing NullDev's solution showed me that I was 'on to something' in my 1-2-4 doubling logic. Though, clearly my approach was too shallow.

I may not have solved Part 2, but I had fun noodling around with this puzzle and simulating another solver's algorithm.