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

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 = [
  "1000303",
  "41,x,x,x,x,…
];

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 13: Shuttle Search

Part 1

Today we want to find the earliest bus we can take to the airport. Therefore, we have to extract the earliestDepartureAt and busIds from our input. Entries that show "x" are out of service, so we can just ignore them.

Now, to find the earliest bus, we can look at the bus schedule. Each bus departs in a fixed interval. The interval is specified by its ID. So a bus with ID "7" departs at 0, 7, 14, 21 and so on. We can see here, that the numbers (except 0) are divisible by "7" without a remainder.

This means, we can find the earliest departure time for each bus. Starting from our earliest departure time, we keep increasing the departureTime. As soon as the departureTime is divisible by the current busId without a remainder, we've found the earliest time this bus departs.

After doing this for all busses, we simply find the bus with the earliest departure time (minimum) and we can solve the puzzle! Here's the full solution:

const earliestDepartureAt = parseInt(lines[0]);

// Extract `busIds`. We can ignore entries with `"x"`. 
const busIds = lines[1]
  .split(",")
  .filter((busId) => busId !== "x")
  .map((busId) => parseInt(busId));

const departureTimes = busIds.map((busId) => {
  let departureTime = earliestDepartureAt;

  // If this modulo operation does not return 0, the bus does not depart at the current time.
  // Thus, we increase the time and retry.
  while (departureTime % busId) {
    departureTime++;
  }

  return departureTime;
});

// We've determined the departure times for all busses.
// Now, we can retrieve the earliest departure and bus.
const departureAt = Math.min(...departureTimes);
const busId = busIds[departureTimes.indexOf(departureAt)];

return busId * (departureAt - earliestDepartureAt);

Part 2

Part 2 is a bit more complicated. We should find the earliest timestamp, where each bus in our puzzle input departs one minute after the previous bus. This time, x means any bus, so we can simply assume their departure interval equals 1 minute. This makes it easier for us.

How do we find a solution here? Well, we can make use of a step variable. This variable holds a number that is used for incrementing the timestamp variable. If this first bus in our input has the ID 7, we'll start with a step size of 7.

Why? Let me try to explain:

We know 7 is our first bus, and we are looking for the earliest timestamp where the busses from our input depart in the exact same order with a one-minute difference each. This means, that we should look only at timestamps, where our bus with the ID 7 (or whatever your first bus is) departs. If 7 does not depart at a specific timestamp, it's unnecessary to even look at it. It's impossible to match our puzzle input then.

Ok. Now we are looking at each bus. We increment our timestamp by the value of step until we've found a timestamp where the current bus departs. Now the current bus and the previous bus are in the correct schedule. To keep those two aligned, we have to adjust our step size. Therefore, we'll calculate the least common multiple of our current step value and the current busId. This way, our step always takes all previous busses into consideration.

If we've done this for all busses, our timestamp matches the earliest timestamp where all busses depart in the given order. We've solved the puzzle. Here's the full solution:

// Extract `busIds`. Entries with `"x"` are used as if they had an ID of 1.
const busIds = lines[1].split(",").map((busId) => {
  return busId !== "x" ? parseInt(busId) : 1;
});

let step = busIds[0];
let timestamp = 0;

// Modify `step` in a way, that it takes each bus into consideration.
// Therefore, we can use the least common multiple.
busIds.forEach((busId, i) => {
  if (busId === 1 || busId === step) return;

  while ((timestamp + i) % busId !== 0) {
    timestamp += step;
  }

  step = lcm(step, busId);
});

return timestamp;

// Least common multiple
function lcm(a: number, b: number): number {
  if ([a, b].includes(0)) return 0;
  return Math.abs((a * b) / gcd(a, b));
}

// Greatest common divisor
function gcd(a: number, b: number): number {
  if (!b) return Math.abs(a);
  return gcd(b, a % b);
}

Conclusion

While part 1 was pretty easy today, part 2 was probably a lot harder for you. There are many possible solutions for part 2. However, you have to find a time- and space-efficient approach. That's not to say, that my implementation is very efficient. Nevertheless, it might be possible that you've found a valid solution that would take a long time to finish.

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