Advent of Code day 9

Today we will hack into our airplane's data port (somehow I'm guessing this would be a bit more difficult in real life).

The set up:

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.

For part 1 we need to find to find the first number that does not match the XMAS code (i.e. the first number that is not a combination of two numbers from the 25 previous.)

For this we can just use python's itertools module to find all the combinations of 2 numbers in the preamble and compare that list of sums to the number we have. When the number is not in the list of sums, we know we have the invalid one.

For part two, we need to

find a contiguous set of at least two numbers in your list which sum to the invalid number from step 1.

Since the numbers have to be contiguous, this is not an easy itertools problem.
We’ll have to code it by hand.

I’m going to start by using loops. Loops are generally avoided in cases like this because they are inefficient, but I believe I can add efficiencies that will make it worth it. For example, if the sum of code[1:n] is larger than my target number, I know for sure that the same of [1:n+1] will also be, so I can just exit the loop at that point.

I use a double set of loops (one to determine where my set of contiguous values starts and one for where it ends). It actually runs really quickly and I get the answer (see Github for details).

I thought about redoing the code by generating the list of ranges first, and then checking them all (thereby going from two loops to just one), but my solution ran so quickly I didn’t bother.