Advent of Code 2020 - Day 13

This is a running series of posts on the Advent of Code 2020. The introductory post has the details, including the accompanying GitHub repo, in case you reached this directly.

In this puzzle, once you remove the decoration about buses, everything consists on cycles of given periods, and it screams modular arithmetic. The input is quite simple, a list of cycle periods with some xs; these just serve to set up the positions of the cycles, which will be used in the second part. A quick analysis of the cycle periods shows that all are prime numbers, which simplifies operations (the least common multiple of a group of prime numbers is their product).

Part 1

The question is, after translation, to find which cycle is the first to recur on or after a given time, and how long it will take.

We can easily calculate the time since the last recurrence of each period at a given time as time mod period. Then, the period less that is the remaining time until the next recurrence (unless the last recurrence was exactly at the given time, in which case we keep the zero).

We define a function to calculate this value for each period, apply it and keep the minimum.

Part 2

This one is a little tougher. We need to find the earliest time t so that each period recurs at t + p, where p is the position of the period in the period list (this is what the xs in the input are setting up).

What we will do here is construct a global cycle step by step. At each step we will add a new period.

The first step is easy: we can arbitrarily take -delay as the start of the cycle (where delay is the position of the first period), so that the initial recurrence at time zero fulfills the condition. The global cycle period is just the first period, so that the delay is kept. This is not explicit in the code as the first period is at position zero, so we can just keep the position.

To add the next period, we need to update the start of the cycle so that it the new delay matches. As long as we advance in increments of the global cycle the previous conditions hold. So we just do that, add one cycle at a time to the start time until the delay matches, that is (-delay = start) (mod cycle), which is expressed in a different way in lines 31 and 32 in the code. Then we update the global cycle by multiplying it by the new period that has been added (the advantage of all periods being prime numbers). This ensures that in the next iterations the conditions hold for all periods up to this one (the global cycle always is a multiple of each period included in it, so the delay is kept).

Rinse and repeat until all periods are included, with their corresponding delays.