X = the first number that is not the sum of two of the N numbers before it
and N = 25
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
35 20 15 25 47 40 62 55 65 95 102 117 150 182 127 219 299 277 309 576
- Just a series of numbers
- Visualizing a 'descending staircase' algorithm
- Trying to write that algorithm...then stopping
- A much simpler, working 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?
- 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)
- 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
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
- Where to start, the beginning or end?
- Writing a working algorithm
- 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
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