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

- [ 1 ]
- [ 2 ]
- [ 3 ]
- [ 4 ]
- [ 5 ]
- [ 6 ]
- [ 7 ]
- [ 8 ]
- [ 9 ]
- [ 10 ]
- [ 11 ]
- [ 12 ]
- [ 13 ]
- [ 14 ]
- [ 15 ]
- [ 16 ]
- [ 17 ]
- [ 18 ]

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 = [
"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:

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