# Advent of Code 2020: Day 9

## 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 preamble; std::list::iterator it; std::map 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 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!

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