Advent of Code 2020: Day 13

, 9 min read
advent of code 2020

Part 1

Your ferry can make it safely to a nearby port, but it won’t get much further. When you call to book another ship, you discover that no ships embark from that port to your vacation island. You’ll need to get from the port to the nearest airport.

Fortunately, a shuttle bus service is available to bring you from the sea port to the airport! Each bus has an ID number that also indicates how often the bus leaves for the airport.

The time this loop takes a particular bus is also its ID number: the bus with ID 5 departs from the sea port at timestamps 0, 5, 10, 15, and so on. The bus with ID 11 departs at 0, 11, 22, 33, and so on. If you are there when the bus departs, you can ride that bus to the airport!

Your notes (your puzzle input) consist of two lines. The first line is your estimate of the earliest timestamp you could depart on a bus. The second line lists the bus IDs that are in service according to the shuttle company; entries that show x must be out of service, so you decide to ignore them.

To save time once you arrive, your goal is to figure out the earliest bus you can take to the airport. (There will be exactly one such bus.)

For example, suppose you have the following notes:

1
2
    939
    7,13,x,x,59,x,31,19

What is the ID of the earliest bus you can take to the airport multiplied by the number of minutes you’ll need to wait for that bus?

You can read the full text here. The first part of today’s puzzle is fairly straightforward.

Our first step is to read in both lines of the input. The first line contains the earliest time we can leave the port. The second line includes a series of numbers which are the IDs of each bus. The ID tells us how often that bus runs, starting at 0. E.g. bus 7 runs at 0, 7, 14, 21, … past an initial time of 0. The x’s tell us that a bus is out of service and we should ignore it.

We start using the usual,

1
2
3
4
5
std::fstream myfile("input", std::ios_base::in);
std::string line1, line2;
std::getline(myfile, line1);
std::getline(myfile, line2);
myfile.close();

Now we have the input in our program in string representation. Line 1 is easy, we just turn it into an integer. Line 2 requires us to loop through looking for numbers and “x"s. For this we can use a regex pattern,

1
2
3
4
5
const std::regex reg("([0-9x]+)+");
std::sregex_token_iterator it = {line2.begin(), line2.end(), reg, 1};
while (it != std::sregex_token_iterator()) {
    std::cout << *it << std::endl;
}

This code would output 7, 13, x etc., for the example input. Great! But how do we solve part 1?

Well for part 1 we must find the bus which leaves the soonest after our input time, t0. For this, we will use remainders. For example, if our time was 17 and we considered the bus with ID = 19, then 17%19=2, so we would have to wait 2 minutes for this bus.

What about the bus with an ID=8, well 17%8=1, but (17/8) * 2 = 2 * 8 = 16. The remainder is 1 minute, but this bus leaves 1 minute too early. Thus, if the bus leaves too early the wait time is the remainder subtracted from the bus ID, which in this case is 7 minutes. We can apply this process to all of our bus IDs,

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
int n = mytime / val;
int rem = mytime % val;
// If the value is less than the time, then we must do val-rem
// to find out how long after the bus leaves
if (n*val < mytime)
    rem = val - rem;
// Is this the bus with the shortest wait?
if (rem < best_bus.second){
    best_bus.first = val;
    best_bus.second = rem;
}

Great, that is all we needed to do to earn our first star, ⭐.

The full code can be found on github

Part 2

The shuttle company is running a contest: one gold coin for anyone that can find the earliest timestamp such that the first bus ID departs at that time and each subsequent listed bus ID departs at that subsequent minute. (The first line in your input is no longer relevant.)

For example, suppose you have the same list of bus IDs as above:

1
2
    939
    7,13,x,x,59,x,31,19

An x in the schedule means there are no constraints on what bus IDs must depart at that time.

This means you are looking for the earliest timestamp (called t) such that:

1
2
3
4
5
6
7
8
9
    Bus ID 7 departs at timestamp t.
    Bus ID 13 departs one minute after timestamp t.
    There are no requirements or restrictions on
        departures at two or three minutes after timestamp t.
    Bus ID 59 departs four minutes after timestamp t.
    There are no requirements or restrictions on departures
        at five minutes after timestamp t.
    Bus ID 31 departs six minutes after timestamp t.
    Bus ID 19 departs seven minutes after timestamp t.

The only bus departures that matter are the listed bus IDs at their specific offsets from t. Those bus IDs can depart at other times, and other bus IDs can depart at those times. For example, in the list above, because bus ID 19 must depart seven minutes after the timestamp at which bus ID 7 departs, bus ID 7 will always also be departing with bus ID 19 at seven minutes after timestamp t.

What is the earliest timestamp such that all of the listed bus IDs depart at offsets matching their positions in the list?

You can read the full text here. I would strongly encourage you to click on the link and really digest what the question is asking because this is a hard question.

I’m not embarrassed to say this question took me several hours to solve. After sitting at my laptop for an hour, making little progress, I decided to go for a run. Then 2 hours later, I returned and spent 5 minutes implementing my solution and voila, solved!

What do we do? We start by sorting the bus ID’s and then reversing them such that we start with the largest bus ID first.

1
2
std::sort(bus_ids.begin(), bus_ids.end());
std::reverse(bus_ids.begin(), bus_ids.end());

This can actually be done in a single line, but whatever. We then set the solution guess to be

1
2
3
// Pick a starting value which we know works
long int t = bus_ids[0].first - bus_ids[0].second;
long int step = bus_ids[0].first;

We know that the first bus ID, bus_ids[0].first + the time offset, bus_ids[0].second, is a solution. Namely, we have a constructed a time, t such that (t+bus_ids[0].second)/bus_ids[0].first has a zero remainder. With this initial solution for the first bus, we can set the time step, step, to be the ID of the first bus. Then as we have a working solution for the first bus, incrementing the time by the ID of the first bus will always yield a working solution.

We then move onto the second bus. If the current time doesn’t work for the second bus, we keep incrementing the time with the step, which is the ID of bus 1. When we find a time which works for bus 2, we already know it is a solution for bus 1 due to our choice of step.

Now comes the clever part. We then set the new step to be the lowest common multiple of the current step and the second bus ID. Now we know that any future times which we reach using this step will also be solutions for the first two buses. We keep iterating through every bus in our input. The whole code looks like this,

1
2
3
4
5
6
for (auto v : bus_ids){
    while ((t + v.second) % v.first != 0)
        t += step;

    step = std::lcm(step, v.first);
}

To summarise, we start with a solution which works for bus 1, and we set our step to be the ID of bus 1 so that every future time we try will be valid for bus 1. Then we find a time which works for bus 2 AND update the step to be the lowest common multiple of bus 1 and bus 2. Any future time reached with this step is guaranteed to be a solution for bus 1 and bus 2. We keep applying this same process for all the buses. As we start with the bus with the largest ID, we begin with the largest possible initial step which reduces the number of iterations required to reach the full solution.

There we go ⭐⭐!

The full code can be found on github

Reflections

I’m not sure if this is the optimal solution. Still, it runs instantly on my laptop, so I’m calling it an optimal solution!

Both parts of today’s puzzle have time and space complexities, O(N) where N is the number of in-service buses in the input.

I suspect there is a slightly more efficient solution to part 2, which will be on the advent of code subreddit. However, I’m not quite ready to give in and look it up yet. I’m pretty happy I was able to come up with a near-instant solution today, so I’m going to take the rest of the day off.

. . . .

I have no affiliation with AoC. I’m just a fan of the programming puzzles. If you enjoy them too, please feel free to join in and support the creators

Back to my advent calendar

Comments

Back to all posts