Advent of Code 2020 Day 9 - Solution + Tutorial (TypeScript)

published
All TypeScript Solutions for Advent of Code 2020

I'll try to update asap. Please bear in a mind that I'll probably lag one or multiple days behind.


Prerequisites

I assume you've put your puzzle input into an array called lines where each array item is a line of the input text file. It's up to you to either parse the text file or create an array by hand.

const lines = [
  "10",
  "33",
  "20",
  "42",
  "34",];

Solution

Puzzle

Just to make sure, you know what I'm talking about, take a look at today's puzzle:

Day 9: Encoding Error

Part 1

Let's start. I hope you've read the puzzle description. In short, we are given a list of numbers and have to find an invalid number. We recognize this number by a special property. It is impossible to form this number with 2 from the previous 25 numbers.

To make it easier for us in the long run, let's first convert our puzzle input into something more usable. Usually, it's a good idea to start with this.

Our input looks like this:

"10",
"33",
"20",

It's a list of numbers. To make working with them easier, let's use the correct data type.

const numbers = lines.map((line) => Number(line));

Good, now we (really) have a list of numbers. Now, what should we do? According to the puzzle description, a number's previous 25 numbers form the preamble. This preamble should be used to determine if the number is valid or not. Also, the first 25 numbers of our list do not count - they are used as preamble but should not be considered for our search.

Thus, let's go through all numbers, starting with the 26th:

// Use a variable for preamble size. This way, we don't use a "magic number".
const PREAMBLE_SIZE = 25;

for (let i = PREAMBLE_SIZE; i < numbers.length; i++) {
  const number = numbers[i];
  
  // TODO: Somehow determine whether `number` is valid.
  const numberIsValid =if (!numberIsValid) {
    return number;
  }
}

Wow, with this implementation we are almost done. We are iterating through all numbers and as soon as we found the invalid number, we can return it. In this case, numberIsValid is a boolean value. However, we still need to implement a bit of code. How to determine if the number is valid?

Well, we should look at the preamble. Let's define a variable:

const preamble = numbers.slice(i - PREAMBLE_SIZE, i);

Remember, we are still looping through all numbers. i is the index of the current number. To find the preamble for the current number, we have to extract its previous 25 numbers. Therefore, we use Array#slice and our pre-defined PREAMBLE_SIZE.

Now, similar to our solution for Day 1: Report Repair, we'll look for two numbers from our preamble. These should result in our number when added together.

Let's use our preamble array to implement something like this. I'll show you the code and explain it afterwards:

const numberIsValid = preamble.some((first) => {
  return preamble.some((second) => {
    if (first === second) return false;
    return first + second === number;
  });
});

What is happening here? Well, we make use of the Array#some method twice. We go through all numbers in our preamble. Then for each of those numbers (first), we want to find a second number. This second number should NOT be equal to our first number. Also, first and second number should add up to our number. If there is any combination that works, this code results in true. So our number is valid and not the one we are searching for.

Conversely, this means, adding all of our code together, and we've found our invalid number. It's the number where numberIsValid equals false. Here's the full solution:

const numbers = lines.map((line) => Number(line));

const PREAMBLE_SIZE = 25;

for (let i = PREAMBLE_SIZE; i < numbers.length; i++) {
  const number = numbers[i];

  const preamble = numbers.slice(i - PREAMBLE_SIZE, i);

  const numberIsValid = preamble.some((first) => {
    return preamble.some((second) => {
      if (first === second) return false;
      return first + second === number;
    });
  });

  if (!numberIsValid) {
    return number;
  }
}

Part 2

Let's tackle part 2. This time, we should find a contiguous set of at least two numbers. This set's sum should result in our invalid number from part 1. In reverse, that means, we'll need our invalid number from part 1 again.

Let's reuse our code from part 1 to define a function:

function findInvalidNumber(numbers: number[]): number {
  const PREAMBLE_SIZE = 25;

  for (let i = PREAMBLE_SIZE; i < numbers.length; i++) {
    const number = numbers[i];

    const preamble = numbers.slice(i - PREAMBLE_SIZE, i);

    const numberIsValid = preamble.some((first) => {
      return preamble.some((second) => {
        if (first === second) return false;
        return first + second === number;
      });
    });

    if (!numberIsValid) {
      return number;
    }
  }

  // Should never happen.
  throw new Error();
}

Nothing special here. It's our code from part 1 wrapped in a function.

