ETOOBUSY 🚀 minimal blogging for the impatient
AoC 2016/15 - Chinese Reminder Theorem - again!
TL;DR
The Advent of Code puzzle 15 from 2016 has more Chinese Remainder Theorem!
As you might have noticed, I’ve been taking a look at the 2016 edition of the puzzles in Advent of Code.
No, this will not be another series!
It so happens that puzzle 15 has a long and involved description about capsules, discs, alignments, exact timings… I had to read it twice and put my brain in full imaginative mode.
Anyway, as I read through it, I started suspecting that it had to do with the Chinese Remainder Theorem. Which, indeed, it does.
First thought was: again?!? Then I had that Back to the Future moment when I realized that this puzzle came before the ones I discussed last December 🙄
Second thought was: I don’t want to understand this problem, I want to COOOODE!.
He who its first…
… hits twice, right?
So I went ahead, took the relevant functions from cglib’s Numbers.pm, put some parsing, a bit of this, a bit of that… and ended up with the following:
#!/usr/bin/env perl
use 5.024;
use warnings;
use English qw< -no_match_vars >;
use autodie;
use experimental qw< postderef signatures >;
no warnings qw< experimental::postderef experimental::signatures >;
use File::Basename qw< basename >;
use Data::Dumper; $Data::Dumper::Indent = 1;
use Storable 'dclone';
$|++;
my @stuff;
my $filename = shift || basename(__FILE__) =~ s{\.pl\z}{.tmp}rmxs;
open my $fh, '<', $filename;
while (<$fh>) {
my ($delay, $n, $position) = m{
\A Disc \s+ \#(\d+) \s+
has \s+ (\d+) \s+ positions .*?
at \s+ position \s+ (\d+)
}mxs or die $_;
push @stuff, $n, ($delay + $position) % $n;
}
close $fh;
say((chinese_remainder_theorem(@stuff))[1]);
# chinese_remainder_theorem and egcd below... nothing new
I have to admit that I was a bit unsure about the ($delay +
$position) % $n - it was somehow a shot in the dark.
Anyway, I run it over the example input and presto! - it worked! Right off the bat!
$ cat 15.tmp
Disc #1 has 5 positions; at time=0, it is at position 4.
Disc #2 has 2 positions; at time=0, it is at position 1.
$ perl 15-1.pl 15.tmp
5
OK, on with my puzzle input then:
$ cat 15.input
Disc #1 has 13 positions; at time=0, it is at position 1.
Disc #2 has 19 positions; at time=0, it is at position 10.
Disc #3 has 3 positions; at time=0, it is at position 2.
Disc #4 has 7 positions; at time=0, it is at position 1.
Disc #5 has 5 positions; at time=0, it is at position 3.
Disc #6 has 17 positions; at time=0, it is at position 5.
$ perl 15-1.pl 15.input
64118
Only that… NO, it does not work!!!
I hit first… but I hit wrong!
Back to the paper
This must be my humbling year, because I’m reminded so many times of how many ways I have to fail!
Well, I meant learn 👨🎓
Let’s see… if we start at time $T$, the first disk is reached after a delay of $1$ at time $T + 1$, and if its starting position (at $t = 0$) is $P_{1, 0}$ then its position at $T + 1$ will be $T + 1 + p_1 \pmod {n_1}$. We have similar relations for the other discs:
\[P_{1, T + 1} \equiv T + 1 + P_{1, 0} \pmod {n_1} \\ P_{2, T + 2} \equiv T + 2 + P_{2, 0} \pmod {n_2} \\ ... \\ P_{i, T + i} \equiv T + i + P_{i, 0} \pmod {n_i}\]If we really need that capsule, each of the left-hand sides MUST be $0$, which brings us to:
\[T \equiv -1 - P_{1, 0} \pmod {n_1} \\ T \equiv -2 - P_{2, 0} \pmod {n_2} \\ ... \\ T \equiv -i - P_{i, 0} \pmod {n_i}\]This can also be rewritten as:
\[r_1 = T \pmod {n_1} = n_1 - (1 + P_{1, 0} \pmod {n_1}) \\ r_2 = T \pmod {n_2} = n_2 - (2 + P_{2, 0} \pmod {n_2}) \\ ... \\ r_i = T \pmod {n_i} = n_i - (i + P_{i, 0} \pmod {n_i})\]I knew it!
It’s also funny that it worked for the example input: simply put, $1 \equiv -1 \pmod 2$, so the sign flip didn’t matter!
So the right code is actually this… a small change for a program, but a big step ahead for a puzzle solver!
#!/usr/bin/env perl
use 5.024;
use warnings;
use English qw< -no_match_vars >;
use autodie;
use experimental qw< postderef signatures >;
no warnings qw< experimental::postderef experimental::signatures >;
use File::Basename qw< basename >;
use Data::Dumper; $Data::Dumper::Indent = 1;
use Storable 'dclone';
$|++;
my @stuff;
my $filename = shift || basename(__FILE__) =~ s{\.pl\z}{.tmp}rmxs;
open my $fh, '<', $filename;
while (<$fh>) {
my ($delay, $n, $position) = m{
\A Disc \s+ \#(\d+) \s+
has \s+ (\d+) \s+ positions .*?
at \s+ position \s+ (\d+)
}mxs or die $_;
push @stuff, $n, $n - ($delay + $position) % $n;
}
close $fh;
say((chinese_remainder_theorem(@stuff))[1]);
# ...
Let’s run it…
$ perl 15.pl 15.input
376777
Yay, this is correct now!
A final thought
I work in the telecommunications industry and most of my… coding occasions come in relation to relatively small integrations, so I definitely have a biased view.
This said… I wonder if the Chineses discovered this theorem just for the fun of puzzle builders and solvers in the 21st century!