Advent of Code 2020 Day 15 - 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 a variable called input.

const input = "1,0,15,2,10,13";

Solution

Preface

Starting with Day 10, I'll just publish my solution for both parts without explaining every single step. Unfortunately, I can't continue providing full step-by-step tutorials for each day. The concepts used get more difficult day by day. So, I've concluded that it's better if I wrote separate blog posts about these concepts later.

Also, it's holiday season. This makes it much more difficult creating well-thought-out tutorials. However, I'll try to annotate my code examples a little. This way, you might understand what I've done.

I will now move on to sharing useful tips for web developers regularly. These should help you become a better developer. Also, the shared tips should help with solving problems like those we encounter in Advent of Code. Here's my first post: 14 Awesome JavaScript Array Tips You Should Know About

Puzzle

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

Day 15: Rambunctious Recitation

Part 1

Today, the elves want to play a strange memory game with us. Each turn, a number is spoken. Depending on the previous number spoken, the next number spoken is different. We have to find the 2020th number spoken.

Let's start by parsing our input and create an array of numbers from it. Also, we should keep track of which numbers were spoken already. This is done with the spokenNumbers variable in the code example below. Our starting numbers are the first numbers spoken. So, we can add them to our spoken numbers array.

Now, remember, each turn a number is spoken. We'll have to take turns until we've reached the 2020th turn. Here, a while-loop is used. Each iteration increases the turn value, because a new turn has started. Then, we have to find out, whether the previous number has been spoken already. We determine this by looking at the spokenNumbers array. Depending on the outcome, we either speak 0 or the age (like defined in the puzzle description) next. After that, the next turn starts.

We keep doing this, until we've finished the 2020th turn. Then, we've got our solution:

// Convert our input string into an array of numbers.
const startingNumbers = input
  .split(",")
  .map((startingNumber) => parseInt(startingNumber));

// Create a `spokenNumbers` array and add our starting numbers.
const spokenNumbers: number[] = [...startingNumbers];

// Each turn a number is spoken. Thus, our current turn is the length of the array.
let turn = spokenNumbers.length;

// We should find the 2020th number spoken. Therefore, we use this `while`-loop.
while (turn < 2020) {
  // Start of a new turn.
  turn++;

  // Use `turn` to access the `lastNumberSpoken`.
  const lastNumberSpoken = spokenNumbers[turn - 2];

  // When was the last time this number was spoken?
  const lastIndex = spokenNumbers.lastIndexOf(lastNumberSpoken);

  // When was the second-to-last time this number was spoken?
  const secondToLastIndex = spokenNumbers.lastIndexOf(
    lastNumberSpoken,
    lastIndex - 1
  );

  // Check if there was no second-to-last time. 
  if (secondToLastIndex === -1) {
    // Speak `0`.
    spokenNumbers.push(0);
    continue;
  }

  // Speak `age`. It's calculated by using the last and second-to-last turn.
  const lastTurn = lastIndex + 1;
  const secondToLastTurn = secondToLastIndex + 1;
  const age = lastTurn - secondToLastTurn;
  spokenNumbers.push(age);
}

// Return the last number spoken.
return spokenNumbers[spokenNumbers.length - 1];

Part 2

Funny. Part 2 is basically the exact same task like in part 1. Except with a minor (or major...) difference. Instead of finding the 2020th number spoken, we should find the 30,000,000th number spoken. Easy.

We can re-use our implementation from part 1 and simply change 2020 to 30000000. Let's run it:

...

...

...

Hm, we have to do something else. It takes waaay to long. So this time, we have to come up with a better, more efficient solution.

Instead of adding each spoken number to an array that keeps getting bigger, let's use a Map. This map keeps track of each number, and the last time it was spoken. Then, we could determine whether the number has never been spoken before or what its age is.

The implementation is pretty similar to part 1 with a few adjustments to use the map. We could have used this implementation for part 1 also. Take a look at the comments in the code example.

Here's the full solution:

// Convert our input string into an array of numbers.
const startingNumbers = input
  .split(",")
  .map((startingNumber) => parseInt(startingNumber));

// Create a `spokenNumbers` map and add our starting numbers.
const spokenNumbers = new Map<number, number>();
startingNumbers.forEach((startingNumber, i) => {
  spokenNumbers.set(startingNumber, i + 1);
});

// Each turn a number is spoken. Thus, our current turn is the size of the map.
let turn = spokenNumbers.size;

// We have to keep track of the last number spoken. We can extract it from our map this time.
let lastNumberSpoken = [...spokenNumbers.keys()].pop()!;

// We should find the 30000000th number spoken. Therefore, we use this `while`-loop.
while (turn < 30000000) {
  // Start of a new turn.
  turn++;

  // Find the last time the last number was spoken.
  const lastTurn = turn - 1;

  // Find the second-to-last time the last number was spoken.
  const secondToLastTurn = spokenNumbers.get(lastNumberSpoken);

  // Update `spokenNumbers` here.
  // Thus, if we ever encounter the number again, the value refers to the `secondToLast` time.
  spokenNumbers.set(lastNumberSpoken, lastTurn);

  // Check if the last number has been spoken before.
  if (!secondToLastTurn) {
    // Update our last number spoken.
    // Don't update our `spokenNumbers` yet.
    lastNumberSpoken = 0;
    continue;
  }

  // Update our last number spoken.
  // Don't update our `spokenNumbers` yet.
  const age = lastTurn - secondToLastTurn;
  lastNumberSpoken = age;
}

return lastNumberSpoken;

Conclusion

Today was interesting. Part 1 and part 2 were basically the same task. However, as you may have noticed, it was important that the implementation is efficient. Our solution from part 1 isn't fast enough to solve part 2 in a reasonable time. Therefore, we've optimized the code. Still, it's okay how we've solved part 1. I think you should optimize as soon as it's necessary. Not earlier. However, for part 2 it was necessary.

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!
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.