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!