# Day 13 (Advent of Code 2020)

This article is part of the Advent of Code 2020 series.

In the Day 13 problem, we're trying to take the bus.

Our input looks like this:

`939 7,13,x,x,59,x,31,19`

The first line indicates the earliest minute we can leave from the bus terminal, and the second line indicates the "identifier" of the buses that are active.

Each bus departs every "bus ID" minutes - bus 7 leaves at minute 0, minute 7, minute 14, minute 21, etc. The question is: which bus can we take first (apparently they either all go to the same destination, or we don't really care where we're going), and how long do we have to wait for it?

The answer to give is computed by multiplying the bus ID with the number of minutes we need to wait.

You know the drill by now... let's make some types!

Rust code

#[derive(Debug)]structProblemStatement{departure_time:usize,buses:Vec<usize>, }#[derive(Debug)]structWaitTime{bus_id:usize,/// in minuteswait:usize, }

Then a quick parser:

Rust code

implProblemStatement{fnparse(input:&str)->Self{letmutlines = input.lines();ProblemStatement{departure_time: lines.next().unwrap().parse().unwrap(),buses: lines.next().unwrap().split(',').filter(|&s| s !="x").map(|x| x.parse().unwrap()).collect(), } } }

Let's check we can actually parse the example input:

Rust code

9397,13,x,x,59,x,31,19

Shell session`$ cargo run --quiet [src/main.rs:31] ProblemStatement::parse(include_str!("input.txt")) = ProblemStatement { departure_time: 939, buses: [ 7, 13, 59, 31, 19, ], }`

From there, we need to figure out how many minutes we need to wait until the
next bus. Well, we've been using the modulo operator (`%`

) a couple times in
this series, it does bring us half the way there. If we reproduce the table
from the example:

So what we really want to do is do `bus_id - (departure_time % bus_id)`

, which would
give us the distance to the *next* departure:

That seems easy to implement!

Yup! We already have a type for it!

Rust code

fnmain(){letstat =ProblemStatement::parse(include_str!("input.txt"));lettimes:Vec<_>= stat.buses.iter().map(|&bus_id|WaitTime{ bus_id,wait: bus_id - stat.departure_time% bus_id, }).collect();dbg!(times);}

Shell session`$ cargo run --quiet [src/main.rs:41] times = [ WaitTime { bus_id: 7, wait: 6, }, WaitTime { bus_id: 13, wait: 10, }, WaitTime { bus_id: 59, wait: 5, }, WaitTime { bus_id: 31, wait: 22, }, WaitTime { bus_id: 19, wait: 11, }, ]`

Now we need to find the bus that leaves at the earliest time following our
earliest departure time, ie. the minimum `WaitTime::wait`

.

Mhhh we could use `Iterator::min`

... but only if we first `map(|wt| wt.wait)`

or
something - and then we'd lose the `bus_id`

!

Yeah that won't do - we'll need a closely related method: `Iterator::min_by_key`

!

Rust code

fnmain(){letstat =ProblemStatement::parse(include_str!("input.txt"));letanswer = stat.buses.iter().map(|&bus_id|WaitTime{ bus_id,wait: bus_id - stat.departure_time% bus_id, }).min_by_key(|wt| wt.wait);matchanswer { Some(wt)=> {dbg!(&wt, wt.bus_id * wt.wait);} None => {panic!("No answer found!");} } }

OooOOoohhh!

Shell session`$ cargo run --quiet [src/main.rs:44] &wt = WaitTime { bus_id: 59, wait: 5, } [src/main.rs:44] wt.bus_id * wt.wait = 295`

Cool! It works with the sample input.. but will it work with the real input?

Only one way to find out!

Shell session`$ cargo run --quiet [src/main.rs:44] &wt = WaitTime { bus_id: 383, wait: 5, } [src/main.rs:44] wt.bus_id * wt.wait = 1915`

Correct!

## Part 2

Oh no, Part 1 was deceptively simple - is Part 2 going to be super confusing?

Why yes it is!

Now we don't care about the first line at all, all we care about is this line:

`7,13,x,x,59,x,31,19`

The `x`

values now matter (surprise!) because the problem takes into account
the position of a bus ID into the list, so we should remember:

- 7 => 0,
- 13 => 1,
- 59 => 4,
- 31 => 6,
- 19 => 7,

And we should find a timestamp `t`

such that:

- Bus 7 departs at
`t`

- Bus 13 departs at
`t + 1`

- Bus 59 departs at
`t + 4`

- Bus 31 departs at
`t + 6`

- Bus 19 departs at
`t + 7`

This part was super confusing to me and I had to reread it a bunch of times to even make sense of it.

But then I used a super secret weapon... spreadsheets!

The "Time offset" column is just the bus's position in the initial list.

The "Offset gap" is the difference between this bus's time offset and the next - the last bus, bus 19, does not have an "offset gap", because there is no bus after it on the list.

All the cells below are simply `timestamp % bus_id`

. Zero values (which
correspond to departures) are highlighted in blue thanks to Google Sheets'
conditional formatting feature.

And here's what's interesting: if we look at the blue row in Bus 19's column, and look at the cell immediately to the left of it, we find the "offset gap" from Bus 31. If we take the blue cell in Bus 31's column and move left, we find the "offset gap" from Bus 59 - and so on.

If we keep going backwards all the way to the start of the list (Bus 7), and the cell to the left always matches the "offset gap", then we've found an answer: the blue cell in the first column.

There's probably a better explanation for all this, but it's XMas and my brain is broken, so it's easier for me to reason about this visually.

So we have a plan then?

I guess we do!

Let's go for it!

First let's attack parsing - we must now remember the position we found the bus in, in the provided list:

Rust code

#[derive(Debug)]structProblemStatement{departure_time:usize,buses:Vec<Bus>, }#[derive(Debug)]structBus{id:usize,time_offset:usize, }implProblemStatement{fnparse(input:&str)->Self{letmutlines = input.lines();ProblemStatement{departure_time: lines.next().unwrap().parse().unwrap(),buses: lines.next().unwrap().split(',').enumerate().filter_map(|(index, input)| { input.parse().ok().map(|id|Bus{ id,time_offset: index, })}).collect(), } } }fnmain(){letstat =ProblemStatement::parse(include_str!("input.txt"));dbg!(stat);}

Shell session`$ cargo run --quiet [src/main.rs:36] stat = ProblemStatement { departure_time: 939, buses: [ Bus { id: 7, time_offset: 0, }, Bus { id: 13, time_offset: 1, }, Bus { id: 59, time_offset: 4, }, Bus { id: 31, time_offset: 6, }, Bus { id: 19, time_offset: 7, }, ], }`

Okay, this matches our magical spreadsheet!

For the next part, I suppose... we could iterate over all our buses, and use
`tuple_windows`

to consider them pair-wise!

Shell session`$ cargo add itertools Adding itertools v0.9.0 to dependencies`

Rust code

fnmain(){letstat =ProblemStatement::parse(include_str!("input.txt"));useitertools::Itertools;stat.buses.iter().tuple_windows().for_each(|(earlier, later)| {letoffset_gap = later.time_offset- earlier.time_offset;dbg!("-----------", earlier.id, later.id, offset_gap);});}

Shell session`$ cargo run --quiet [src/main.rs:44] "-----------" = "-----------" [src/main.rs:44] earlier.id = 7 [src/main.rs:44] later.id = 13 [src/main.rs:44] offset_gap = 1 [src/main.rs:44] "-----------" = "-----------" [src/main.rs:44] earlier.id = 13 [src/main.rs:44] later.id = 59 [src/main.rs:44] offset_gap = 3 [src/main.rs:44] "-----------" = "-----------" [src/main.rs:44] earlier.id = 59 [src/main.rs:44] later.id = 31 [src/main.rs:44] offset_gap = 2 [src/main.rs:44] "-----------" = "-----------" [src/main.rs:44] earlier.id = 31 [src/main.rs:44] later.id = 19 [src/main.rs:44] offset_gap = 1`

Things are shaping up nicely! Here's the spreadsheet again for reference:

The offset gap between buses 31 and 19 should indeed by 1 (as per our spreadsheet), between 59 and 31 it should be 2, between 13 and 59, 3, and between 7 and 13, 1 again.

Let's go a little bit further - say we already know a potential solution (ie. a departure time for the last bus, Bus 19), can we check it?

Let's get fancy here and use a `fold`

! In fact, let's get even fancier, and
use a `Result<T, E>`

accumulator, where `T`

is a timestamp, and `E`

is a
custom error type:

Rust code

