Encoding Error

Advent of Code 2020 Day 9

Here's a visualization of both my algorithms using the example input:

Task: Solve for X where...

Part 1:

X = the first number that is not the sum of two of the N numbers before it

and N = 25

Part 2:

X = the sum of the smallest and largest numbers included in a list of contiguous numbers from the puzzle input that sum to the number identified in Part 1

Example input where N = 5

35
20
15
25
47
40
62
55
65
95
102
117
150
182
127
219
299
277
309
576

It represents:

• Just a series of numbers

Part 1

1. Visualizing a 'descending staircase' algorithm
2. Trying to write that algorithm...then stopping
3. A much simpler, working algorithm

Visualizing a 'descending staircase' algorithm

It seems we need to track all possible sums among a group of numbers.

Let's say those numbers are 1-5

   1 2 3 4 5

1  2 3 4 5 6
2  3 4 5 6 7
3  4 5 6 7 8
4  5 6 7 8 9
5  6 7 8 9 10

Next, we must exclude sums from adding the same number twice

   1 2 3 4 5

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

And we've got our sums.

It seems a formula here could be:

Where N = the size of the group
N * (N - 1) = the amount of sums to track

N = 5
5 * (5 - 1) = 20 sums to track

N = 25
25 * (25 - 1) = 225 sums to track

Say the first number to check as an included sum is 6:

   1 2 3 4 5

1    3 4 5 6
2  3   5 6 7
3  4 5   7 8  <-- 6?
4  5 6 7   9
5  6 7 8 9  

Yup! It's in there.

How should the group of sums adjust?

Here's a visual I made to show exactly that:

Each turn:

• All sums from the earliest number are removed
• The sum formed using the earliest number with each subsequent number is removed
• An element is added to each subsequent number's subset that contains the sum of that number and the number that was just checked for inclusion in the group
• A new subset is added at the end and filled with values containing the sum of the newly added number and each of the pre-summed numbers in the ever-shifting list (minus the one that used to be at the front)

Trying to write that algorithm...then stopping

• It started with nested loops: to generate a grid of sums from each number
• It then quickly devolved into a series of array look-up, deletion and insertion steps that felt all kinds of wrong
• I stopped writing the algorithm when I couldn't figure out how to insert an element at the location one greater than the value of an incrementing counter - because at that point my effort felt futile

A much simpler, working algorithm

I laid down for bed, and the answer hit me!

Forget about storing and updating a list of sums

Store the puzzle input as an array of numbers

Create and store the preamble subset

Check as many numbers needed in the preamble until a match is found for the inclusion of the number that equals the next number in the input list minus the number being checked
  If a match is found
    Escape the loop immediately with an indication that a match was found

Update the preamble subset such that the first number is removed and the next number in the input list is added
  Else, if no match is found
    Return the next number in the input list

Here's a visualization of that algorithm:

Part 2

1. Where to start, the beginning or end?
2. Writing a working algorithm

Where to start, the beginning or end?

• In the illustrated example, the contiguous set of numbers that sum to the first invalid number are closer to the beginning of the list
• But, the first invalid number in my puzzle input is closer to the end of the list
• So, I could create an algorithm that starts at the beginning
• But that seems less performant given the length of the list, the length of the contiguous lists that I'll have to accumulate from the much smaller numbers at the beginning, and because it seems smarter to assume the contiguous list of numbers is closer to the invalid number than the beginning of the list

It is decided: start from one before the invalid number and work backward, not from the beginning of the input list and work forward

Writing a working algorithm

Run Part 1's algorithm to identify the first invalid number
Store the location of that number in the puzzle input list
Initialize an incrementing value i to 1
Create an empty array, nums
Do as long as the numbers stored in nums do not sum to the invalid number
  Set an incrementing value j to i
  Do as long as the numbers stored in nums sum to a value less than the invalid number
    Insert in nums the value from the puzzle input at the location equivalent to the location of the invalid number minus the value stored in j
    Increment j by 1
  If, by now, nums is empty or the numbers stored in nums sum to a value greater than the invalid number
    Reset nums to an empty array
    Increment i by 1
Return the sum of the highest and lowest numbers in nums

It seems I was smart to start from the invalid number near location 650, because for my puzzle input the contiguous list of 17 numbers started around location 500

Here's a visualization of both my algorithms using the example input: