part1 (2537B)
1--- Day 9: Encoding Error --- 2 3With your neighbor happily enjoying their video game, you turn your attention to an open data port 4on the little screen in the seat in front of you. 5 6Though the port is non-standard, you manage to connect it to your computer through the clever use of 7several paperclips. Upon connection, the port outputs a series of numbers (your puzzle input). 8 9The data appears to be encrypted with the eXchange-Masking Addition System (XMAS) which, 10conveniently for you, is an old cypher with an important weakness. 11 12XMAS starts by transmitting a [1m[37mpreamble[0m of 25 numbers. After that, each number you 13receive should be the sum of any two of the 25 immediately previous numbers. The two numbers will 14have different values, and there might be more than one such pair. 15 16For example, suppose your preamble consists of the numbers 1 through 25 in a random order. To be 17valid, the next number must be the sum of two of those numbers: 18 19- 26 would be a [1m[37mvalid[0m next number, as it could be 1 plus 25 (or many other pairs, like 202 and 24). - 49 would be a [1m[37mvalid[0m next number, as it is the sum of 24 and 25. - 100 21would [1m[37mnot[0m be valid; no two of the previous 25 numbers sum to 100. - 50 would also 22[1m[37mnot[0m be valid; although 25 appears in the previous 25 numbers, the two numbers in the 23pair must be different. 24 25Suppose the 26th number is 45, and the first number (no longer an option, as it is more than 25 26numbers ago) was 20. Now, for the next number to be valid, there needs to be some pair of numbers 27among 1-19, 21-25, or 45 that add up to it: 28 29- 26 would still be a [1m[37mvalid[0m next number, as 1 and 25 are still within the previous 25 30numbers. - 65 would [1m[37mnot[0m be valid, as no two of the available numbers sum to it. - 64 31and 66 would both be [1m[37mvalid[0m, as they are the result of 19+45 and 21+45 respectively. 32 33Here is a larger example which only considers the previous [1m[37m5[0m numbers (and has a 34preamble of length 5): 35 3635 20 15 25 47 40 62 55 65 95 102 117 150 182 127 219 299 277 309 576 37 38In this example, after the 5-number preamble, almost every number is the sum of two of the previous 395 numbers; the only number that does not follow this rule is [1m[37m127[0m. 40 41The first step of attacking the weakness in the XMAS data is to find the first number in the list 42(after the preamble) which is [1m[37mnot[0m the sum of two of the 25 numbers before it. 43[1m[37mWhat is the first number that does not have this property?[0m 44 45