Advent of Code: Day 13

This is going to be about software. Mostly.

There’s this thing – the advent of code. It’s a sequence of 25 puzzles to be solved with code. Some people do it in Python, some people Java, someone with aggressively self-flagellating tendencies is doing it in SQL and there’s a rumour of someone who’s done it purely with formulas in Excel. If that’s true then that person should be found and immediately restrained, for the good of all.

Anyway. This year I’ve really enjoyed the puzzles, until we got to number 13. Unlucky for some. Unlucky for me, since I get hyperfixated on things, and this one I could not let go of. The conceit is simple: imagine a bus timetable for an airport shuttle bus. Each bus number is also the period of its route – the number 5 bus departed at midnight and will be back at 5, 10, 15…minutes past the hour. The number 17 bus will be back at 17, 34, 51…minutes later.

Here’s the challenge. Given a list of buses and offsets, where each offset is the number of minutes from the first bus, what’s the earliest time in minutes when all the buses line up? For example, imagine we’ve got five buses (7, 13, 59, 31, and 19) and their offsets are, respectively, (0, 1, 4, 6, and 7). We line all the bus timetables up – assuming we have a lot of paper – and add a dot for each minute. When the bus arrives/departs, we add a D. We do this for a while, until:

time     bus 7   bus 13  bus 59  bus 31  bus 19
1068773    .       .       .       .       .
1068774    D       .       .       .       .
1068775    .       .       .       .       .
1068776    .       .       .       .       .
1068777    .       .       .       .       .
1068778    .       .       .       .       .
1068779    .       .       .       .       .
1068780    .       .       .       .       .
1068781    D       .       .       .       .
1068782    .       D       .       .       .
1068783    .       .       .       .       .
1068784    .       .       .       .       .
1068785    .       .       D       .       .
1068786    .       .       .       .       .
1068787    .       .       .       D       .
1068788    D       .       .       .       D
1068789    .       .       .       .       .
1068790    .       .       .       .       .
1068791    .       .       .       .       .
1068792    .       .       .       .       .
1068793    .       .       .       .       .
1068794    .       .       .       .       .
1068795    D       D       .       .       .
1068796    .       .       .       .       .
1068797    .       .       .       .       .

Hurrah! We found the answer. It was 1068781 minutes past midnight. Unfortunately, even though we dotted each row in only a second, it’s taken us almost two weeks to figure out the answer. Is there an easier way?

There is, of course. It would be a very modernist approach to tell you about this problem without describing how to solve it easily. My partner, who’s a genuine STEM person and genius, figured it out within a couple of minutes of me describing it to her. To her eternal credit, despite me not listening properly while she explained it and instead spending two days coming to the same solution, she has not once smugly told me that she told me so.

I mean she’s clear that she told me. She’s just not smug about it, which demonstrates that she’s a much better person than I am.

I’m going to pause here. Perhaps you already know the answer. Perhaps you’d like to work it out for yourself. Either way, I’m going to break shortly and tell you my favourite apocryphal tale about Isaac Newton.

Isaac Newton was an odd man, by all accounts, but he was befriended by a cat and seemed to enjoy her presence. She and he had one strong difference of opinion: he would gladly have stayed in his room for all eternity, working on new systems of mathematics and getting high on mercury, but she wanted to explore the world. What to do? The answer was simple. He cut a hole in his study door at cat height, tacked thick velvet across it, never thought to patent his new Cloth-Door-For-Easy-Entry-And-Exit-Of-Felines, and forgot all about it.

The cat had three kittens. It’s how we get new cats. For many people this might have been a problem, but Isaac had solved the “cat in the room” problem before. This, therefore, was merely a question of multiplication, which was why the next day his housekeeper watched with bemusement while he cut another three holes in his door.

In programming, if we cannot solve a large problem we generally try to reduce it to a simpler problem – preferably one that’s been solved before. In this way we get all of the credit for almost none of the work. In the problem above, let’s try to solve just the first case: bus 7 (offset 0) and bus 13 (offset 1).

What is the first value that satisfies the test condition – a time at which the number 7 bus departs and, one minute later, the number 13 departs?

If you’d like to work it out by hand, please do. I wrote something for my computer to do it:

class Bus:
    def __init__(self, interval: int, offset: int):
        self.interval = interval
        self.offset = offset

    def __repr__(self):
        return f"Bus {self.interval}"

def paired_bus_intervals(self, base_bus: Bus, pair_bus: Bus) -> Bus:
        time = base_bus.offset
        while not (time + pair_bus.offset) % pair_bus.interval == 0:
            time += base_bus.interval
        return Bus(pair_bus.interval * base_bus.interval, time)

A bit of explanation – I’ve made up an object called a Bus, which has an interval – that repeating period – and an offset, which I touched on above. I’ve defined it because it’s a bit tidier.

The function below that is the important one: it takes two Buses and turns them into one. We do a little trickery, but the method is the same as when we were doing it on paper. We look at the leftmost column and jump by the interval of that Bus every time. Once we’ve jumped, we add the offset of the other Bus – the offset – and try to divide by that Bus‘s interval. We use the % sign because that only returns the remainder. If there’s no remainder, then we know for a fact that the number is exactly divisible – and that means we’ve found our solution!

If not, we move to the next jump, and try again.

Above, we find that at time=77 the Buses align perfectly. The next time they align will have to be a multiple of both 7 and 13, which means we can predict that the next perfect alignment will be 77 + (7 * 13) = 168. And that’s right – 168 / 7 is 24, and 169 is 13 squared.

Awesome. So now we know how to find the interval and offset for two buses. Now here’s the trick: here’s Isaac, cutting a hole in the door.

Every pair of Buses can be treated as as one, with a unique interval and offset. The offset is the earliest time we find that works for both; the interval is each of their intervals multiplied together. If we can reduce two Buses to one Bus, then we can solve the problem of three Buses. Because once we’ve solved two of them to make one, we’ll have two Buses again. And even if we had four, we could just solve for two of them – twice – to reduce the problem down to two Buses again!

In Python we implement this with a function called reduce. Because it reduces things. I implemented it like this:

answer = reduce(paired_bus_intervals, really_long_list_of_Buses)

And this will churn away, converting two of the problem inputs into one output, which it will then use as one of its next two inputs, which it will turn into…

Three days of thinking for 6 lines of code. What a splendid way to spend one’s time.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s