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!


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