structWrongGap<'a>{earlier:&'aBus,later:&'aBus,offset_gap:usize,actual_gap:usize, }implfmt::DebugforWrongGap<'_>{fnfmt(&self,f:&mutfmt::Formatter<'_>)-> fmt::Result{write!(f,"expected Bus {} to leave {} minutes after Bus {}, but it left {} minutes after",self.later.id,self.earlier.id,self.offset_gap,self.actual_gap)} }implfmt::DisplayforWrongGap<'_>{fnfmt(&self,f:&mutfmt::Formatter<'_>)-> fmt::Result{ fmt::Debug::fmt(self, f)} }implstd::error::ErrorforWrongGap<'_>{}

And now let's use it:

Rust code

fnmain(){letstat =ProblemStatement::parse(include_str!("input.txt"));useitertools::Itertools;letsolution =1068781_usize;letok = stat.buses.iter().tuple_windows().fold(Ok::<_,WrongGap>(solution), |acc,(earlier, later)| {letearlier_timestamp = acc?;letlater_timestamp = earlier_timestamp + later.id-(earlier_timestamp % later.id);letoffset_gap = later.time_offset- earlier.time_offset;letactual_gap = later_timestamp - earlier_timestamp;ifoffset_gap == actual_gap { Ok(later_timestamp)}else{ Err(WrongGap{ earlier, later, earlier_timestamp, offset_gap, actual_gap, })} },);dbg!(&ok);}

Shell session`$ cargo run --quiet [src/main.rs:89] &ok = Ok( 1068788, )`

We already knew this solution was going to work - let's see how this behaves
with a value that's *not* a solution, like `256`

:

Rust code`$ cargo run --quiet`

[src/main.rs:91]&ok = Err(expected Bus13to leave7minutes after Bus1(which left at256), but it left4minutes after,)

How informative!

Thanks, I'm rather happy about it 😊

There's *one* thing I'd like to address before we start writing tests. Well, two.

First off, let's move all that into a method and add some debug printing:

Rust code

implProblemStatement{fncheck_solution(&self,solution:usize)->Result<(),WrongGap<'_>>{useitertools::Itertools;self.buses.iter().tuple_windows().fold(Ok::<_,WrongGap>(solution), |acc,(earlier, later)| {// 👇 here's the only debug print we needdbg!(&acc);letearlier_timestamp = acc?;letlater_timestamp = earlier_timestamp + later.id-(earlier_timestamp % later.id);letoffset_gap = later.time_offset- earlier.time_offset;letactual_gap = later_timestamp - earlier_timestamp;ifoffset_gap == actual_gap { Ok(later_timestamp)}else{ Err(WrongGap{ earlier, later, earlier_timestamp, offset_gap, actual_gap, })} }).map(|_|())} }

...and change `main`

to use it:

Rust code

fnmain(){letstat =ProblemStatement::parse(include_str!("input.txt"));dbg!(&stat.check_solution(256));}

Shell session`$ cargo run --quiet [src/main.rs:71] &acc = Ok( 256, ) [src/main.rs:71] &acc = Err( expected Bus 13 to leave 7 minutes after Bus 1 (which left at 256), but it left 4 minutes after, ) [src/main.rs:71] &acc = Err( expected Bus 13 to leave 7 minutes after Bus 1 (which left at 256), but it left 4 minutes after, ) [src/main.rs:71] &acc = Err( expected Bus 13 to leave 7 minutes after Bus 1 (which left at 256), but it left 4 minutes after, ) [src/main.rs:96] &stat.check_solution(256) = Err( expected Bus 13 to leave 7 minutes after Bus 1 (which left at 256), but it left 4 minutes after, )`

Ohh.. `fold`

ends up iterating through all items of the list even though we
fail on the first one?

Yup!

That's a shame though - I thought the `acc?`

trick was kinda neat - it's fun to
see error propagation going on in a closure passed to `fold`

!

It is! But it's rather inefficient here.

It's inefficient, because we're going to be testing lots of solutions -
pretty much every departure time of the first bus. So for every departure
time of the first bus, we're going to have `fold`

iterate through *all buses*
even if the next departure of the second bus wouldn't fit the puzzle input.

Luckily, there's a method for that!
`Iterator::try_fold`

allows us to "short-circuit" a `fold`

:

Rust code

implProblemStatement{fncheck_solution(&self,solution:usize)->Result<(),WrongGap<'_>>{useitertools::Itertools;self.buses.iter().tuple_windows()// 👇 here's our `try_fold`.try_fold(solution, |acc,(earlier, later)| {// 👇 that debug print is still here for now// (note that `acc` is now a `usize`, not a `Result<usize, WrongGap>`)dbg!(&acc);letearlier_timestamp = acc;letlater_timestamp = earlier_timestamp + later.id-(earlier_timestamp % later.id);letoffset_gap = later.time_offset- earlier.time_offset;letactual_gap = later_timestamp - earlier_timestamp;// 👇 we still return a `Result` though!ifoffset_gap == actual_gap { Ok(later_timestamp)}else{ Err(WrongGap{ earlier, later, earlier_timestamp, offset_gap, actual_gap, })} }).map(|_|())} }

Let's run it again with the wrong solution (`256`

):

Shell session`$ cargo run --quiet [src/main.rs:71] &acc = 256 [src/main.rs:97] &stat.check_solution(256) = Err( expected Bus 13 to leave 7 minutes after Bus 1 (which left at 256), but it left 4 minutes after, )`

It stopped immediately!

🙌

Now let's try to find the example's solution all by ourselves:

Rust code

implProblemStatement{fnsolve(&self)->usize{letfirst_bus =self.buses.first().unwrap();itertools::iterate(0, |&i| i + first_bus.id).find(|×tamp|self.check_solution(timestamp).is_ok()).unwrap()} }

So we're... generating all the departure times from the first bus, and stopping on the first one that's a valid solution to the problem?

That's exactly it!

Rust code

fnmain(){letstat =ProblemStatement::parse(include_str!("input.txt"));dbg!(&stat.solve());}

If you're following along, don't forget to remove the `dbg!`

from
`check_solution`

, unless you like *very noisy* terminal outputs
(and are patient).

Shell session`$ cargo run --quiet [src/main.rs:103] &stat.solve() = 1068781`

We can even add some tests, as we have a few examples provided in the statement for part 2:

Rust code

#[test]fntest_solutions(){macro_rules!test {($list: literal, $solution: expr)=> { assert_eq!(ProblemStatement::parse(concat!("0\n", $list,"\n")).solve(), $solution)};}test!("17,x,13,19",3417);test!("67,7,59,61",754018);test!("67,x,7,59,61",779210);test!("67,7,x,59,61",1261476);test!("1789,37,47,1889",1202161486);}

Ooh, I like this macro - tiny little macro, as a tiny little treat. Very handy.

Yup, I do that a lot - it's not quite a DSL, but it allows me to group all the test's data neatly in one place, and leave the logic elsewhere.

This test passes - it's always unsettling when things work first time like that, so I added a failing test just to make sure, and sure enough, it did fail.

I guess we're ready for prime time! Let's replace `input.txt`

with our actual
puzzle input, and run it in `release`

mode this time, because the problem statement
warns:

However, with so many bus IDs in your list, surely the actual earliest timestamp will be larger than

`100000000000000`

!

...so we can expect a fair bit of number crunching.

Shell session`$ cargo build --release Finished release [optimized] target(s) in 0.00s $ time ./target/release/day13`

Well...

It has been a few minutes, and nothing yet.

Yup.

...we might have to use maths for this one.

Yup.

Okay. OKAY. Well we were bound to stumble upon a problem we can't just use brute force on, at some point.

Fine. Let's try and explain some maths.

## Linear congruences

The problem as stated in Part 2 is akin to solving "a set of linear congruences".

What's a set of linear congruence? Well, here's one for example:

$\left{ \begin{aligned} x &\equiv 2 \pmod 3 \ x &\equiv 1 \pmod 5 \ x &\equiv 5 \pmod 7 \ \end{aligned} \right.$

A congruence is sorta like an equality, but in modular arithmetic.

$x \equiv 2 \pmod 3$ means "the remainder of euclidean division of $x$ by 3 must be 2" — this is true for a bunch of values of $x$!

In fact, on the number line, every third number is a solution, because we can rewrite it as $x = 3j + 2$.

And this is true for any value of $j$:

- when $j = 0$, we have $x = 3 \cdot 0 + 2 = 2$ so 2 is a solution
- when $j = 1$, we have $x = 3 \cdot 1 + 2 = 5$ so 5 is a solution
- when $j = 2$, we have $x = 3 \cdot 2 + 2 = 8$ so 8 is a solution
- etc.

But the other two congruences need to be true as well, so we end up having:

$\left{ \begin{aligned} x &= 3j + 2 \ x &= 5k + 1 \ x &= 7l + 5 \ \end{aligned} \right.$

And there's four unknowns ($x$, $j$, $k$, and $l$) and only three equations, so, it's not that straightforward. Well it turns out there's a method to solve these, and it's called the Chinese remainder theorem.

Let's walk through this particular example. First off, for convenience, we're going to re-order our congruences from largest modulo to smallest modulo - it doesn't matter much, they all need to be true anyway:

$\left{ \begin{aligned} x &\equiv 5 \pmod 7 \ x &\equiv 1 \pmod 5 \ x &\equiv 2 \pmod 3 \ \end{aligned} \right.$

Now, we write $x$ as an expression using the congruence with the largest modulo, 7:

$x = 7j + 5$

And replace $x$ in our second congruence with that expression. We can totally do that: $x$ must satisfy both of these, so we can substitute at will.

$\begin{aligned} x &\equiv 1 \pmod 5 \[.5em] 7j + 5 &\equiv 1 \pmod 5 \end{aligned}$

Now we need to *solve* that linear congruence. And here we find ourselves a
bit limited. See, if this was an equation, we could just "apply
transformation to both sides" until we've isolated $j$.

At first we'd have:

$7j + 5 = 1$

Then we'd subtract 5 on both sides:

$\begin{aligned} 7j + 5 - 5 &= 1 - 5 \ 7j &= -4 \end{aligned}$

Then divide by 7 on both sides:

$\begin{aligned} \frac{7j}{7} &= \frac{-4}{7} \[1em] j &= - \frac{4}{7} \end{aligned}$

And then boom, we'd be done!

But modular arithmetic doesn't *quite* work like that.

You keep bringing up "modular arithmetic" like it's just a thing... people know? With no further explanation?

Fair enough - let's talk about fundamentals for a bit. But don't get angry if I don't use the right nomenclature okay?

Sure - let's just try to intuit what we're talking about.

Now who's using fancy words.

## Modular arithmetic

Okay so - here's one way to look at it - with "regular" arithmetic, we're working on a number line, on which all signed integers have a place:

And when we have an equation like ${7j + 5 = 1}$, well, both the left-hand side (${7j + 5}$) and the right-hand-side (${1}$) are at the same place on that number line:

Here it's pretty easy to figure out where they are - one side is just ${1}$. But it doesn't matter much where they are - we could just as well remove the numbers from the number line:

The important thing when manipulating equations (equalities, pretty much) is to apply the same transformations to both sides. If we don't, they end up at different spots on the number line - for example, if we just subtract 5 from ${7j + 5}$, we get:

Suddenly both sides are not equal anymore. No, if we want to subtract 5, we
have to subtract it from *both sides*:

There's other transformations we can apply to both sides. Adding a positive number moves to the right

What about multiplication?

Well, multiplication modifies the distance to zero:

And so does division:

"Solving" an equation means isolating the unknown: applying transforms until the unknown (here, ${j}$) is alone on one side. Whatever is on the other side is its value.

Here, we picked a pretty poor example though, because ${j}$ is not an integer. If we divide both sides by 7, we land between two integers (${-1}$ and ${0}$):

Well, we can do some of it - kinda. We *can* subtract five on both sides, but
the result on the right hand side will be "mod 5" (modulo five).

Okay, what about modular arithmetic?

Well, with modular arithmetic, our numbers are not on a line, they're *on a
circle*. Say we're working "mod 8" (modulo eight), then our circle is
divided in eight slices:

Let's place 0 up top, and assign numbers clockwise:

Where's 8?

Well - here's the thing - it's more of a spiral really, because we can keep
going clockwise and place *all positive integers*:

What about negative integers?

Same deal! Except we spin in the other direction:

The fact that ${-2, 6, 14}$ are all at the same position on the "mod 8" circle means that "the remainder of their division by 8 is the same", ie.:

$-2 \bmod 8 = 6 \bmod 8 = 14 \bmod 8$

Of all the numbers that are on the circle, some we like more than others - the ones we assigned first. The "canonical" name for that position on the left is 6, because:

$\begin{aligned} -2 \bmod 8 &= 6 \ 6 \bmod 8 &= 6 \ 14 \bmod 8 &= 6 \ \end{aligned}$

And here's where we draw a parallel with "regular" arithmetic. When we have a linear congruence, like so:

$x \equiv 3 \pmod 8$

We're saying something about the position of ${x}$ on the "mod 8" circle - it's here:

If that's our only constraint, as we've seen, ${x}$ can be 3, 11, 19, 27, etc.
It can even be negative! As long as, when placed on the "mod 8" circle, it
ends up at *that position*.

Okay - and how do we *solve* a linear congruence? Like an equation?

Sort of, yeah!

Sometimes our linear congruence is a bit more complicated, say, maybe it's ${7j + 5 \equiv 1 \pmod 5}$:

Well, we can still apply transformations - addition and subtraction are particularly easy - adding just moves along the circle clockwise, and subtracting moves counter-clockwise (unless you're adding/subtracting negative numbers, in which case it's the other way around).

Here for example, we can subtract 5!:

(And since we're modulo 5, we end up at the exact same spot)

But then we have a little conundrum.

Multiplication is well-defined: just like on the number line, it increases the distance to zero - except it wraps around, so, uh, sometimes you end up closer to zero than were you started.

Circles, I tell you.

How do they work??!

However, there's no such thing as division.

There's not?

Not really no. Well.. okay, sort of.

Let's get back to the number line, and talk about powers (or exponents).

## Powers / exponents

Any integer to the 0th power is 1. Any integer to the 1st power is itself. Any integer to the 2nd power is itself times itself - and so on.

$\begin{aligned} x^0 &= 1 \ x^1 &= x \ x^2 &= x \cdot x \ x^3 &= x \cdot x \cdot x \ \dots \end{aligned}$

But what about *negative* powers? Well, x to the... "negative first" power?
It's ${\frac{1}{x}}$. So we can complete our little list so that it's nice and symmetric:

$\begin{aligned} \dots \ x^{-3} &= \frac{1}{x \cdot x \cdot x} \ x^{-2} &= \frac{1}{x \cdot x} \ x^{-1} &= \frac{1}{x} \ x^0 &= 1 \ x^1 &= x \ x^2 &= x \cdot x \ x^3 &= x \cdot x \cdot x \ \dots \end{aligned}$

There's also a very nice symmetry between:

- addition and subtraction
- multiplication and division
- positive and negative powers

For example, we have:

$\begin{aligned} a^x a^y &= a^{x+y} \ \frac{a^x}{a^y} &= a^{x-y} \ \end{aligned}$

Which explains why ${x^{-1} = \frac{1}{x}}$, by the way:

$\frac{1}{x} = \frac{x^0}{x^1} = x^{0-1} = x^{-1}$

That does look nice, but uhhh.. are we getting lost?

Not at all!

See, where this gets interesting is that we can transform division into multiplication, because:

$\frac{x}{y} = x \left(\frac{1}{y}\right) = x y^{-1}$

Oohhhhh we can totally do multiplication in modular arithmetic!

Yes we bloody well can!

On the `mod m`

circle, for a number `a`

, if we can find a number (let's call
it `i`

for now) such that, when multiplied with `a`

, it gives 1, then we can do this:

$\begin{aligned} ax &\equiv b \pmod m \ iax &\equiv ib \pmod m \ \end{aligned}$

And because we know that ${ia = 1}$,

$x \equiv ib \pmod m$

We just got rid of a! Ahhhhh!!!

That number is actually written as $a^{-1}$, and it's called the "modular multiplicative inverse of a (mod m)":

$\begin{aligned} ax &\equiv b \pmod m \ a^{-1}ax &\equiv a^{-1}b \pmod m \ x &\equiv a^{-1}b \pmod m \ \end{aligned}$

Which brings us to the next question: how do we find the "modular multiplicative inverse" of a number ${a}$, modulo ${m}$?

The full name really is "the modular multiplicative inverse of a modulo m":
the "modulo m" part is important, even though it doesn't appear in the `a⁻¹`

notation, the "multiplicative inverse" would be different for different
modulos.

Well, there's a couple methods! The first one is the "extended euclidean algorithm". Which is itself a downloadable addon to the "euclidean algorithm", so let's start with the base game.

## The Euclidean algorithm

When two numbers love each other very much, they have a Greatest Common Divisor. For example, ${21}$ and ${33}$ have a ${GCD}$ of ${3}$ - it's the largest number by which they can both be divided.

$\begin{aligned} GCD(21, 33) &= 3 \ \frac{21}{3} &= 7 \ \frac{33}{3} &= 11 \ \end{aligned}$

There's a bunch of ways to find the greatest common divisor of two numbers. One of them is to just decompose them into a product of prime factors:

$\begin{aligned} 21 &= 3 \cdot 7 \ 33 &= 3 \cdot 11 \ \end{aligned}$

Then take the common factors (here, we just have ${3}$), multiply them together, and voilà! One ${GCD}$.

What's a prime number again?

Ah, a prime number is a number that has *exactly two divisors*: ${1}$ and
itself.

So `1`

is not a prime number?

No it's not! But ${2}$, ${3}$, ${5}$, ${7}$, ${11}$ etc. are prime numbers.

Furthermore, if the ${GCD}$ of two numbers is ${1}$, then they're said to be "coprime". It's easy to build a pair of coprime numbers: just pick different prime factors, for example:

$\begin{aligned} 2^1 \cdot 11^2 &= 242 \ 3^1 \cdot 7^2 &= 147 \ \end{aligned}$

These are pretty large, so you'd think they'd have a common divisor other than ${1}$, right? Wrong.

Another method to find the GCD is just to find all the divisors of both numbers, and take the... greatest one they have in common. That method is annoying.

A slightly less annoying method is, well, the Euclidean algorithm.

Let's say ${L}$ is the larger number, and ${l}$ is the smaller number, then the idea is to write down this:

$L = al + b$

$a$ and $b$ are easy to find - $b$ is the remainder of the integer division of $L$ by $l$,
and $a$ is well, the *result* of the integer division of $L$ by $l$.

Then we keep going - trying to divide $l$ by $b$, and so on and so forth.

Uhhh can we have an example?

Say we're trying to find the $GCD$ of ${888}$ and ${54}$, we have:

When we have a remainder of ${0}$, we're done! Our answer is ${GCD(888, 54) = 6}$.

## Extended euclidean algorithm

With the Euclidean algorithm, we've just calculated ${GCD(a, b)}$, where ${a = 888}$
and ${b = 54}$. With the *extended* euclidean algorithm, we can find an $x$ and $y$
such that:

$ax + by = GCD(a, b)$

That's apparently called Bézout's identity.

And we can find $x$ and $y$ by manipulating the equalities we got when following the Euclidean algorithm a little:

There we have it! We have $x = -2$ and $y = 33$.

But what does this have to do with the "modular multiplicative inverse modulo m"? Well... say we have the following congruence:

$a \equiv b \pmod m$

Then if $a$ and $m$ are coprime, their GCD is 1.

Then, Bézout's identity, which is:

$ax + my = GCD(a, m)$

Becomes:

$ax + my = 1$

Which is very, very interesting. Because, if we're "modulo m", then we have:

$ax + my \equiv 1 \pmod m$

But ${m \bmod m = 0}$, so it all reduces down to:

$\begin{aligned} ax + 0 \cdot y &\equiv 1 \pmod m \ ax &\equiv 1 \pmod m \ \end{aligned}$

Ohhhhh, `x`

is `a⁻¹`

!!!

Yes it is!

So, for ${7}$ and ${5}$, in ${7j \equiv 1 \pmod 5}$, let's run through the whole thing again.

First, the Euclidean Algorithm:

$\begin{aligned} 7 &= 1 \cdot 5 + 2 \ 5 &= 2 \cdot 2 + 1 \ 2 &= 2 \cdot 1 + 0 \ \end{aligned}$

Then the Extended Euclidean algorithm:

$\begin{aligned} 1 &= 5 - 2 \cdot 2 \ 1 &= 5 - 2 (7 - 5) \ 1 &= 3 \cdot 5 - 2 \cdot 7 \ \end{aligned}$

Which gives us ${7^{-1} = -2 \pmod 5}$ — we've found the modular
multiplicative inverse of 7 modulo 5! And since we're modulo 5, we have ${-2
\bmod 5 = 3}$, so ${3}$ is *also* the modular multiplicative inverse of 7
modulo 5.

Using it, we can get rid of the factor 7 in our linear congruence:

$\begin{aligned} 7j &\equiv 1 \pmod 5 \ 7^{-1} \cdot 7j &\equiv 7^{-1} \cdot 1 \pmod 5 \ j &\equiv 3 \cdot 1 \pmod 5 \ j &\equiv 3 \pmod 5 \ \end{aligned}$

Let's make *another* spreadsheet to make sure everything checks out:

Looks good!

However, the Extended Euclidean Algorithm seems rather annoying to implement in code. I'm sure it's not that bad, but we have an even simpler way available due to what our puzzle input is.

## Euler's totient

Another method to determine the modular multiplicative inverse of $a$ modulo $m$ exists, if $a$ and $m$ are coprime. For ${7j \equiv 1 \pmod 5}$, it's definitely the case: both ${7}$ and ${5}$ are prime.

In that case, we have:

$a^{\phi(m)} \equiv 1 \pmod m$

And:

$a^{\phi(m)-1} \equiv a^{-1} \pmod m$

Where phi (`ϕ`

) is Euler's totient function.

Euler's what know?

${\phi(m)}$ counts the positive integers up to $m$ that are relatively prime to $m$.

If $m$ is prime, it's even easier! *All* integers $n$ between ${1}$ and ${m-1}$
(included) are relatively prime to $m$ - in other words, $GCD(n, m) = 1$.

So, for a prime $m$, we have $\phi(m) = m - 1$, and thus:

$a^{\phi(m)-1} \equiv a^{-1} \pmod m$

Becomes:

$a^{(m-1)-1} \equiv a^{-1} \pmod m$

Which reduces to:

$a^{m-2} \equiv a^{-1} \pmod m$

Using this, we can find ${7^{-1} \pmod 5}$:

$\begin{aligned} 7^{-1} &\equiv 7^{5-2} \pmod 5 \ 7^{-1} &\equiv 7^3 \pmod 5 \ 7^{-1} &\equiv 343 \pmod 5 \ (343 \bmod 5 &= 3) \ 7^{-1} &\equiv 3 \pmod 5 \ \end{aligned}$

We get the same result!

From there - I have good news and bad news. Which do you want to hear first, bear?

Let's hear the good news first!

Here's the good news: I don't know if you've noticed, but *all the bus IDs*
in the puzzle inputs are prime numbers.

In my puzzle input, I have ${19, 37, 383, 23, 13, 29, 457, 41, 17}$ - they're all primes. This is not a coincidence! I believe the Advent of Code writers have done this on purpose.

Sounds good! So we can use Euler's totient there?

Yes!

Although... that's where the bad news come in. Say we have the following linear congruence:

$13j \equiv 2 \pmod{457}$

Using Euler's totient, we can find the modular multiplicative inverse of 13 modulo 457 like so:

$\begin{aligned} 13^{-1} &\equiv 13^{457-2} \pmod{457} \ 13^{-1} &\equiv 13^{455} \pmod{457} \ \end{aligned}$

The problem is that uh... ${13^{455}}$ is a *huge* number.

Huge.

As in, it doesn't fit in a `u64`

:

Rust code

fnmain(){dbg!(13_u64.pow(455));}

Shell session`Compiling playground v0.0.1 (/playground) Finished dev [unoptimized + debuginfo] target(s) in 1.41s Running `target/debug/playground` thread 'main' panicked at 'attempt to multiply with overflow', /rustc/7eac88abb2e57e752f3302f02be5f3ce3d7adfb4/library/core/src/num/mod.rs:707:5`

Heck, it doesn't even fit in an `u128`

!

We could, of course, use something like num-bigint.

Rust code

usenum_bigint::BigUint;fnmain(){leta:BigUint="13".parse().unwrap();dbg!(a.pow(455).to_str_radix(10));}

Shell session`Compiling playground v0.0.1 (/playground) Finished dev [unoptimized + debuginfo] target(s) in 3.41s Running `target/debug/playground` [src/main.rs:5] a.pow(455).to_str_radix(10) = "698594721138087101169088219064926429093683995717535691958391180527375156988715725642243890871883009275610843781276220679332947793384643076241831002323658555648998535582443808358436808350475323422663450896893453131394048123221684800209034474726802596033203335669614369076809716123273257303071068129527888344287266217650968529754239505317017230570888006093561845355916409336361243674362617819009028956341804832084422627863716588624177425577212277628851844621576921451262128531363806650216682920524232108345957"`

That's a *big* number!

Yup! It has 507 digits.

But here's the interesting thing - just as before, there's a much smaller modular multiplicative inverse: that value modulo 457, which happens to be 211.

It doesn't stop there though: remember how powers work? ${13^{455}}$ is just:

$13^{455} = 13 \cdot 13 \cdot 13 \dots 13 \cdot 13$

And remember that we're also "modulo 457". So we can compute it by doing each individual multiplication, and only keeping the remainder of euclidean division by 457 at every step:

$\begin{aligned} 13^2 &\equiv 13 \cdot 13 &\equiv 169 \pmod{457} \ 13^3 &\equiv 13^2 \cdot 13 &\equiv 169 \cdot 13 \equiv 2197 \equiv 369 \pmod{457} \ 13^4 &\equiv 13^3 \cdot 13 &\equiv 369 \cdot 13 \equiv 4797 \equiv 227 \pmod{457} \ \dots \ \end{aligned}$

Or, in code:

Rust code

fnmain(){leta =13_u64;letm =457_u64;letmuta_mmi =1;for_in1..=(m-2){ a_mmi =(a_mmi*a)% m;}dbg!(a_mmi);}

Shell session`Compiling playground v0.0.1 (/playground) Finished dev [unoptimized + debuginfo] target(s) in 3.15s Running `target/debug/playground` [src/main.rs:9] a_mmi = 211`

Of course, we could optimize that - we only need to wrap around when we would
overflow `u64`

. Luckily, Rust comes with a `checked_pow`

function that simply
returns `None`

if we would overflow, so:

Rust code

fnmain(){dbg!(modular_multiplicative_inverse(13,457));}/// Finds the modular multiplicative inverse of `a` modulo `m`/// Returns the wrong result if `m` isn't prime.fnmodular_multiplicative_inverse(a:i64,m:u32)->i64{modular_pow(a, m -2, mas_)}fnmodular_pow(x:i64,exp:u32,modulo:i64)->i64{(matchx.checked_pow(exp){ Some(x)=> x, None => {letexp_a = exp /2;letexp_b = exp - exp_a;modular_pow(x, exp_a, modulo)*modular_pow(x, exp_b, modulo)} })% modulo }

Aww this would be so cool with tail call optimization.

One day, bearrito.

Shell session`Compiling playground v0.0.1 (/playground) Finished dev [unoptimized + debuginfo] target(s) in 0.78s Running `target/debug/playground` [src/main.rs:2] modular_multiplicative_inverse(13, 457) = 211`

Out of curiosity, I added some debug printing to know how many times
`modular_pow`

was called: turns out, just 63 times! Much better than our 457
loop than before. I have no doubt there are even smarter solutions out there,
but this'll do.

Notably, `num-bigint`

provides a
`modpow`

function, whose comment mentions "Montgomery multiplication" for any odd modulus - this
seems like it would work here, except for `m = 2`

(the only prime that's also an even
number), for which the result of `modular_multiplicative_inverse`

would be `1`

anyway,
since `aᵐ⁻² = a⁰ = 1`

.

But let's not make this article any longer, shall we.

Okay! Should we get back to the problem at hand?

## Solving a system of linear congruences (again)

Let's go back to this set of linear congruences:

$\left{ \begin{aligned} x &\equiv 5 \pmod 7 \ x &\equiv 1 \pmod 5 \ x &\equiv 2 \pmod 3 \ \end{aligned} \right.$

We rewrote $x$ as:

$x = 7j + 5$

Then substituted `x`

in the second linear congruence:

$\begin{aligned} x &\equiv 1 \pmod 5 \ 7j + 5 &\equiv 1 \pmod 5 \ 7j &\equiv 1 - 5 \equiv 1 \pmod 5 \ \end{aligned}$

We've just seen that the modular multiplicative inverse of 7 modulo 5 is 3, so that gives us ${j \equiv 3 \pmod 5}$.

Rewriting this as an expression, we get:

$j = 5k + 3$

Then we substitute `j`

:

$\begin{aligned} x &= 7j + 5 \ x &= 7(5k + 3) + 5 \ x &= 35k + 7 \cdot 3 + 5 \ x &= 35k + 26 \ \end{aligned}$

Finally, we substitute `x`

in our last congruence:

$\begin{aligned} x &\equiv 2 \pmod 3 \ 35k + 26 &\equiv 2 \pmod 3 \ \end{aligned}$

And solve it:

$\begin{aligned} 35k &\equiv (2 - 26) \equiv -24 \equiv 0 \pmod 3 \ 35k &\equiv 0 \pmod 3 \ \end{aligned}$

We need the modular multiplicative inverse of 35 modulo 3. Luckily, 3 is prime, so we can re-use our code...

Hang on - don't we have 0 on the right-hand side? Doesn't that mean that whatever we multiply both sides by, the right-hand side will remain 0?

Oh, good call!

That means we can just get rid of the 35 factor:

$k \equiv 0 \pmod 3$

Then express `k`

:

$k = 3l$

Substitute `k`

in our last expression for `x`

:

$\begin{aligned} x &= 35k + 26 \ x &= 35(3l) + 26 \ x &= 105l + 26 \ \end{aligned}$

And that's our solution!

Spreadsheet?

Spreadsheet!

As a reminder, this was our set:

$\begin{aligned} x &\equiv 5 \pmod 7 \ x &\equiv 1 \pmod 5 \ x &\equiv 2 \pmod 3 \ \end{aligned}$

Awesome!

## Another example

I think it's time to move on to an example from the Advent of Code: the following input:

`17,x,13,19`

Translates to the following set of linear congruences:

$\left{ \begin{aligned} x &\equiv 0 \pmod{17} \ x &\equiv 2 \pmod{13} \ x &\equiv 3 \pmod{19} \ \end{aligned} \right.$

The remainders (0, 2 and 3) are the position of the items in the list.

We'll do exactly as before - but we'll try and write a bit of code to help us along the way.

Our first congruence gives us the following expression:

$x = 17j$

We can then replace it in the second congruence:

$\begin{aligned} x &\equiv 2 \pmod{13} \ 17j &\equiv 2 \pmod{13} \ \end{aligned}$

Let's think about how we could solve that congruence in code.

First we'd need a way to represent it. There's probably a very simple way to
do all this, but I haven't looked at anyone else's code, so I just want to try
and reproduce *in code* what we've been doing by hand.

If we're going to write a "solver", we need to be able to represent expressions, including expressions with variables.

We could start with something as simple as this:

Rust code

#[derive(Clone, Debug, PartialEq, Eq)]enumExpr{ Literal(i64), Var, Add(Vec<Expr>), Mul(Vec<Expr>), }

Then we can start working on a "reduce" method: for example, `Add(vec![2, 3])`

should reduce to `Literal(5)`

.

Rust code

implExpr{fnreduce(&self)->Expr{matchself{&Expr::Literal(lit)=>Expr::Literal(lit),Expr::Var =>Expr::Var,Expr::Add(items)=> {let(literals, others):(Vec<_>,Vec<_>)= items.iter().map(Self::reduce).partition(|x|matches!(x, Self::Literal(_)));ifliterals.is_empty()&& others.is_empty(){Expr::Literal(0)}else{letmutterms = others;letsum = literals.into_iter().map(|x| {ifletExpr::Literal(x)= x { x }else{unreachable!()} }).sum();ifsum !=0{ifterms.is_empty(){returnSelf::Literal(sum);}else{ terms.insert(0,Self::Literal(sum));} }ifterms.len()==1{ terms.pop().unwrap()}else{Expr::Add(terms)} } }Expr::Mul(items)=> {let(literals, others):(Vec<_>,Vec<_>)= items.iter().map(Self::reduce).partition(|x|matches!(x, Self::Literal(_)));ifliterals.is_empty()&& others.is_empty(){Expr::Literal(1)}else{letmutterms = others;letproduct = literals.into_iter().map(|x| {ifletExpr::Literal(x)= x { x }else{unreachable!()} }).product();ifproduct !=1{ifterms.is_empty(){returnSelf::Literal(product);}else{ terms.insert(0,Self::Literal(product));} }ifterms.len()==1{ terms.pop().unwrap()}else{Expr::Mul(terms)} } } } } }

That's a lot of code, let's write some tests!

Rust code

#[test]fntest_reduce(){assert_eq!(Expr::Add(vec![]).reduce(), Expr::Literal(0).reduce());assert_eq!(Expr::Add(vec![Expr::Literal(2), Expr::Literal(3)]).reduce(), Expr::Add(vec![Expr::Literal(5)]).reduce(),);assert_eq!(Expr::Add(vec![Expr::Literal(2), Expr::Literal(3), Expr::Literal(5)]).reduce(), Expr::Add(vec![Expr::Literal(10)]).reduce(),);assert_eq!(Expr::Add(vec![Expr::Literal(2), Expr::Literal(3), Expr::Var]).reduce(), Expr::Add(vec![Expr::Literal(5), Expr::Var]).reduce(),);assert_eq!(Expr::Mul(vec![Expr::Literal(2), Expr::Literal(3), Expr::Var]).reduce(), Expr::Mul(vec![Expr::Literal(6), Expr::Var]).reduce(),);assert_eq!(Expr::Mul(vec![Expr::Add(vec![Expr::Literal(2), Expr::Literal(3)]), Expr::Literal(10), Expr::Var]).reduce(), Expr::Mul(vec![Expr::Literal(50), Expr::Var]).reduce(),);}

This passes - seems like a decent start!

Now we must have a way to represent linear congruences:

Rust code

#[derive(Clone, Debug, PartialEq, Eq)]structLinearCongruence{lhs:Expr,rhs:Expr,modulo:u32, }

Now, we can represent the linear congruence we wanted to solve:

Rust code

fnmain(){letlc =LinearCongruence{lhs:Expr::Mul(vec![Expr::Literal(17), Expr::Var]),rhs:Expr::Literal(2),modulo:13, };println!("{:?}", lc);}

Shell session`$ cargo run --quiet LinearCongruence { lhs: Mul([Literal(17), Var]), rhs: Literal(2), modulo: 13 }`

Mhh, this isn't the prettiest way we could print that. How about we provide
a custom `Debug`

implementation for `Expr`

?

Rust code

implfmt::DebugforExpr{fnfmt(&self,f:&mutfmt::Formatter<'_>)-> fmt::Result{matchself{&Expr::Literal(lit)=>write!(f,"{}", lit),Expr::Var =>write!(f,"x"),Expr::Add(terms)=> {write!(f,"(")?;for(i, term)interms.iter().enumerate(){ifi ==0{write!(f,"{:?}", term)?;}else{write!(f," + {:?}", term)?;} }write!(f,")")?;Ok(())}Expr::Mul(terms)=> {write!(f,"(")?;for(i, term)interms.iter().enumerate(){ifi ==0{write!(f,"{:?}", term)?;}else{write!(f," * {:?}", term)?;} }write!(f,")")?;Ok(())} } } }

Shell session`$ cargo run --quiet LinearCongruence { lhs: (17 * x), rhs: 2, modulo: 13 }`

Better! Now a custom `Debug`

implementation for `LinearCongruence`

:

Rust code

implfmt::DebugforLinearCongruence{fnfmt(&self,f:&mutfmt::Formatter<'_>)-> fmt::Result{write!(f,"{:?} ≡ {:?} (mod {})",self.lhs,self.rhs,self.modulo)} }

Shell session`$ cargo run --quiet (17 * x) ≡ 2 (mod 13)`

Super neat!

It's time to try and solve linear congruences in code.

This case is easy - we just need to multiply both sides by the modular multiplicative inverse of 17.

Rust code

#[derive(Debug)]structCantSolve(LinearCongruence);implfmt::DisplayforCantSolve{fnfmt(&self,f:&mutfmt::Formatter<'_>)-> fmt::Result{ fmt::Debug::fmt(self, f)} }implstd::error::ErrorforCantSolve{}implLinearCongruence{fnsolve(&self)->Result<Self,CantSolve>{ifletExpr::Mul(items)=&self.lhs{iflet[Expr::Literal(lit),Expr::Var]= items[..]{letmmi =modular_multiplicative_inverse(litas_,self.modulo);todo!("Must multiply both sides by {}", mmi);} } Err(CantSolve(self.clone()))} }

Let's stop there and verify it's attempting the right thing:

Rust code

fnmain(){letlc =LinearCongruence{lhs:Expr::Mul(vec![Expr::Literal(17), Expr::Var]),rhs:Expr::Literal(2),modulo:13, };dbg!(&lc);letlc = lc.solve().unwrap();dbg!(&lc);}

Shell session`$ cargo run --quiet [src/main.rs:326] &lc = (17 * x) ≡ 2 (mod 13) thread 'main' panicked at 'not yet implemented: Must multiply both sides by 10', src/main.rs:312:17 note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace`

Seems fairly straightforward - except we haven't really taught our `reduce`

method about modulos, so if we just do the obvious - multiply on both sides:

Rust code

implExpr{/// Multiply `self` by `expr`fnmul(&self,expr:Expr)->Self{matchself{Self::Mul(items)=> {Self::Mul(std::iter::once(expr).chain(items.iter().cloned()).collect())} _ =>Self::Mul(vec![expr,self.clone()]), } } }implLinearCongruence{/// Multiply both sides of congruence by `expr`fnmul(&self,expr:Expr)->Self{Self{lhs:self.lhs.mul(expr.clone()).reduce(),rhs:self.rhs.mul(expr).reduce(),modulo:self.modulo, } } }implLinearCongruence{fnsolve(&self)->Result<Self,CantSolve>{eprintln!("should solve {:?}",self);ifletExpr::Mul(items)=&self.lhs{iflet[Expr::Literal(lit),Expr::Var]= items[..]{letmmi =modular_multiplicative_inverse(lit,self.modulo);eprintln!("multiplying by mmi: {}", mmi);returnself.mul(Expr::Literal(mmi)).solve();} } Err(CantSolve(self.clone()))} }fnmain(){letlc =LinearCongruence{lhs:Expr::Mul(vec![Expr::Literal(17), Expr::Var]),rhs:Expr::Literal(2),modulo:13, };letlc = lc.solve().unwrap();dbg!(&lc);}

We get an infinite loop:

Shell session`$ cargo run --quiet 2>&1 | head should solve (17 * x) ≡ 2 (mod 13) multiplying by mmi: 10 should solve (170 * x) ≡ 20 (mod 13) multiplying by mmi: 1 should solve (170 * x) ≡ 20 (mod 13) multiplying by mmi: 1 should solve (170 * x) ≡ 20 (mod 13) multiplying by mmi: 1 should solve (170 * x) ≡ 20 (mod 13) multiplying by mmi: 1`

Because ${170 \bmod 13 = 1}$, but `Expr`

doesn't know we're modulo 13! So,
I think we need a second method - `modulo`

:

Rust code

implExpr{fnmodulo(&self,modulo:u32)->Self{matchself{&Self::Literal(lit)=>Expr::Literal(lit.rem_euclid(moduloas_)),Self::Var =>Expr::Var,Self::Add(_)=>self.clone(),Self::Mul(items)=>Self::Mul(items.iter().map(|x| x.modulo(modulo)).collect()), } } }

In the case of `mul`

, we `reduce`

again, because if we start with ${170x}$ and end
up with ${1x}$, we want to get rid of that ${1}$.

Let's try it out:

Rust code

implLinearCongruence{/// Multiply both sides of congruence by `expr`fnmul(&self,expr:Expr)->Self{Self{lhs:self.lhs.mul(expr.clone()).reduce().modulo(self.modulo),rhs:self.rhs.mul(expr).reduce().modulo(self.modulo),modulo:self.modulo, } } }

Shell session`$ cargo run --quiet should solve (17 * x) ≡ 2 (mod 13) multiplying by mmi: 10 should solve x ≡ 7 (mod 13) thread 'main' panicked at 'called `Result::unwrap()` on an `Err` value: CantSolve(x ≡ 7 (mod 13))', src/main.rs:372:25 note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace`

Alright! Turns out, this is the solved form - the variable is isolated on the left, there's nothing left to do.

Let's add a condition for that:

Rust code

implLinearCongruence{fnsolve(&self)->Result<Self,CantSolve>{eprintln!("should solve {:?}",self);ifletExpr::Mul(items)=&self.lhs{iflet[Expr::Literal(lit),Expr::Var]= items[..]{letmmi =modular_multiplicative_inverse(lit,self.modulo);eprintln!("multiplying by mmi: {}", mmi);returnself.mul(Expr::Literal(mmi)).solve();} }ifletExpr::Var =&self.lhs{// 👇// already solved!returnOk(self.clone());} Err(CantSolve(self.clone()))} }

Rust code`$ cargo run --quiet should`

solve(17*x)≡2(mod13)multiplying by mmi:10should solve x ≡7(mod13)[src/main.rs:378]&lc = x ≡7(mod13)

Okay! We've solved ${17j \equiv 2 \pmod{13}}$ with code.

Awesome!

What were we doing again? Oh right, solving a set of linear congruences.

Now we can express $j$ as an.. expression:

Rust code

implLinearCongruence{/// Turns this linear congruence into an expression,/// for example `x ≡ 7 (mod 13)` would give `13*var + 7`./// Panics if linear congruence is not solved yet.fnexpr(&self)->Expr{match(&self.lhs,&self.rhs){(Expr::Var,&Expr::Literal(remainder))=>Expr::Add(vec![Expr::Mul(vec![Expr::Literal(self.moduloas_), Expr::Var]), Expr::Literal(remainder),]), _ => {panic!("Expected solved congruence (of form `var ≡ literal (mod m)`), but got `{:?}`",self)} } } }

Rust code

fnmain(){letlc =LinearCongruence{lhs:Expr::Mul(vec![Expr::Literal(17), Expr::Var]),rhs:Expr::Literal(2),modulo:13, };letlc = lc.solve().unwrap();dbg!(&lc);// 👇 new!letexpr = lc.expr();dbg!(&expr);}

Shell session`$ cargo run --quiet should solve (17 * x) ≡ 2 (mod 13) multiplying by mmi: 10 should solve x ≡ 7 (mod 13) [src/main.rs:398] &lc = x ≡ 7 (mod 13) [src/main.rs:400] &expr = ((13 * x) + 7)`

Things get a bit confusing here, since we only have one variable in code (for simplicity), when we actually are dealing with several variables in the maths world.

Let's recap what we've done so far:

$\begin{aligned} &\text{From first congruence} \ x &\equiv 0 \pmod{17} \ &\text{As an equation} \ x &= 17j + 0 = 17j \ &\text{From second congruence} \ x &\equiv 2 \pmod{13} \ &\text{Substitution} \ 17j &\equiv 2 \pmod{13} \ &\text{After solving} \ j &\equiv 7 \pmod{13} \ &\text{As an equation} \ j &= 13k + 7 \ \end{aligned}$

Now we need to replace the $j$ in ${x = 17j}$ with ${13k + 7}$.

Let's try and make a method for that:

Rust code

implExpr{// Replaces `Expr::Var` with `expr` everywhere in that expressionfnreplace(&self,expr:Expr)->Self{matchself{&Expr::Literal(lit)=>Expr::Literal(lit),Expr::Var => expr,Expr::Add(items)=>Expr::Add(items.iter().cloned().map(|ex| ex.replace(expr.clone())).collect(),),Expr::Mul(items)=>Expr::Mul(items.iter().cloned().map(|ex| ex.replace(expr.clone())).collect(),), } } }

And actually do it:

Rust code

fnmain(){letlc =LinearCongruence{lhs:Expr::Mul(vec![Expr::Literal(17), Expr::Var]),rhs:Expr::Literal(2),modulo:13, };letlc = lc.solve().unwrap();dbg!(&lc);letexpr = lc.expr();dbg!(&expr);letexpr =LinearCongruence{lhs:Expr::Var,rhs:Expr::Literal(0),modulo:17, }.expr().replace(expr);dbg!(&expr);}

Shell session`$ main ❯ cargo run --quiet should solve (17 * x) ≡ 2 (mod 13) multiplying by mmi: 10 should solve x ≡ 7 (mod 13) [src/main.rs:452] &lc = x ≡ 7 (mod 13) [src/main.rs:454] &expr = ((13 * x) + 7) [src/main.rs:463] &expr = ((17 * ((13 * x) + 7)) + 0`

Things are getting quite confusing now, since `x`

is used for everything.

Let's make a slight adjustement: `Var`

will now take a `char`

- but we'll
still assume we only ever have *one* var in a given expression.

Rust code

#[derive(Clone, PartialEq, Eq)]enumExpr{ Literal(i64), Var(char), Add(Vec<Expr>), Mul(Vec<Expr>), }

We'll need to fix up our `Debug`

implementation:

Rust code

implfmt::DebugforExpr{fnfmt(&self,f:&mutfmt::Formatter<'_>)-> fmt::Result{matchself{&Expr::Literal(lit)=>write!(f,"{}", lit),// 👇Expr::Var(c)=>write!(f,"{}", c),// (other arms omitted)} } }

along with `Expr::reduce`

, our reduce tests, `LinearCongruence::solve`

,
also `LinearCongruence::expr`

- which will now take the name of the new
variable:

Rust code

implLinearCongruence{/// Turns this linear congruence into an expression,/// for example `x ≡ 7 (mod 13)` would give `13*name + 7`./// Panics if linear congruence is not solved yet.// 👇fnexpr(&self,name:char)->Expr{match(&self.lhs,&self.rhs){(Expr::Var(_),&Expr::Literal(remainder))=>Expr::Add(vec![// 👇Expr::Mul(vec![Expr::Literal(self.moduloas_), Expr::Var(name)]), Expr::Literal(remainder),]), _ => {panic!("Expected solved congruence (of form `var ≡ literal (mod m)`), but got `{:?}`",self)} } } }

(The changes that aren't shown are left as an exercise to the reader).

And to really be able to describe what we're doing with just method calls, we'll
add a `replace`

method to `LinearCongruence`

as well:

Rust code

implLinearCongruence{// Replaces `Expr::Var` with `expr` everywhere in that expressionfnreplace(&self,expr:Expr)->Self{Self{lhs:self.lhs.replace(expr.clone()),rhs:self.rhs.replace(expr),modulo:self.modulo, } } }

Now let's use actual names in our `main`

function.

Rust code

fnmain(){letcon1 =LinearCongruence{lhs:Expr::Var('x'),rhs:Expr::Literal(0),modulo:17, };letcon2 =LinearCongruence{lhs:Expr::Var('x'),rhs:Expr::Literal(2),modulo:13, };letcon3 =LinearCongruence{lhs:Expr::Var('x'),rhs:Expr::Literal(3),modulo:19, };println!("First congruence");println!("{:?}", con1);letx = con1.expr('j');println!("x = {:?}", x);letx = x.reduce();println!("After simplification");println!("x = {:?}", x);println!("Second congruence");println!("{:?}", con2);letcon2 = con2.replace(x.clone());println!("After substitution");println!("{:?}", con2);letcon2 = con2.solve().unwrap();println!("Solved");println!("{:?}", con2);println!("As equation");letj = con2.expr('k');println!("j = {:?}", j);println!("After substitution");letx = x.replace(j);println!("x = {:?}", x);println!("After simplification");letx = x.reduce();println!("x = {:?}", x);}

Shell session`$ cargo run --quiet First congruence x ≡ 0 (mod 17) x = ((17 * j) + 0) After simplification x = (17 * j) Second congruence x ≡ 2 (mod 13) After substitution (17 * j) ≡ 2 (mod 13) should solve (17 * j) ≡ 2 (mod 13) multiplying by mmi: 10 should solve j ≡ 7 (mod 13) Solved j ≡ 7 (mod 13) As equation j = ((13 * k) + 7) After substitution x = (17 * ((13 * k) + 7)) After simplification x = (17 * (7 + (13 * k)))`

Okay, okay, there's a wrinkle - we don't know how to distribute yet. Well, let's try it!

Rust code

implExpr{fndistribute(&self)->Self{ifletSelf::Mul(items)=self{iflet[Self::Literal(lit),Self::Add(add_terms)]=&items[..]{returnSelf::Add(add_terms.iter().map(|ex| ex.mul(Self::Literal(*lit))).collect(),);} }self.clone()} }

Rust code

println!("After substitution");letx = x.replace(j);println!("x = {:?}", x);// 👇 new!println!("After distribution");letx = x.distribute();println!("x = {:?}", x);println!("After simplification");letx = x.reduce();println!("x = {:?}", x);

Shell session`$ cargo run --quiet (some lines omitted) As equation j = ((13 * k) + 7) After substitution x = (17 * ((13 * k) + 7)) After distribution x = ((17 * 13 * k) + (17 * 7)) After simplification x = (119 + (221 * k))`

Alright! Now we can keep going:

Rust code

// in main:println!("Third congruence");println!("{:?}", con3);letcon3 = con3.replace(x);println!("After substitution");println!("{:?}", con3);letcon3 = con3.solve().unwrap();println!("Solved");println!("{:?}", con3);

Shell session`Third congruence x ≡ 3 (mod 19) After substitution (119 + (221 * k)) ≡ 3 (mod 19) should solve (119 + (221 * k)) ≡ 3 (mod 19) thread 'main' panicked at 'called `Result::unwrap()` on an `Err` value: CantSolve((119 + (221 * k)) ≡ 3 (mod 19))', src/main.rs:535:31 note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace`

Ah, we don't know how to solve that yet. Well that should be easy! If the left-hand-side is an addition, and one of the term is a literal, just subtract it from both sides:

Rust code

implLinearCongruence{fnsolve(&self)->Result<Self,CantSolve>{eprintln!("should solve {:?}",self);ifletExpr::Mul(items)=&self.lhs{iflet[Expr::Literal(lit),Expr::Var(_)]= items[..]{letmmi =modular_multiplicative_inverse(lit,self.modulo);eprintln!("multiplying by mmi: {}", mmi);returnself.mul(Expr::Literal(mmi)).solve();} }// 👇 new!ifletExpr::Add(items)=&self.lhs{ifletSome(lit)= items.iter().find_map(|expr|matchexpr {Expr::Literal(lit)=> Some(lit), _ => None, }){eprintln!("adding {} on both sides", -lit);returnself.add(Expr::Literal(-lit)).solve();} }ifletExpr::Var(_)=&self.lhs{// already solved!returnOk(self.clone());} Err(CantSolve(self.clone()))} }

Shell session`Third congruence x ≡ 3 (mod 19) After substitution (119 + (221 * k)) ≡ 3 (mod 19) should solve (119 + (221 * k)) ≡ 3 (mod 19) adding -119 on both sides should solve (12 * k) ≡ 17 (mod 19) multiplying by mmi: 8 should solve k ≡ 3 (mod 19) Solved k ≡ 3 (mod 19)`

Now for the grand finale:

Rust code

println!("As equation");letk = con3.expr('l');println!("After substitution");letx = x.replace(k);println!("x = {:?}", x);println!("After distribution");letx = x.distribute();println!("x = {:?}", x);println!("After simplification");letx = x.reduce();println!("x = {:?}", x);

Shell session`Solved k ≡ 3 (mod 19) As equation After substitution x = (119 + (221 * ((19 * l) + 3))) After distribution x = (119 + (221 * ((19 * l) + 3))) After simplification x = (119 + (221 * (3 + (19 * l))))`

Oh, we were a bit too quick with our `Expr::distribute`

method, let's revise it:

Rust code

implExpr{fndistribute(&self)->Self{ifletSelf::Mul(items)=self{iflet[Self::Literal(lit),Self::Add(add_terms)]=&items[..]{returnSelf::Add(add_terms.iter().map(|ex| ex.mul(Self::Literal(*lit))).collect(),);} }// 👇 new!ifletSelf::Add(items)=self{returnSelf::Add(items.iter().map(|ex| ex.distribute()).collect());}self.clone()} }

Much like the rest of our methods, it won't work for all expressions, but we just need it to work for the expressions we actually have, so it should bring us a bit further:

Shell session`Solved k ≡ 3 (mod 19) As equation After substitution x = (119 + (221 * ((19 * l) + 3))) After distribution x = (119 + ((221 * 19 * l) + (221 * 3))) After simplification x = (119 + (663 + (4199 * l)))`

Mhhh better, but still not quite there - we need a way to turn `Add(x, Add(y, z))`

into `Add(x, y, z)`

.

Rust code

implExpr{fnreduce(&self)->Expr{matchself{&Expr::Literal(lit)=>Expr::Literal(lit),&Expr::Var(c)=>Expr::Var(c),Expr::Add(items)=> {// 👇 new!ifletSome((index, nested_items))= items.iter().enumerate().find_map(|(index, item)|matchitem {Expr::Add(terms)=> Some((index, terms)), _ => None, }){returnExpr::Add(items.iter().enumerate().filter(|&(i, _)| i != index).map(|(_, item)| item).chain(nested_items).cloned().collect(),).reduce();}// (the rest is as before)}// other arms omitted} } }

And with that change, we get the following output:

Shell session`$ cargo run --quiet First congruence x ≡ 0 (mod 17) x = ((17 * j) + 0) After simplification x = (17 * j) Second congruence x ≡ 2 (mod 13) After substitution (17 * j) ≡ 2 (mod 13) should solve (17 * j) ≡ 2 (mod 13) multiplying by mmi: 10 should solve j ≡ 7 (mod 13) Solved j ≡ 7 (mod 13) As equation j = ((13 * k) + 7) After substitution x = (17 * ((13 * k) + 7)) After distribution x = ((17 * 13 * k) + (17 * 7)) After simplification x = (119 + (221 * k)) Third congruence x ≡ 3 (mod 19) After substitution (119 + (221 * k)) ≡ 3 (mod 19) should solve (119 + (221 * k)) ≡ 3 (mod 19) adding -119 on both sides should solve (12 * k) ≡ 17 (mod 19) multiplying by mmi: 8 should solve k ≡ 3 (mod 19) Solved k ≡ 3 (mod 19) As equation After substitution x = (119 + (221 * ((19 * l) + 3))) After distribution x = (119 + ((221 * 19 * l) + (221 * 3))) After simplification x = (782 + (4199 * l))`

Which means the first solution is $x = 782$, and indeed, we have:

$\begin{aligned} 782 \bmod 17 &= 0 \ 782 \bmod 13 &= 2 \ 782 \bmod 19 &= 3 \ \end{aligned}$

..but the advent of code example says otherwise:

The earliest timestamp that matches the list 17,x,13,19 is 3417.

So we clearly went wrong somewhere.

But before we dig into that, let's try and automate the whole process.

Ideally, we'd like a function that can take a `Vec<LinearCongruence>`

and
can solve the *whole thing*:

Rust code

fnsolve_lincon_system(cons:Vec<LinearCongruence>)->i64{println!("Solving system of {} linear congruences", cons.len());// Variable namingletmutcurr_var =b'a';letmutnext_var = || ->char{letres = curr_varaschar;curr_var +=1;res };letmutcons = cons.iter();letcon = cons.next().unwrap();println!("👉 {:?}", con);letmutx = con.expr(next_var()).reduce();println!("x = {:?}", x);forconincons {println!("👉 {:?}", con);x = x.replace(con.replace(x.clone()).solve().unwrap().expr(next_var())).distribute().reduce();println!("x = {:?}", x);}letx = x.replace(Expr::Literal(0)).reduce();ifletExpr::Literal(lit)= x { lit }else{panic!("expected `x` to be a literal but got {:?}", x)} }

With that, our whole `main`

function simply becomes:

Rust code

fnmain(){letcon1 =LinearCongruence{lhs:Expr::Var('x'),rhs:Expr::Literal(0),modulo:17, };letcon2 =LinearCongruence{lhs:Expr::Var('x'),rhs:Expr::Literal(2),modulo:13, };letcon3 =LinearCongruence{lhs:Expr::Var('x'),rhs:Expr::Literal(3),modulo:19, };println!("✅ Solution: {}", solve_lincon_system(vec![con1, con2, con3]));}

And we get:

Shell session`$ cargo run --quiet Solving system of 3 linear congruences 👉 x ≡ 0 (mod 17) x = (17 * a) 👉 x ≡ 2 (mod 13) should solve (17 * a) ≡ 2 (mod 13) multiplying by mmi: 10 should solve a ≡ 7 (mod 13) x = (119 + (221 * b)) 👉 x ≡ 3 (mod 19) should solve (119 + (221 * b)) ≡ 3 (mod 19) adding -119 on both sides should solve (12 * b) ≡ 17 (mod 19) multiplying by mmi: 8 should solve b ≡ 3 (mod 19) x = (782 + (4199 * c)) ✅ Solution: 782`

Not gonna lie, that's super cool. It's a bit... odd, that going to such lengths is required to solve that problem, but uhh it's really really cool to have the steps printed out like that.

Yes... odd indeed.

We can even go one step further - taking the input, parsing it, generating a system of linear congruences, and solving it.

First off, we can change our `solve_lincon_system`

to simply take an
`Iterator`

:

Rust code

fnsolve_lincon_system<I>(mutcons:I)->i64whereI:Iterator<Item=LinearCongruence>, {// (same code, with the first `println!` omitted, because it called `.len()`)}

If we still wanted to call it manually, we'd do this:

Rust code

fnmain(){// omitted: let con1, con2, con3println!("✅ Solution: {}",// new: we call into_iter 👇solve_lincon_system(vec![con1, con2, con3].into_iter()));}

But we don't! We want to call it from `ProblemStatement::solve`

, where we do
have an `Iterator`

, because we `map`

from `ProblemStatement::buses`

:

I can't believe you've found a way to make this about iterators again.

😎

Rust code

implProblemStatement{fnsolve(&self)->i64{solve_lincon_system(self.buses.iter().map(|bus|LinearCongruence{lhs:Expr::Var('x'),rhs:Expr::Literal(bus.time_offsetas_),modulo: bus.idas_, }))} }

Now our main becomes:

Rust code

fnmain(){println!("✅ Solution: {}", ProblemStatement::parse("0\n17,x,13,19").solve());}

And still gives the same solution:

Shell session`$ cargo run --quiet 👉 x ≡ 0 (mod 17) x = (17 * a) 👉 x ≡ 2 (mod 13) should solve (17 * a) ≡ 2 (mod 13) multiplying by mmi: 10 should solve a ≡ 7 (mod 13) x = (119 + (221 * b)) 👉 x ≡ 3 (mod 19) should solve (119 + (221 * b)) ≡ 3 (mod 19) adding -119 on both sides should solve (12 * b) ≡ 17 (mod 19) multiplying by mmi: 8 should solve b ≡ 3 (mod 19) x = (782 + (4199 * c)) ✅ Solution: 782`

But as mentioned.. that's not the solution the Advent of Code problem statement gives us.

So let's try and think about our timetable again...

This:

$x \equiv 0 \pmod{17}$

Definitely means that Bus 17 leaves at $x$. (And $x + 17$, and $x + 2 \cdot 17$, etc.)

But what does this mean?

$x \equiv 2 \pmod{13}$

Does it really mean that Bus 13 leaves in 2 minutes?

Ohhhhhhhhhhhhhhhhhhhh. OHHHHHHH! That's not what it means at all!

Correct!

What it actually means is that Bus 13 *left 2 minutes ago*. The problem we've
been solving — for quite a few minutes now — is: what's the timestamp `x`

where:

- Bus 17 leaves
- Bus 13 has left 2 minutes prior
- Bus 19 has left 3 minutes prior

If we want to find a timestamp where Bus 13 leaves 2 minutes *after*, we need
this instead:

$\begin{aligned} x &\equiv 13 - 2 \pmod{13} \ x &\equiv 11 \pmod{13} \ \end{aligned}$

That's an easy fix!

Rust code

implProblemStatement{fnsolve(&self)->i64{solve_lincon_system(self.buses.iter().map(|bus|LinearCongruence{lhs:Expr::Var('x'),// 👇👇👇rhs:Expr::Literal((bus.idasi64- bus.time_offsetasi64).rem_euclid(bus.idas_)),modulo: bus.idas_, }))} }

Let's try it 🤞:

Shell session`$ cargo run --quiet 👉 x ≡ 0 (mod 17) x = (17 * a) 👉 x ≡ 11 (mod 13) should solve (17 * a) ≡ 11 (mod 13) multiplying by mmi: 10 should solve a ≡ 6 (mod 13) x = (102 + (221 * b)) 👉 x ≡ 16 (mod 19) should solve (102 + (221 * b)) ≡ 16 (mod 19) adding -102 on both sides should solve (12 * b) ≡ 9 (mod 19) multiplying by mmi: 8 should solve b ≡ 15 (mod 19) x = (3417 + (4199 * c))`

Hurray! 🎉🎉🎉

Finally!

Wait, didn't we have tests?

Oh right — the tests.

Those tests:

Rust code

#[test]fntest_solutions(){macro_rules!test {($list: literal, $solution: expr)=> { assert_eq!(ProblemStatement::parse(concat!("0\n", $list,"\n")).solve(), $solution)};}test!("17,x,13,19",3417);test!("67,7,59,61",754018);test!("67,x,7,59,61",779210);test!("67,7,x,59,61",1261476);test!("1789,37,47,1889",1202161486);}

Well, if we didn't mess anything up... those should still work, right?
They just use `ProblemStatement::solve`

, which now uses our fancy math.

Shell session`$ cargo t -q running 2 tests .. test result: ok. 2 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out`

They do!

So now, if we just use the proper puzzle input...

Rust code

fnmain(){println!("✅ Solution: {}", ProblemStatement::parse(include_str!("input.txt")).solve());}

Shell session`$ cargo run --quiet 👉 x ≡ 0 (mod 19) x = (19 * a) 👉 x ≡ 24 (mod 37) should solve (19 * a) ≡ 24 (mod 37) multiplying by mmi: 2 should solve a ≡ 11 (mod 37) x = (209 + (703 * b)) 👉 x ≡ 364 (mod 383) should solve (209 + (703 * b)) ≡ 364 (mod 383) adding -209 on both sides should solve (320 * b) ≡ 155 (mod 383) multiplying by mmi: 231 should solve b ≡ 186 (mod 383) x = (130967 + (269249 * c)) 👉 x ≡ 19 (mod 23) should solve (130967 + (269249 * c)) ≡ 19 (mod 23) adding -130967 on both sides should solve (11 * c) ≡ 14 (mod 23) multiplying by mmi: 21 should solve c ≡ 18 (mod 23) x = (4977449 + (6192727 * d)) 👉 x ≡ 7 (mod 13) should solve (4977449 + (6192727 * d)) ≡ 7 (mod 13) adding -4977449 on both sides should solve (8 * d) ≡ 11 (mod 13) multiplying by mmi: 5 should solve d ≡ 3 (mod 13) x = (23555630 + (80505451 * e)) 👉 x ≡ 10 (mod 29) should solve (23555630 + (80505451 * e)) ≡ 10 (mod 29) adding -23555630 on both sides should solve e ≡ 7 (mod 29) x = (587093787 + (2334658079 * f)) 👉 x ≡ 407 (mod 457) should solve (587093787 + (2334658079 * f)) ≡ 407 (mod 457) adding -587093787 on both sides should solve (2 * f) ≡ 353 (mod 457) multiplying by mmi: 229 should solve f ≡ 405 (mod 457) x = (946123615782 + (1066938742103 * g)) 👉 x ≡ 22 (mod 41) should solve (946123615782 + (1066938742103 * g)) ≡ 22 (mod 41) adding -946123615782 on both sides should solve (35 * g) ≡ 31 (mod 41) multiplying by mmi: 34 should solve g ≡ 29 (mod 41) x = (31887347136769 + (43744488426223 * h)) 👉 x ≡ 1 (mod 17) should solve (31887347136769 + (43744488426223 * h)) ≡ 1 (mod 17) adding -31887347136769 on both sides should solve (9 * h) ≡ 3 (mod 17) multiplying by mmi: 2 should solve h ≡ 6 (mod 17) x = (294354277694107 + (743656303245791 * i)) ✅ Solution: 294354277694107`

And finally, we have our answer!

But *looks at estimated reading time* did we really need to do all of that?

What a good-looking question.

### The remainder of the Chinese Remainder Theorem

It was only when I was 90% done with this, you gotta give it to me, *amazing*
solution that I went to read about the Chinese Remainder Theorem once more,
and, as it turns out... there's a direct construction method.

If you have a system of linear congruences, like so:

$\left{ \begin{aligned} x &\equiv a_1 \pmod{n_1} \ \vdots \ x &\equiv a_k \pmod{n_k} \ \end{aligned} \right.$

And, if the $n_i$ are pairwise coprime (any two of them are coprime)...

Which they are for us, since they're all primes in the puzzle input!

We then let $N_i = N/n_i$ be the product of all moduli but one.

Because $n_i$ are pairwise coprime, then $N_i$ and $n_i$ are coprime as well.

From there, Bézout's identity applies, and we can say with certainty that there exists integers $M_i$ and $m_i$ such that

$M_i N_i + m_i n_i = 1$

Which, expressed as a congruence modulo $n_i$, gives us:

$\begin{aligned} M_i N_i + m_i n_i &\equiv 1 \pmod{n_i} \ M_i N_i &\equiv 1 \pmod{n_i} \ \end{aligned}$

In other words, we simply have $M_i \equiv N_i^{-1} \pmod{n_i}$.

A solution of the system of congruences is:

$x = \sum_{i=1}^k a_i M_i N_i$

Which is the sum, for all $i$, of the remainder $a_i$, multiplied by $N_i$, which is the product of all $n_j$ except for $j = i$, and again multiplied by $M_i$, which we've just established is the modular multiplicative inverse of $N_i \pmod{n_i}$.

Mhhh we can cook with that.

Can we? Let's find out!

Rust code

fnsolve_lincong_system_direct<I>(congs:I)->i64whereI:Iterator<Item=LinearCongruence>, {// This time, we need to be able to index our linear congruencesletcongs:Vec<_>= congs.collect();fnremainder(lc:&LinearCongruence)->i64{match&lc.rhs{Expr::Literal(lit)=>*lit, _ =>panic!(), } }(0..congs.len()).map(|i| {leta_i =remainder(&congs[i]);letN_i = congs.iter().enumerate().filter(|&(j, _)| j != i).map(|(_, con)| con.moduloasi64).product();letM_i =modular_multiplicative_inverse(N_i, congs[i].modulo);a_i*N_i*M_i }).sum()}

Let's... give it a shot? If we use `solve_lincong_system_direct`

in
`ProblemStatement::solve`

... our tests stop passing:

Shell session`$ cargo t -q running 2 tests .F failures: ---- test_solutions stdout ---- thread 'test_solutions' panicked at 'assertion failed: `(left == right)` left: `49606`, right: `3417`', src/main.rs:113:5 note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace`

Ah. We should've found ${3417}$ but we found ${49606}$.

Well, is ${49606}$ even a solution?

The linear congruence system for the first test was:

$\left{ \begin{aligned} x &\equiv 0 \pmod {17} \ x &\equiv 11 \pmod {13} \ x &\equiv 16 \pmod {19} \ \end{aligned} \right.$

And we have:

$\begin{aligned} 49606 \bmod {17} &= 0 \ 49606 \bmod {13} &= 11 \ 49606 \bmod {19} &= 16 \ \end{aligned}$

So yes, it is a solution! Just not the *first* solution. In fact, the last
step we found when solving the example gave us *all the solution*, in the
following form:

$x = 3417 + 4199c$

So we can figure out what the value of $c$ is!

$\begin{aligned} 49606 &= 3417 + 4199c \ 46189 &= 4199c \ c &= \frac{46189}{4199} \ c &= 11 \ \end{aligned}$

So the solution we found was ${3417 + 4199 \cdot 11}$.

So uhh... can we get the *first* solution using this direct construction
method?

I don't know. Someone else might know, but I sure don't.

So, had I pursued this solution first, I would've been stuck! Plus,
isn't it a lot more fun to write functions like `distribute`

, `replace`

,
`reduce`

, and `solve`

?

It sure is! Also, I'm fairly sure all those multiplications and additions could end up giving us pretty larger numbers. At least with our solution our numbers stay nice and small.

So we're in agreement, our solution was the only reasonable solution?

Yup. Let's not look at any other solutions, ever.

Until next time, take care, and happy winter holidays!

This article was made possible thanks to my patrons: Alexander Payne, Fredrik Østrem, David Barsky, Yufan Lou, Stephen Molyneaux, Barret Rennie, Thomas Corbin, MW, Jacob Cheriathundam, Michael Watzko, Embark Studios, Eugene Bulkin, Marcus Griep, Petar Radosevic, Tool Army, Tully, Santiago Lema, Spencer Gilbert, Jörn Huxhorn, Garrett Ward, DEX, Christian Oudard, Ronen Cohen, Thor Kamphefner, Kamran Khan, Cole Kurkowski, Arjen Laarhoven, Vicente Bosch, Chirag Jain, Ville Mattila, Marie Janssen, Vladyslav Batyrenko, Cameron Clausen, spike grobstein, Jon Gjengset, Paul Marques Mota, Jakub Fijałkowski, Mitchell Hamilton, Brad Luyster, Max von Forell, Jake S, Dimitri Merejkowsky, Chris Biscardi, René Ribaud, Alex Doroshenko, Vincent, Steven McGuire, Chad Birch, Chris Emery, Bob Ippolito, John Van Enk, metabaron, Isak Sunde Singh, Philipp Gniewosz, Mads Johansen, lukvol, Ives van Hoorne, Jan De Landtsheer, Daniel Strittmatter, Evgeniy Dubovskoy, Alex Rudy, Shane Lillie, Romet Tagobert, Douglas Creager, Corey Alexander, Molly Howell, knutwalker, Zachary Dremann, Sebastian Ziebell, Julien Roncaglia, Amber Kowalski, T, queenfartbutt, Paul Kline, Kristoffer Ström, Astrid Bek, Yoh Deadfall, Justin Ossevoort, Tomáš Duda, Jeremy Banks, Rasmus Larsen, Torben Clasen, C J Silverio, Walther, Pete Bevin, Shane Sveller, Clara Schultz, jer, Wonwoo Choi, Hawken Rives, João Veiga, Richard Pringle, Adam Perry, Benjamin Röjder Delnavaz, Matt Jadczak, Jonathan Knapp, Maximilian, Seth Stadick, brianloveswords, Sean Bryant, Ember, Sebastian Zimmer, Makoto Nakashima, Geoff Cant, Geoffroy Couprie, Michael Alyn Miller, o0Ignition0o, Zaki, Raphael Gaschignard, Romain Ruetschi, Ignacio Vergara, Pascal, Jane Lusby, Nicolas Goy, Ted Mielczarek, Aurora.

This article is part 13 of the Advent of Code 2020 series.

If you liked this article, please support my work on Patreon!