Advent of Code 2020: Day 9

, 9 min read
advent of code 2020 summary

Part 1

With your neighbour happily enjoying their video game, you turn your attention to an open data port on the little screen in the seat in front of you.

Though the port is non-standard, you manage to connect it to your computer through the clever use of several paperclips. Upon connection, the port outputs a series of numbers (your puzzle input).

The data appears to be encrypted with the eXchange-Masking Addition System (XMAS) which, conveniently for you, is an old cypher with an important weakness.

XMAS starts by transmitting a preamble of 25 numbers. After that, each number you receive should be the sum of any two of the 25 immediately previous numbers. The two numbers will have different values, and there might be more than one such pair.

The first step of attacking the weakness in the XMAS data is to find the first number in the list (after the preamble) which is not the sum of two of the 25 numbers before it. What is the first number that does not have this property?

You can read the full text here. Oh no, what are we up to now? After hacking a game, are we now about to hack the Aeroplane computer system?

This is a fun problem. We have a long list of numbers and each number is valid if it is equal to sum of any two of the previous M numbers. M is the size of the preamble, and for this puzzle it remains fixed at 25. We exclude the first M numbers from the criteria, they are all valid.

We want to try and optimise this in real-time. Thus, we won’t be reading all of the numbers into memory; instead, we will loop over the file and read in each number one at a time. Great, but how do we check the number is valid? We don’t want to recompute the previous M * M sums repeatedly looking for a match, as this would give a time complexity of O(N * M * M) where O(N) is the number of inputs.

We can cache the previous M numbers that we have seen in a list. Then we can store their pair sums in a map. For each new number we loop through the previous M-1 numbers and calculate the pair sum, we then increment our map counter. Thus, the map which we call cached stores how many times our previous M numbers sum to give the value x. When we add a new number to the preamble we add the pair sums to the cache, and when we remove a number we just subtract from the cache.

In C++ the code for this might look like:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
std::list<long int> preamble;
std::list<long int>::iterator it;
std::map<long int, long int> cached;
while(std::getline(myfile, line)){
	long int num = std::stol(line);
	// Break if value not in cache
	if(preamble.size() == preamble_max_size){
		if (cached[num] == 0){
			ans1 = num;
			break;
		}
		// Remove oldest value from preamble, and it's contributions to the cache
		int rem = preamble.front();
		preamble.pop_front();
		it = preamble.begin();
		while (it != preamble.end()){
			cached[*it + rem]--;
			it = std::next(it);
		}
	}
	// Add new values contribution to cache, and then insert the new value to preamble
	it = preamble.begin();
	while (it != preamble.end()){
		cached[*it + num]++;
		it = std::next(it);
	}
	preamble.push_back(num);
}

First of all, we read the new number from the file and convert it to a long integer, this is important as the numbers in this puzzle are very large. If our preamble is full, e.g. we are already storing M numbers then we need to validate this number. Thus, we just check if the value of this number is greater than zero in our cache, that means at least one pair of the previous M numbers that sum to this value.

Once we have validated the number, we must then update our preamble to include this value and remove the oldest value. We start by removing the oldest number in the list and removing all of its contributions from the hash map we are using as a cache. We then add the new number to the back of the preamble list and compute its pair sums with the other M-1 values and add those to our cache. Great - now we can move on and validate the next number.

We run this code on our input and unlock the first ⭐!

The full code can be found on github

Part 2

The final step in breaking the XMAS encryption relies on the invalid number you just found: you must find a contiguous set of at least two numbers in your list which sum to the invalid number from step 1.

To find the encryption weakness, add together the smallest and largest number in this contiguous range;

What is the encryption weakness in your XMAS-encrypted list of numbers?

You can read the full text here.

This is a classic competitive programming problem. Find the contiguous subarray with a given sum. We are going to solve this using the ideas from a double-pointer technique. We start with the first value in our input and a current sum of zero. We loop through the numbers incrementing our sum until it is greater than the desired value. When our sum is too large, we remove the elements, in a first-in-first-out order, until the sum is less than the target. We then continue looping through our input, adding more values to the sum. This process repeats until we have the desired sum. As I don’t have the numbers in memory, I’m using a list to store the current subsequence and sum.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
std::list<long int> sequence;
long int sum = 0;
while(std::getline(myfile, line)){
	// Add new number to sequence
	long int num = std::stol(line);
	sum += num;
	sequence.push_back(num);

	// If too large, remove some older values
	while (sum > ans1){
		sum -= sequence.front();
		sequence.pop_front();
	}

	// Have we found the solution?
	if (sum == ans1)
		break;
}

The first thing we do in the loop is read in our new value, add it to the end of our list and increment the sum. If the sum is too large, then we start removing the oldest values from the list and decreasing the sum. Finally, we check if we have reached the solution, if not, we keep going and add more values to the sequence. Once this loop breaks, we have the subsequence with the correct sum. Thus, we can easily find the maximum and minimum values and unlock the second ⭐.

The full code can be found on github

Reflections

I think the solution we implemented is fairly optimal today. For part 1 our time complexity scales as O(N * M) where N is the amount of numbers in the input, and M is the size of the preamble. This is because for each new value we read in, we must compute M sums to add it to our cache. The space complexity of the problem is, at worst, O(M * M) which is the size of our cache when every pair of numbers adds to a different value.

In part 2, I still resisted from reading the input into a vector and instead looped through the file. As we only loop through the file once the time complexity is just O(N). However, as we decided not to read in the file, we must store the current subsequence in memory. The worst-case scenario from a memory perspective is when the subsequence is approximately the full length of the input. As such, the space complexity of this solution is O(N). I could have just read the input into memory and applied the traditional double-pointer technique. It would give the same complexity.

I really enjoyed today’s problem, and I hope you did too. See you tomorrow!

Updates (11/12/20)

For the complexities I claimed in my reflections I should have used an unordered_map. I also accessed the map in a fairly inefficient way. I should have used an iterator to find elements and then delete when the value reduced to zero. The overloaded [] lead to an unwieldy growth of my cache. I need to get more familiar with C++.

Thus for part 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
while (std::getline(myfile, line)) {
	long int num = std::stol(line);
	if (preamble.size() == preamble_max_size) {
		// Can we find the pair of numbers which sum?
		bool found = false;
		it = preamble.begin();
		while (it != preamble.end()) {
			cached_it = cached.find(num - *it);
			if (cached_it != cached.end()) found = true;
			it = std::next(it);
		}
		if (found == false) {
			ans1 = num;
			break;
		}
		// Remove oldest value from preamble
		int rem = preamble.front();
		preamble.pop_front();
		// remove value from cache
		cached_it = cached.find(rem);
		if (cached_it != cached.end()){
			if ((*cached_it).second == 1)
				cached.erase(cached_it);
			else{
				(*cached_it).second--;
			}
		}
	}
	cached[num]++;
	preamble.push_back(num);
}

Instead of caching M * M numbers I store the preamble simultaneously in a unordered_map and a list. Thus, for each new value I loop through the list and see if the value minus that each preamble value is in my unordered_map, this should be a constant look up, O(1).

Then using my list I can remove the oldest preamble value from my unordered_map, and from the list. Thus, the list only exists to store the order of my preamble, and unordered_map exists for rapid lookup.

For part 1 our time complexity now scales as O(N * M) where N is the amount of numbers in the input, and M is the size of the preamble. This is because for each new value we read in, we must compute M sums to check if it is valid. The space complexity of the problem is, at worst, O(M) which is the size of our unordered_map and list.

. . . .

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