Advent of Code 2020: Day 10
, 7 min readadvent of code 2020
Part 1
Patched into the aircraft’s data port, you discover weather forecasts of a massive tropical storm. Before you can figure out whether it will impact your vacation plans, however, your device suddenly turns off! Its battery is dead.
You’ll need to plug it in. There’s only one problem: the charging outlet near your seat produces the wrong number of jolts. Always prepared, you make a list of all of the joltage adapters in your bag.
Each of your joltage adapters is rated for a specific output joltage (your puzzle input). Any given adapter can take an input 1, 2, or 3 jolts lower than its rating and still produce its rated output joltage.
In addition, your device has a builtin joltage adapter rated for 3 jolts higher than the highestrated adapter in your bag. (If your adapter list were 3, 9, and 6, your device’s builtin adapter would be rated for 12 jolts.) Treat the charging outlet near your seat as having an effective joltage rating of 0.
Find a chain that uses all of your adapters to connect the charging outlet to your device’s builtin adapter and count the joltage differences between the charging outlet, the adapters, and your device. What is the number of 1jolt differences multiplied by the number of 3jolt differences?
You can read the full text here. Part 1 is fairly easy. We have a puzzle input with a list of adapters with joltage ratings. If we order these adapters by the joltage rating, then the difference between adjacent adapters is either 1 or 3.
We should also append 0, and our maximum value+3 to our numbers, as the puzzle description states the wall is 0, and our device is our maximum joltage adapter+3.
The easiest way to solve this problem is to sort the sequence of numbers and then loop over them and calculate the joltage difference between each pair of components. Note, I also have the foresight that part 2 will benefit from a sorted sequence.
For this problem, we’re just reading in the inputs, the usual way, and using the builtin C++ sort,


A standard sort is usually O(N log N)
time, where N
is the number of elements. However, it is possible to sort this particular sequence in O(N)
time as the maximum value in the sequence is small, we can allocate an array
of length the maximum value, fill and reduce.
After we’ve sorted the sequence we can loop through the vector
and count the number of pairs which differ by 1 or 3,


That’s all we have to do, and we have the first ⭐!
Part 2
To completely determine whether you have enough adapters, you’ll need to figure out how many different ways they can be arranged. Every arrangement needs to connect the charging outlet to your device. The previous rules about when adapters can successfully connect still apply
You can read the full text here.
Part 2 is a lot more challenging. There is some indication in the puzzle text that this problem shouldn’t be attempted with a brute force attempt. Instead, we have to go to pen and paper to derive a more optimal solution.
Let us consider the following set of numbers:


We start by noticing there are some steps in the sequence which cannot be changed. These are,


We must start at 0, then we must also step from 36, we must also step from 912. We can then break this down into 2 subsequences,


The number of ways of getting from 09 can then be written as a product of how many ways we can get from 03 and how many ways we can get from 69. As for each route in 69, we could couple this with every route in 03. This would just continue for more subsequences.
Thus, now we have simplified our problem by breaking at the points where there is only one possibility. These points are when there is a difference of 3.
How many ways can we go from 0 to 3?


there are 2 ways. Now, what about 6 to 9?


there are 4 ways. Let’s just consider a more complicated subsequence,


we could traverse this in the following ways,


thus there are 7 ways. Now in my input breaking at gaps of 3 never produces a subsequence that is longer than 5 numbers. However, if there was, it is possible to derive the number of ways of getting between the start and endpoint. These sequences are general as all numbers in the input are separated by either 1 or 3.
Now the problem is much more simple. We must loop through our ordered list, selecting subsequences bounded by gaps of 3. We can calculate how many permutations that subsequence contributes, just from the subsequence length:


We can implement this C++ with the following code:


Each time we find a subsequence, we multiply the total number of permutations by the number of permutations contributed by that subsequence. Then we move on to the next subsequence.
Not too bad, just takes a lot of messing about with simple subsequences with pen and paper, ⭐⭐!
Reflections
I think we have implemented the optimal solution for both parts of the problem,
barring that we could have written our own O(N)
sorting solution, where N
is the number of adapters.
In part 1, our solution is O(N log N)
time and O(N)
space. However, it could be improved to achieve O(N)
time with a different sorting algorithm.
Then in part 2, our main loop is also O(N)
time, as it is just a classic doublepointer problem. Thus, we are still bounded by the sorting from part 1. Therefore, the solution is again O(N log N)
time and O(N)
space. Not sure this can be improved today!
Thanks for reading and apologies for the delayed post date.
I have no affiliation with AoC. I’m just a fan of the programming puzzles. If you enjoy them too, please feel free to join in and support the creators