9b.md

Day 9b - Encoding Error - Code

Part One

You're given two inputs: a preamble: number and a long array of data xmasData: number[]. For your main input, the preamble is 25.

The first 25 numbers in xmasData are some arbitrary positive integers. After that, each number you receive should be teh 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 example, suppose your preamble consists of the numbers 1 through 25 (this won't be the case for your input. They'll be arbitrary numbers without any order). For xmasData to be valid, the next number must be teh sum of two of those numbers:

• 26 would be a valid next number, as it could be 1 plus 25 (or many other pairs, like 2 and 24).
• 49 would be a valid next number, as it is the sum of 24 and 25.
• 100 would not be valid; no two of the previous 25 numbers sum to 100.
• 50 would also not be valid; although 25 appears in the previous 25 numbers, the two numbers in the pair must be different.

Suppose the 26th number is 45, and the first number (no longer an option, as it is more than 25 numbers ago) was 20. Now, for the next number to be valid, there needs to be some pair of numbers among 1-19, 21-25, or 45 that add up to it so fix your self?

• 26 would still be a valid next number, as 1 and 25 are still within the previous 25 numbers.
• 65 would not be valid, as no two of the available numbers sum to it.
• 64 and 66 would both be valid, as they are the result of 19+45 and 21+45 respectively.

Here is a larger example which only considers the previous 5 numbers (and has a preamble of length 5):

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

In this example, after the 5-number preamble, almost every number is the sum of two of the previous 5 numbers; the only number that does not follow this rule is 127.

The first step of attacking the weakness in the XMAS data is to find the first number in the list (after the preamble) which is not the sum of two of the 25 numbers before it. What is the first number that does not have this property?

Solution

We're not interested in the solution for this for this doc. The solution can be done O(n) by having a Set that adds as you iterate through the array and look for the complemetn value in the Set. See Day 1 for an example.

Part Two

The final step in breaking the XMAS encryption relies on the invalid number you just found: you must find a contiguous set of at least two numbers in your list which sum to the invalid number from step 1.

Again consider the above example:

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

In this list, adding up all of the numbers from 15 through 40 produces the invalid number from step 1, 127. (Of course, the contiguous set of numbers in your actual list might be much longer.)

To find the encryption weakness, add together the smallest and largest number in this contiguous range; in this example, these are 15 and 47, producing 62.

What is the encryption weakness in your XMAS-encrypted list of numbers?

Solution

You can get a contiguous sum in an array by converting that array to a cumulative sum. If an array is [1, 2, 3, 4, 5], its cumulative sum array would be [1, 3, 6, 10, 15].

Nwo to get a contiguous sum of [2, 3, 4] from the original array above, so index of [1, 3], you can do cumulativeSum[3] - cumulativeSum[0].

We're trying to find a continguous sum that adds up to X, where X is equal to:

X = cumulativeSum[j] - cumulativeSum[i] = sum(originalArray[i...j])

We can use the technique from Part One to keep a working set workingSet going as we iterate through cumulativeSum.

At some index j in cumulativeSum, if there exists a value equal to cumulativeSum[j] - X in the workingSet, then we know that this equation holds true because:

X = cumulativeSum[j] - cumulativeSum[i]
is equivalent to
X - cumulativeSum[i] = cumulativeSum[j]

In code, this gives us:

function findContiguousSum({ sumTo, xmasData }: SimulationPartB): number[] {
  // we don't need to iterate through the entire xmasData, just until the index
  // where the invalidNumber (or sumTo) is.
  const idx = assert(
    xmasData.findIndex((d) => d === sumTo),
    (idx) => idx > -1
  );
  const cumulativeSum = xmasData
    .slice(0, idx + 1)
    .reduce(
      (cumSum, curr) => {
        cumSum.push(cumSum[cumSum.length - 1] + curr);
        return cumSum;
      },
      [0] // add an artificial 0, that we remove after the reduce.
    )
    .slice(1); // remove the first element, which is 0.

  const workingSet = new Map<number, number>(); // cumSum[i] -> i
  for (let i = 0; i < cumulativeSum.length; i++) {
    if (workingSet.has(cumulativeSum[i] - sumTo)) {
      return xmasData.slice(
        workingSet.get(cumulativeSum[i] - sumTo)! + 1,
        i + 1
      );
    }
    workingSet.set(cumulativeSum[i], i);
  }
  throw new Error('No contiguous sum found.');
}