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->";

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:

$r = (b - i) \pmod b$

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:

$k \cdot b = s + i \\$

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

$s = k \cdot b - i = (k - 1) \cdot b + (b - i) = k' \cdot b + (b - i)$

which tells us that:

$s \equiv (b - 1) \pmod b$

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!

Comments? Octodon, , GitHub, Reddit, or drop me a line!