Day 9. Encoding Error

Problem statement

https://adventofcode.com/2020/day/9 (mirror)

---

My solution

This day involves a basic dynamic programming concept.

We need to memorize 25 previous numbers from the input list, and check if the next one is a sum of any two from those previous numbers.

While a queue on surface looks like an ideal fit, we want to be able to easily access all of its elements, not only the first one. Therefore, we will use a list, and overwrite the “oldest” number – which will always be at index currentIndex % PreambleSize (where PreambleSize == 25 is a constant).

for (int i = PreambleSize; i < inputLines.Length; i++)
{
    long nextNumber = Int64.Parse(inputLines[i]);
    if (!IsValid(nextNumber, previousNumbers))
    {
        return nextNumber.ToString();
    }
    else
    {
        int indexToReplace = i % PreambleSize;
        previousNumbers[indexToReplace] = nextNumber;
    }
}

Method IsValid naively compares all possible sums of two numbers from the list of previous 25 to the next number. We keep it simple – sorting / using binary search would make the search quicker, but it would complicate finding the oldest number.

---

In Part B, we need to find consecutive numbers that sum to the number X found in Part A. Because all numbers in input are positive, we will use a sliding window (technically, I belive that a sliding window should have a constant width, but the name is a good fit here as well).

A sliding window has a first (front) index, second (back) index, and sum value. We initialize the front index to 1, back one to 0, and sum to the sum of two first elements from input.

If current sum of sliding window is smaller than X, we widen the window (we increment the front index) so that it includes the next number from input. Because the next number is positive, the sum of the window increases.

Similarly, if the sum of the window is greater than X, we exclude the furthest number from the window (increment the back index), which decreases the sum.

We also need to keep the front index greater than the back index – since the problem description states that we:

[…] must find a contiguous set of at least two numbers […]

The sliding window approach allows us to solve Part B in O(n) time.