So, with this out of our way, let's prepare our input and find the invalid number.

const numbers = lines.map((line) => Number(line));
const invalidNumber = findInvalidNumber(numbers);

Similar to part 1, we convert our input into numbers. Then, we just use our newly defined function to find the invalid numbers. Basically up to here it's what you've done in part 1.

Now, let's get to the real challenge. What's the contiguous set of numbers that, when added together, result in our invalidNumber.

So how do we proceed? Hm... The set of numbers has a minimum size of 2, and the maximum size is undefined. Basically, it could use ALL numbers. This means, we have to check different sizes.

We can gradually increase the size of our set. First, we'll try it with just 2 numbers. We'll try the first and second, then the second and third, third and fourth, and so on. If none of these small sets can be added so that they result in our invalidNumber, we'll have to increase our set size. We have to try combining three numbers then. First, second, third, then second, third, fourth, and so on.

Okay, given that, we'll need a loop. Let's start with a size of 2 and keep increasing.

for (let size = 2; size < numbers.length; size++) {
  for (let start = 0; start <= numbers.length - size; start++) {
    const end = start + size;

    const window = numbers.slice(start, end);

    // TODO: Check the sum.
  }
}

What's this? A nested loop? Well, yes. We'll start with a size of 2. Then, we'll try to slice a window out of our numbers. We start at the first number and end in such a way, that our window has our given size. This window is moved with each iteration, so that we can check first and second, second and third, and so on.

After moving this window and trying every possible combination for a size of 2, we'll start increasing the window size. In the end, we should find the set of numbers we are searching for. However, we are still missing something. We have to check, whether this window is the set of contiguous numbers we are looking for.

Therefore, let's sum the numbers of the current window:

const sum = window.reduce(
  (previousValue, currentValue) => previousValue + currentValue
);

Now we know what the sum of the numbers in our current window is. So we have to check whether this sum equals our invalidNumber.

if (sum === invalidNumber) {
  // TODO: Something is missing here...
}

There's something missing. Well, according to the puzzle description, we should get the smallest and largest number from the numbers that result in our invalidNumber. Our numbers in the window aren't sorted, so let's sort them and then just get the first and last item.

const result = window.sort((a, b) => a - b);

return result.shift()! + result.pop()!;

With this code, we first sort our numbers in ascending order. Then, Array#shift and Array#pop give us the first and last number. Note the !, it's telling TypeScript, that these aren't undefined. We KNOW, that the result has a first and last item. However, TypeScript does not know this, so we'll help it a little.

Great! Combine everything, and we have our solution for today's puzzle:

const numbers = lines.map((line) => Number(line));
const invalidNumber = findInvalidNumber(numbers);

for (let size = 2; size < numbers.length; size++) {
  for (let start = 0; start <= numbers.length - size; start++) {
    const end = start + size;

    const window = numbers.slice(start, end);
    const sum = window.reduce(
      (previousValue, currentValue) => previousValue + currentValue
    );

    if (sum === invalidNumber) {
      const result = window.sort((a, b) => a - b);
      return result.shift()! + result.pop()!;
    }
  }
}
function findInvalidNumber(numbers: number[]): number {
  const PREAMBLE_SIZE = 25;

  for (let i = PREAMBLE_SIZE; i < numbers.length; i++) {
    const number = numbers[i];

    const preamble = numbers.slice(i - PREAMBLE_SIZE, i);

    const numberIsValid = preamble.some((first) => {
      return preamble.some((second) => {
        if (first === second) return false;
        return first + second === number;
      });
    });

    if (!numberIsValid) {
      return number;
    }
  }

  // Should never happen.
  throw new Error();
}

Conclusion

After all those puzzles, you should notice, that it's always a good idea to convert the input into a more usable format. Also, often you can return early if you've already found the answer to this puzzle. The solutions I present you here, sometimes aren't very efficient. However, for solving this puzzle this usually does not matter. If you want a harder challenge, you can always try to find a more efficient solution.

Thanks a lot for reading this post. Please consider sharing it with your friends and colleagues. See you tomorrow!


If you like my content and you want to see more, please follow me on Twitter!
Questions, feedback or just wanna chat? Come and join my Discord!

You May Also Be Interested in the Following Posts

All TypeScript Solutions for Advent of Code 2020

I'll try to update asap. Please bear in a mind that I'll probably lag one or multiple days behind.