Advent of Code 2020: Day 10

, 7 min read
advent 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 built-in joltage adapter rated for 3 jolts higher than the highest-rated adapter in your bag. (If your adapter list were 3, 9, and 6, your device’s built-in 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 built-in adapter and count the joltage differences between the charging outlet, the adapters, and your device. What is the number of 1-jolt differences multiplied by the number of 3-jolt 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 built-in C++ sort,

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
std::fstream myfile("input", std::ios_base::in);
std::string line;
std::vector<int> adapters = {0};
while(std::getline(myfile, line)){
	adapters.push_back(std::stoi(line));
	maxv = std::max(std::stoi(line), maxv);
}
adapters.push_back(maxv + 3);
myfile.close();
// Now sort
std::sort(adapters.begin(), adapters.end());

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,

1
2
3
4
5
6
7
int num1s = 0, num3s = 0;
for(size_t i=1; i<adapters.size(); i++){
	int diff = adapters[i] - adapters[i-1];
	if (diff == 3) num3s++;
	else num1s++;
}
ans1 = num1s * num3s;

That’s all we have to do, and we have the first ⭐!

The full code can be found on github

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:

1
0, 1, 3, 6, 7, 8, 9

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

1
0, .., 3, 6, .., 9

We must start at 0, then we must also step from 3-6, we must also step from 9-12. We can then break this down into 2 subsequences,

1
2
0, .., 3
6, .., 9

The number of ways of getting from 0-9 can then be written as a product of how many ways we can get from 0-3 and how many ways we can get from 6-9. As for each route in 6-9, we could couple this with every route in 0-3. 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?

1
2
0, 1, 3
0, 3

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

1
2
3
4
6, 7, 8, 9
6, 7, 9
6, 8, 9
6, 9

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

1
0, 1, 2, 3, 4

we could traverse this in the following ways,

1
2
3
4
5
6
7
0, 1, 2, 3, 4
0, 1, 2, 4
0, 1, 3, 4
0, 2, 3, 4
0, 1, 4
0, 2, 4
0, 3, 4

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:

1
2
3
3 numbers: 2 ways
4 numbers: 4 ways
5 numbers: 7 ways

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
long int poss = 1;
size_t lp = 0;
size_t rp = 0;
std::cout << adapters.size() << std::endl;
while (rp < adapters.size()){
	// Lets move along
	lp = rp;
	// How big a group until only one possible step?
	rp++;
	while ((rp < adapters.size()) && (adapters[rp] != adapters[rp-1]+3))
		rp++;
	// These are the possible subgroups
	if ((rp - lp) == 3) poss *= 2;
	else if ((rp - lp) == 4) poss *= 4;
	else if ((rp - lp) == 5) poss *= 7;
}
ans2 = poss;

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, ⭐⭐!

The full code can be found on github

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 double-pointer 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

Back to my advent calendar

Comments

Back to all posts