For day 9, we’re trying to break a simple encryption scheme. Our input starts with a preamble of 25 numbers. From there, it continues with a series of additional numbers. Each number must be equal to the sum of any two of the previous 25 numbers. We’re trying to find the first number that doesn’t meet that rule.
Because we’re looking at a fixed window of 25 numbers, I did some research and discovered the deque class within the collections package. There are a number of cool things about deque. First, it allows for the easy addition or removal of an item on either side of the variable (left or right side). The other thing which is what I really liked in this case, is that you can set max length. When that is done, if I hit that max length and then add another value on one side, it will automatically pop the last value on the other side of the register.
To solve the problem was fairly straight forward. Start by loading the first 25 values into the deque. From there, look at the next value on our list. I used the combination function to give me all of the combinations of 2 values within the current contents of the deque. From there, cycle through the combinations and finding each sum until we found one that matched. If we made it to the end, then that current value was the answer.
Part two played off the value found in part 1. Basically what it says is that, from the corrupt number that we found, going back to previous valid input, there was a contiguous range of numbers that when you add them together will give you the corrupt value.
To solve this, I used the corrupt value as the ending point of a loop. Starting from the beginning of the preamble it cycles through the sum of the numbers until it hits the corrupt number. If the sum matches the corrupt value, great, and if not, it moves one number up in the list as it’s starting point until we eventually find the range of numbers we’re looking for.
My complete solution is found here.