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.