TL;DR

Puzzle 13 in this year’s Advent of Code was interesting.

First of all, thanks to @riffraff for indirectly reminding me about Advent of Code:

Am I the only one feeling the #AdventOfCode puzzles this year have been simpler than in the past, until day 9 at least?

I was interested, and I even discovered that I already participated into Advent of Code five years ago. The blessing of forgetting!

When I arrived to the second part of puzzle 13, the three words Chinese Remainder Theorem formed as a reflex in my memory. The blessing of remembering.

Well, don’t get me wrong: I only know more or less what the theorem is about, and in particular that it’s useful to address systems of congruences. That’s enough, though, because I can go and read it time and again when it pops up in my mind. The blessing of Wikipedia.

So here’s my solution in all its cryptic glory, without the I/O part:

#!/usr/bin/env perl
use 5.024;
use warnings;
use experimental qw< postderef signatures >;
no warnings qw< experimental::postderef experimental::signatures >;
use List::Util 'reduce';
use bigint;

my @buses = split m{[,\s]+}mxs, '7,13,x,x,59,x,31,19';
my $overall = reduce {crt($a->@*, $b->@*)}
   map  { [$buses[$_], ($buses[$_] - $_) % $buses[$_]] }
   grep { $buses[$_] ne 'x' } 0 .. $#buses;
say "result for part2: $overall->[1]";

sub crt ($n1, $r1, $n2, $r2) {
   my ($gcd, $x, $y) = egcd($n1, $n2);
   die "not coprime! <$n1> <$n2>" if $gcd != 1;
   my $N = $n1 * $n2;
   my $r = ($r2 * $x * $n1 + $r1 * $y * $n2) % $N;
   return [$N, $r];
}

sub egcd {    # https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
   my ($X, $x, $Y, $y, $A, $B, $q) = (1, 0, 0, 1, @_);
   while ($A) {
      ($A, $B, $q) = ($B % $A, $A, int($B / $A));
      ($x, $X, $y, $Y) = ($X, $x - $q * $X, $Y, $y - $q * $Y);
   }
   return ($B, $x, $y);
} ## end sub egcd

Function egcd comes straight from The extended Euclid’s algorithm.

The function crt implements the Chinese Remainder Theorem to find a solution for a pair of congruences, giving back the combined congruence. It’s really just a translation of the Wikipedia page into code, leveraging the egcd function and making sure that the two input values $n1 and $n2 are coprime.

So… we just have to unpack how we get $overall, that will eventually hold our solution. Let’s put some line numbers:

 1 my $overall = reduce {crt($a->@*, $b->@*)}
 2    map  { [$buses[$_], ($buses[$_] - $_) % $buses[$_]] }
 3    grep { $buses[$_] ne 'x' } 0 .. $#buses;

We start from line 3: we iterate over the index in array @buses, keeping only those related to actual bus numbers (i.e. ignoring those whose bus is set as x).

In line 2 we transform each index into a pair of values: the first is the modulo number - that is the same as the bus number - while the second is the remainder. More on this a few lines down below.

In line 1 I finally get to use a function whose power I only suspect. It iterates over a list, where at each step applies a function that takes in input two values and produces one value. The two values are the first two elents in the list for the first call; afterwards, it’s the result of the previous call and the next element in the list.

As we have to incrementally apply function crt to get a single growing congruence… it hits the nail right in the head.

Now let’s come to line 2 again. As I said, the modulo number is the same as the bus, so there’s nothing much to say here. On the other hand, the remainder of our solution $s$ by the bus number is calculated as:

This can be explained like this: the index $i$ of the bus in the array represents the target time offset of the specific bus with respect to the first one. So, it’s the remainder of the multiple of $b$ immediately following our solution $s$, modulo the solution $s$ itself:

On the other hand, we’re interested into the rest of the division of $s$ by $b$. The relation above can be expressed as:

which tells us that:

i.e. the value that we exposed above and that we put as the second element in our pairs of line 1.

At this point, I hope I managed to intrigue you a bit… happy coding!