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)] struct ProblemStatement { departure_time: usize, buses: Vec<usize>, } #[derive(Debug)] struct WaitTime { bus_id: usize, /// in minutes wait: usize, }

Then a quick parser:

Rust code
impl ProblemStatement { fn parse(input: &str) -> Self { let mut lines = 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
939 7,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:

departure_time % bus_id gives us the distance between our earliest departure and the last departure of bus_id

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:

bus_id - departure_time % bus_id gives us the distance betweeen our earliest departure and the next departure of bus_id

That seems easy to implement!

Yup! We already have a type for it!

Rust code
fn main() { let stat = ProblemStatement::parse(include_str!("input.txt")); let times: 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
fn main() { let stat = ProblemStatement::parse(include_str!("input.txt")); let answer = stat .buses .iter() .map(|&bus_id| WaitTime { bus_id, wait: bus_id - stat.departure_time % bus_id, }) .min_by_key(|wt| wt.wait); match answer { 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:

And we should find a timestamp t such that:

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)] struct ProblemStatement { departure_time: usize, buses: Vec<Bus>, } #[derive(Debug)] struct Bus { id: usize, time_offset: usize, } impl ProblemStatement { fn parse(input: &str) -> Self { let mut lines = 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(), } } } fn main() { let stat = 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
fn main() { let stat = ProblemStatement::parse(include_str!("input.txt")); use itertools::Itertools; stat.buses .iter() .tuple_windows() .for_each(|(earlier, later)| { let offset_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
struct WrongGap<'a> { earlier: &'a Bus, later: &'a Bus, offset_gap: usize, actual_gap: usize, } impl fmt::Debug for WrongGap<'_> { fn fmt(&self, f: &mut fmt::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 ) } } impl fmt::Display for WrongGap<'_> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { fmt::Debug::fmt(self, f) } } impl std::error::Error for WrongGap<'_> {}

And now let's use it:

Rust code
fn main() { let stat = ProblemStatement::parse(include_str!("input.txt")); use itertools::Itertools; let solution = 1068781_usize; let ok = stat.buses.iter().tuple_windows().fold( Ok::<_, WrongGap>(solution), |acc, (earlier, later)| { let earlier_timestamp = acc?; let later_timestamp = earlier_timestamp + later.id - (earlier_timestamp % later.id); let offset_gap = later.time_offset - earlier.time_offset; let actual_gap = later_timestamp - earlier_timestamp; if offset_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 Bus 13 to leave 7 minutes after Bus 1 (which left at 256), but it left 4 minutes 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
impl ProblemStatement { fn check_solution(&self, solution: usize) -> Result<(), WrongGap<'_>> { use itertools::Itertools; self.buses .iter() .tuple_windows() .fold(Ok::<_, WrongGap>(solution), |acc, (earlier, later)| { // 👇 here's the only debug print we need dbg!(&acc); let earlier_timestamp = acc?; let later_timestamp = earlier_timestamp + later.id - (earlier_timestamp % later.id); let offset_gap = later.time_offset - earlier.time_offset; let actual_gap = later_timestamp - earlier_timestamp; if offset_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
fn main() { let stat = 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
impl ProblemStatement { fn check_solution(&self, solution: usize) -> Result<(), WrongGap<'_>> { use itertools::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); let earlier_timestamp = acc; let later_timestamp = earlier_timestamp + later.id - (earlier_timestamp % later.id); let offset_gap = later.time_offset - earlier.time_offset; let actual_gap = later_timestamp - earlier_timestamp; // 👇 we still return a `Result` though! if offset_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
impl ProblemStatement { fn solve(&self) -> usize { let first_bus = self.buses.first().unwrap(); itertools::iterate(0, |&i| i + first_bus.id) .find(|&timestamp| 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
fn main() { let stat = ProblemStatement::parse(include_str!("input.txt")); dbg!(&stat.solve()); }
Cool bear's hot tip

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] fn test_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:

{x≡2(mod3)x≡1(mod5)x≡5(mod7) \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≡2(mod3)x \equiv 2 \pmod 3 means "the remainder of euclidean division of xx by 3 must be 2" — this is true for a bunch of values of xx!

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

And this is true for any value of jj:

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

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

And there's four unknowns (xx, jj, kk, and ll) 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:

{x≡5(mod7)x≡1(mod5)x≡2(mod3) \left{ \begin{aligned} x &\equiv 5 \pmod 7 \ x &\equiv 1 \pmod 5 \ x &\equiv 2 \pmod 3 \ \end{aligned} \right.

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

x=7j+5 x = 7j + 5

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

x≡1(mod5)7j+5≡1(mod5) \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 jj.

At first we'd have:

7j+5=1 7j + 5 = 1

Then we'd subtract 5 on both sides:

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

Then divide by 7 on both sides:

7j7=−47j=−47 \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{7j + 5 = 1}, well, both the left-hand side (7j+5{7j + 5}) and the right-hand-side (1{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{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{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{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{j} is not an integer. If we divide both sides by 7, we land between two integers (−1{-1} and 0{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{-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 mod 8=6 mod 8=14 mod 8 -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:

−2 mod 8=66 mod 8=614 mod 8=6 \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≡3(mod8) x \equiv 3 \pmod 8

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

If that's our only constraint, as we've seen, x{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≡1(mod5){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.

x0=1x1=xx2=x⋅xx3=x⋅x⋅x… \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 1x{\frac{1}{x}}. So we can complete our little list so that it's nice and symmetric:

…x−3=1x⋅x⋅xx−2=1x⋅xx−1=1xx0=1x1=xx2=x⋅xx3=x⋅x⋅x… \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:

For example, we have:

axay=ax+yaxay=ax−y \begin{aligned} a^x a^y &= a^{x+y} \ \frac{a^x}{a^y} &= a^{x-y} \ \end{aligned}

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

1x=x0x1=x0−1=x−1 \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:

xy=x(1y)=xy−1 \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:

ax≡b(modm)iax≡ib(modm) \begin{aligned} ax &\equiv b \pmod m \ iax &\equiv ib \pmod m \ \end{aligned}

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

x≡ib(modm) x \equiv ib \pmod m

We just got rid of a! Ahhhhh!!!

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

ax≡b(modm)a−1ax≡a−1b(modm)x≡a−1b(modm) \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{a}, modulo m{m}?

Cool bear's hot tip

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{21} and 33{33} have a GCD{GCD} of 3{3} - it's the largest number by which they can both be divided.

GCD(21,33)=3213=7333=11 \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:

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

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

What's a prime number again?

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

So 1 is not a prime number?

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

Furthermore, if the GCD{GCD} of two numbers is 1{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:

21⋅112=24231⋅72=147 \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{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{L} is the larger number, and l{l} is the smaller number, then the idea is to write down this:

L=al+b L = al + b

aa and bb are easy to find - bb is the remainder of the integer division of LL by ll, and aa is well, the result of the integer division of LL by ll.

Then we keep going - trying to divide ll by bb, and so on and so forth.

Uhhh can we have an example?

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

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

Extended euclidean algorithm

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

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

Cool bear's hot tip

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

And we can find xx and yy by manipulating the equalities we got when following the Euclidean algorithm a little:

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

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

a≡b(modm) a \equiv b \pmod m

Then if aa and mm are coprime, their GCD is 1.

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

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

Becomes:

ax+my=1 ax + my = 1

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

ax+my≡1(modm) ax + my \equiv 1 \pmod m

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

ax+0⋅y≡1(modm)ax≡1(modm) \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{7} and 5{5}, in 7j≡1(mod5){7j \equiv 1 \pmod 5}, let's run through the whole thing again.

First, the Euclidean Algorithm:

7=1⋅5+25=2⋅2+12=2⋅1+0 \begin{aligned} 7 &= 1 \cdot 5 + 2 \ 5 &= 2 \cdot 2 + 1 \ 2 &= 2 \cdot 1 + 0 \ \end{aligned}

Then the Extended Euclidean algorithm:

1=5−2⋅21=5−2(7−5)1=3⋅5−2⋅7 \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(mod5){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 mod 5=3{-2 \bmod 5 = 3}, so 3{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:

7j≡1(mod5)7−1⋅7j≡7−1⋅1(mod5)j≡3⋅1(mod5)j≡3(mod5) \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 aa modulo mm exists, if aa and mm are coprime. For 7j≡1(mod5){7j \equiv 1 \pmod 5}, it's definitely the case: both 7{7} and 5{5} are prime.

In that case, we have:

aϕ(m)≡1(modm) a^{\phi(m)} \equiv 1 \pmod m

And:

aϕ(m)−1≡a−1(modm) a^{\phi(m)-1} \equiv a^{-1} \pmod m

Where phi (ϕ) is Euler's totient function.

Euler's what know?

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

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

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

aϕ(m)−1≡a−1(modm) a^{\phi(m)-1} \equiv a^{-1} \pmod m

Becomes:

a(m−1)−1≡a−1(modm) a^{(m-1)-1} \equiv a^{-1} \pmod m

Which reduces to:

am−2≡a−1(modm) a^{m-2} \equiv a^{-1} \pmod m

Using this, we can find 7−1(mod5){7^{-1} \pmod 5}:

7−1≡75−2(mod5)7−1≡73(mod5)7−1≡343(mod5)(343 mod 5=3)7−1≡3(mod5) \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{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≡2(mod457) 13j \equiv 2 \pmod{457}

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

13−1≡13457−2(mod457)13−1≡13455(mod457) \begin{aligned} 13^{-1} &\equiv 13^{457-2} \pmod{457} \ 13^{-1} &\equiv 13^{455} \pmod{457} \ \end{aligned}

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

Huge.

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

Rust code
fn main() { 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
use num_bigint::BigUint; fn main() { let a: 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? 13455{13^{455}} is just:

13455=13⋅13⋅13…13⋅13 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:

132≡13⋅13≡169(mod457)133≡132⋅13≡169⋅13≡2197≡369(mod457)134≡133⋅13≡369⋅13≡4797≡227(mod457)… \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
fn main() { let a = 13_u64; let m = 457_u64; let mut a_mmi = 1; for _ in 1..=(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
fn main() { dbg!(modular_multiplicative_inverse(13, 457)); } /// Finds the modular multiplicative inverse of `a` modulo `m` /// Returns the wrong result if `m` isn't prime. fn modular_multiplicative_inverse(a: i64, m: u32) -> i64 { modular_pow(a, m - 2, m as _) } fn modular_pow(x: i64, exp: u32, modulo: i64) -> i64 { (match x.checked_pow(exp) { Some(x) => x, None => { let exp_a = exp / 2; let exp_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.

Cool bear's hot tip

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:

{x≡5(mod7)x≡1(mod5)x≡2(mod3) \left{ \begin{aligned} x &\equiv 5 \pmod 7 \ x &\equiv 1 \pmod 5 \ x &\equiv 2 \pmod 3 \ \end{aligned} \right.

We rewrote xx as:

x=7j+5 x = 7j + 5

Then substituted x in the second linear congruence:

x≡1(mod5)7j+5≡1(mod5)7j≡1−5≡1(mod5) \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≡3(mod5){j \equiv 3 \pmod 5}.

Rewriting this as an expression, we get:

j=5k+3 j = 5k + 3

Then we substitute j:

x=7j+5x=7(5k+3)+5x=35k+7⋅3+5x=35k+26 \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:

x≡2(mod3)35k+26≡2(mod3) \begin{aligned} x &\equiv 2 \pmod 3 \ 35k + 26 &\equiv 2 \pmod 3 \ \end{aligned}

And solve it:

35k≡(2−26)≡−24≡0(mod3)35k≡0(mod3) \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≡0(mod3) k \equiv 0 \pmod 3

Then express k:

k=3l k = 3l

Substitute k in our last expression for x:

x=35k+26x=35(3l)+26x=105l+26 \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:

x≡5(mod7)x≡1(mod5)x≡2(mod3) \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:

{x≡0(mod17)x≡2(mod13)x≡3(mod19) \left{ \begin{aligned} x &\equiv 0 \pmod{17} \ x &\equiv 2 \pmod{13} \ x &\equiv 3 \pmod{19} \ \end{aligned} \right.

Cool bear's hot tip

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 x = 17j

We can then replace it in the second congruence:

x≡2(mod13)17j≡2(mod13) \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)] enum Expr { 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
impl Expr { fn reduce(&self) -> Expr { match self { &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(_))); if literals.is_empty() && others.is_empty() { Expr::Literal(0) } else { let mut terms = others; let sum = literals .into_iter() .map(|x| { if let Expr::Literal(x) = x { x } else { unreachable!() } }) .sum(); if sum != 0 { if terms.is_empty() { return Self::Literal(sum); } else { terms.insert(0, Self::Literal(sum)); } } if terms.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(_))); if literals.is_empty() && others.is_empty() { Expr::Literal(1) } else { let mut terms = others; let product = literals .into_iter() .map(|x| { if let Expr::Literal(x) = x { x } else { unreachable!() } }) .product(); if product != 1 { if terms.is_empty() { return Self::Literal(product); } else { terms.insert(0, Self::Literal(product)); } } if terms.len() == 1 { terms.pop().unwrap() } else { Expr::Mul(terms) } } } } } }

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

Rust code
#[test] fn test_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)] struct LinearCongruence { lhs: Expr, rhs: Expr, modulo: u32, }

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

Rust code
fn main() { let lc = 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
impl fmt::Debug for Expr { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { match self { &Expr::Literal(lit) => write!(f, "{}", lit), Expr::Var => write!(f, "x"), Expr::Add(terms) => { write!(f, "(")?; for (i, term) in terms.iter().enumerate() { if i == 0 { write!(f, "{:?}", term)?; } else { write!(f, " + {:?}", term)?; } } write!(f, ")")?; Ok(()) } Expr::Mul(terms) => { write!(f, "(")?; for (i, term) in terms.iter().enumerate() { if i == 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
impl fmt::Debug for LinearCongruence { fn fmt(&self, f: &mut fmt::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)] struct CantSolve(LinearCongruence); impl fmt::Display for CantSolve { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { fmt::Debug::fmt(self, f) } } impl std::error::Error for CantSolve {} impl LinearCongruence { fn solve(&self) -> Result<Self, CantSolve> { if let Expr::Mul(items) = &self.lhs { if let [Expr::Literal(lit), Expr::Var] = items[..] { let mmi = modular_multiplicative_inverse(lit as _, 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
fn main() { let lc = LinearCongruence { lhs: Expr::Mul(vec![Expr::Literal(17), Expr::Var]), rhs: Expr::Literal(2), modulo: 13, }; dbg!(&lc); let lc = 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
impl Expr { /// Multiply `self` by `expr` fn mul(&self, expr: Expr) -> Self { match self { Self::Mul(items) => { Self::Mul(std::iter::once(expr).chain(items.iter().cloned()).collect()) } _ => Self::Mul(vec![expr, self.clone()]), } } } impl LinearCongruence { /// Multiply both sides of congruence by `expr` fn mul(&self, expr: Expr) -> Self { Self { lhs: self.lhs.mul(expr.clone()).reduce(), rhs: self.rhs.mul(expr).reduce(), modulo: self.modulo, } } } impl LinearCongruence { fn solve(&self) -> Result<Self, CantSolve> { eprintln!("should solve {:?}", self); if let Expr::Mul(items) = &self.lhs { if let [Expr::Literal(lit), Expr::Var] = items[..] { let mmi = modular_multiplicative_inverse(lit, self.modulo); eprintln!("multiplying by mmi: {}", mmi); return self.mul(Expr::Literal(mmi)).solve(); } } Err(CantSolve(self.clone())) } } fn main() { let lc = LinearCongruence { lhs: Expr::Mul(vec![Expr::Literal(17), Expr::Var]), rhs: Expr::Literal(2), modulo: 13, }; let lc = 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 mod 13=1{170 \bmod 13 = 1}, but Expr doesn't know we're modulo 13! So, I think we need a second method - modulo:

Rust code
impl Expr { fn modulo(&self, modulo: u32) -> Self { match self { &Self::Literal(lit) => Expr::Literal(lit.rem_euclid(modulo as _)), 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{170x} and end up with 1x{1x}, we want to get rid of that 1{1}.

Let's try it out:

Rust code
impl LinearCongruence { /// Multiply both sides of congruence by `expr` fn mul(&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
impl LinearCongruence { fn solve(&self) -> Result<Self, CantSolve> { eprintln!("should solve {:?}", self); if let Expr::Mul(items) = &self.lhs { if let [Expr::Literal(lit), Expr::Var] = items[..] { let mmi = modular_multiplicative_inverse(lit, self.modulo); eprintln!("multiplying by mmi: {}", mmi); return self.mul(Expr::Literal(mmi)).solve(); } } if let Expr::Var = &self.lhs { // 👇 // already solved! return Ok(self.clone()); } Err(CantSolve(self.clone())) } }
Rust code
$ cargo run --quiet should solve (17 * x) ≡ 2 (mod 13) multiplying by mmi: 10 should solve x ≡ 7 (mod 13) [src/main.rs:378] &lc = x ≡ 7 (mod 13)

Okay! We've solved 17j≡2(mod13){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 jj as an.. expression:

Rust code
impl LinearCongruence { /// 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. fn expr(&self) -> Expr { match (&self.lhs, &self.rhs) { (Expr::Var, &Expr::Literal(remainder)) => Expr::Add(vec![ Expr::Mul(vec![Expr::Literal(self.modulo as _), Expr::Var]), Expr::Literal(remainder), ]), _ => { panic!( "Expected solved congruence (of form `var ≡ literal (mod m)`), but got `{:?}`", self ) } } } }
Rust code
fn main() { let lc = LinearCongruence { lhs: Expr::Mul(vec![Expr::Literal(17), Expr::Var]), rhs: Expr::Literal(2), modulo: 13, }; let lc = lc.solve().unwrap(); dbg!(&lc); // 👇 new! let expr = 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:

From first congruencex≡0(mod17)As an equationx=17j+0=17jFrom second congruencex≡2(mod13)Substitution17j≡2(mod13)After solvingj≡7(mod13)As an equationj=13k+7 \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 jj in x=17j{x = 17j} with 13k+7{13k + 7}.

Let's try and make a method for that:

Rust code
impl Expr { // Replaces `Expr::Var` with `expr` everywhere in that expression fn replace(&self, expr: Expr) -> Self { match self { &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
fn main() { let lc = LinearCongruence { lhs: Expr::Mul(vec![Expr::Literal(17), Expr::Var]), rhs: Expr::Literal(2), modulo: 13, }; let lc = lc.solve().unwrap(); dbg!(&lc); let expr = lc.expr(); dbg!(&expr); let expr = 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)] enum Expr { Literal(i64), Var(char), Add(Vec<Expr>), Mul(Vec<Expr>), }

We'll need to fix up our Debug implementation:

Rust code
impl fmt::Debug for Expr { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { match self { &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
impl LinearCongruence { /// 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. // 👇 fn expr(&self, name: char) -> Expr { match (&self.lhs, &self.rhs) { (Expr::Var(_), &Expr::Literal(remainder)) => Expr::Add(vec![ // 👇 Expr::Mul(vec![Expr::Literal(self.modulo as _), 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
impl LinearCongruence { // Replaces `Expr::Var` with `expr` everywhere in that expression fn replace(&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
fn main() { let con1 = LinearCongruence { lhs: Expr::Var('x'), rhs: Expr::Literal(0), modulo: 17, }; let con2 = LinearCongruence { lhs: Expr::Var('x'), rhs: Expr::Literal(2), modulo: 13, }; let con3 = LinearCongruence { lhs: Expr::Var('x'), rhs: Expr::Literal(3), modulo: 19, }; println!("First congruence"); println!("{:?}", con1); let x = con1.expr('j'); println!("x = {:?}", x); let x = x.reduce(); println!("After simplification"); println!("x = {:?}", x); println!("Second congruence"); println!("{:?}", con2); let con2 = con2.replace(x.clone()); println!("After substitution"); println!("{:?}", con2); let con2 = con2.solve().unwrap(); println!("Solved"); println!("{:?}", con2); println!("As equation"); let j = con2.expr('k'); println!("j = {:?}", j); println!("After substitution"); let x = x.replace(j); println!("x = {:?}", x); println!("After simplification"); let x = 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
impl Expr { fn distribute(&self) -> Self { if let Self::Mul(items) = self { if let [Self::Literal(lit), Self::Add(add_terms)] = &items[..] { return Self::Add( add_terms .iter() .map(|ex| ex.mul(Self::Literal(*lit))) .collect(), ); } } self.clone() } }
Rust code
println!("After substitution"); let x = x.replace(j); println!("x = {:?}", x); // 👇 new! println!("After distribution"); let x = x.distribute(); println!("x = {:?}", x); println!("After simplification"); let x = 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); let con3 = con3.replace(x); println!("After substitution"); println!("{:?}", con3); let con3 = 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
impl LinearCongruence { fn solve(&self) -> Result<Self, CantSolve> { eprintln!("should solve {:?}", self); if let Expr::Mul(items) = &self.lhs { if let [Expr::Literal(lit), Expr::Var(_)] = items[..] { let mmi = modular_multiplicative_inverse(lit, self.modulo); eprintln!("multiplying by mmi: {}", mmi); return self.mul(Expr::Literal(mmi)).solve(); } } // 👇 new! if let Expr::Add(items) = &self.lhs { if let Some(lit) = items.iter().find_map(|expr| match expr { Expr::Literal(lit) => Some(lit), _ => None, }) { eprintln!("adding {} on both sides", -lit); return self.add(Expr::Literal(-lit)).solve(); } } if let Expr::Var(_) = &self.lhs { // already solved! return Ok(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"); let k = con3.expr('l'); println!("After substitution"); let x = x.replace(k); println!("x = {:?}", x); println!("After distribution"); let x = x.distribute(); println!("x = {:?}", x); println!("After simplification"); let x = 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
impl Expr { fn distribute(&self) -> Self { if let Self::Mul(items) = self { if let [Self::Literal(lit), Self::Add(add_terms)] = &items[..] { return Self::Add( add_terms .iter() .map(|ex| ex.mul(Self::Literal(*lit))) .collect(), ); } } // 👇 new! if let Self::Add(items) = self { return Self::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
impl Expr { fn reduce(&self) -> Expr { match self { &Expr::Literal(lit) => Expr::Literal(lit), &Expr::Var(c) => Expr::Var(c), Expr::Add(items) => { // 👇 new! if let Some((index, nested_items)) = items .iter() .enumerate() .find_map(|(index, item)| match item { Expr::Add(terms) => Some((index, terms)), _ => None, }) { return Expr::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=782x = 782, and indeed, we have:

782 mod 17=0782 mod 13=2782 mod 19=3 \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
fn solve_lincon_system(cons: Vec<LinearCongruence>) -> i64 { println!("Solving system of {} linear congruences", cons.len()); // Variable naming let mut curr_var = b'a'; let mut next_var = || -> char { let res = curr_var as char; curr_var += 1; res }; let mut cons = cons.iter(); let con = cons.next().unwrap(); println!("👉 {:?}", con); let mut x = con.expr(next_var()).reduce(); println!("x = {:?}", x); for con in cons { println!("👉 {:?}", con); x = x .replace(con.replace(x.clone()).solve().unwrap().expr(next_var())) .distribute() .reduce(); println!("x = {:?}", x); } let x = x.replace(Expr::Literal(0)).reduce(); if let Expr::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
fn main() { let con1 = LinearCongruence { lhs: Expr::Var('x'), rhs: Expr::Literal(0), modulo: 17, }; let con2 = LinearCongruence { lhs: Expr::Var('x'), rhs: Expr::Literal(2), modulo: 13, }; let con3 = 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
fn solve_lincon_system<I>(mut cons: I) -> i64 where I: 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
fn main() { // omitted: let con1, con2, con3 println!( "✅ 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
impl ProblemStatement { fn solve(&self) -> i64 { solve_lincon_system(self.buses.iter().map(|bus| LinearCongruence { lhs: Expr::Var('x'), rhs: Expr::Literal(bus.time_offset as _), modulo: bus.id as _, })) } }

Now our main becomes:

Rust code
fn main() { 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≡0(mod17) x \equiv 0 \pmod{17}

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

But what does this mean?

x≡2(mod13) 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:

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

x≡13−2(mod13)x≡11(mod13) \begin{aligned} x &\equiv 13 - 2 \pmod{13} \ x &\equiv 11 \pmod{13} \ \end{aligned}

That's an easy fix!

Rust code
impl ProblemStatement { fn solve(&self) -> i64 { solve_lincon_system(self.buses.iter().map(|bus| LinearCongruence { lhs: Expr::Var('x'), // 👇👇👇 rhs: Expr::Literal((bus.id as i64 - bus.time_offset as i64).rem_euclid(bus.id as _)), modulo: bus.id as _, })) } }

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] fn test_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
fn main() { 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:

{x≡a1(modn1)⋮x≡ak(modnk) \left{ \begin{aligned} x &\equiv a_1 \pmod{n_1} \ \vdots \ x &\equiv a_k \pmod{n_k} \ \end{aligned} \right.

And, if the nin_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 Ni=N/niN_i = N/n_i be the product of all moduli but one.

Because nin_i are pairwise coprime, then NiN_i and nin_i are coprime as well.

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

MiNi+mini=1 M_i N_i + m_i n_i = 1

Which, expressed as a congruence modulo nin_i, gives us:

MiNi+mini≡1(modni)MiNi≡1(modni) \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 Mi≡Ni−1(modni)M_i \equiv N_i^{-1} \pmod{n_i}.

A solution of the system of congruences is:

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

Which is the sum, for all ii, of the remainder aia_i, multiplied by NiN_i, which is the product of all njn_j except for j=ij = i, and again multiplied by MiM_i, which we've just established is the modular multiplicative inverse of Ni(modni)N_i \pmod{n_i}.

Mhhh we can cook with that.

Can we? Let's find out!

Rust code
fn solve_lincong_system_direct<I>(congs: I) -> i64 where I: Iterator<Item = LinearCongruence>, { // This time, we need to be able to index our linear congruences let congs: Vec<_> = congs.collect(); fn remainder(lc: &LinearCongruence) -> i64 { match &lc.rhs { Expr::Literal(lit) => *lit, _ => panic!(), } } (0..congs.len()) .map(|i| { let a_i = remainder(&congs[i]); let N_i = congs .iter() .enumerate() .filter(|&(j, _)| j != i) .map(|(_, con)| con.modulo as i64) .product(); let M_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{3417} but we found 49606{49606}.

Well, is 49606{49606} even a solution?

The linear congruence system for the first test was:

{x≡0(mod17)x≡11(mod13)x≡16(mod19) \left{ \begin{aligned} x &\equiv 0 \pmod {17} \ x &\equiv 11 \pmod {13} \ x &\equiv 16 \pmod {19} \ \end{aligned} \right.

And we have:

49606 mod 17=049606 mod 13=1149606 mod 19=16 \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 x = 3417 + 4199c

So we can figure out what the value of cc is!

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

So the solution we found was 3417+4199⋅11{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: Christian Oudard, Ronen Cohen, Matt Welke, Ivan Towlson, Nathan Lincoln, Daniel Wagner-Hall, Felix Weis, Henrik Sylvester Pedersen, Thor Kamphefner, VALENTIN MARIETTE, Kamran Khan, Cole Kurkowski, Arjen Laarhoven, Jeremy Kaplan, Jon Reynolds, Vicente Bosch, Chirag Jain, Ville Mattila, Marie Janssen, Vladyslav Batyrenko, Cameron Clausen, Pierre Guillaume Herveou, Agam Brahma, spike grobstein, Daniel Franklin, Jon Gjengset, Tex, Nick Thomas, Blaž Tomažič, Johan, Paul Marques Mota, Jakub Fijałkowski, Mitchell Hamilton, Ruben Duque, Brad Luyster, Max von Forell, Jake S, Justin, Dimitri Merejkowsky, Chris Biscardi, mrcowsy, René Ribaud, Alex Doroshenko, Julian, Vincent, Steven McGuire, Jack DeNeut, Chad Birch, Martin-Louis Bright, Chris Emery, Bob Ippolito, Jomer, John Van Enk, metabaron, Isak Sunde Singh, DaVince, Philipp Gniewosz, Richard Hill, Simon Rüegg, Roman Levin, V, Max Fermor, Mads Johansen, lukvol, Ives van Hoorne, Greg Stoll, Jan De Landtsheer, Scott Munro, Михаил Захаркин, Daniel Strittmatter, Evgeniy Dubovskoy, Sandro, Alex Rudy, Jake Rodkin, Shane Lillie, Romet Tagobert, Geekingfrog, Douglas Creager, Corey Alexander, Molly Howell, Jeff Crocker, knutwalker, Zachary Dremann, Olivier Peyrusse, Sebastian Ziebell, Julien Roncaglia, eigentourist, Amber Kowalski, Charlton Eivind Rodda, Jan Schiefer, Edil Kratskih, Chris Emerson, Matthew Campbell, Krasimir Slavkov, Juniper Wilde, Paul Kline, Pascal Hartig, Samir Talwar, TD, Kristoffer Ström, Henning Schmick, Ryan Levick, Antoine Boegli, Astrid Bek, Ryan, Yoh Deadfall, Justin Ossevoort, Jeremy, Tomáš Duda, playest, Meghana Gupta, Sebastian Dröge, Adam, Nick Gerace, Jeremy Banks, Rasmus Larsen, exelotl, Ramnivas Laddad, Yury Mikhaylov, Torben Clasen, Sam Rose, Nickolas Fotopoulos, C J Silverio, Walther, Pete Bevin, Shane Sveller, Marcel Jackwerth, Brian Dawn, Clara Schultz, Robert Cobb, jer, Wonwoo Choi, Hawken Rives, João Veiga, Dave Gauer, David Cornu, Richard Pringle, Adam Perry, Yann Schwartz, Jaseem Abid, Zinahe Asnake, Ryan Blecher, Benjamin Röjder Delnavaz, Grégoire Hubert, Matt Jadczak, Nazar Mokrynskyi, Julian Hofer, Mara Bos, Brandon, Jonathan Knapp, Maximilian, Seth Stadick, brianloveswords, Sean Bryant, Ember, Sebastian Zimmer, Makoto Nakashima, Geert Depuydt, Geoff Cant, Geoffroy Couprie, Michael Alyn Miller, Vengarioth, o0Ignition0o, Zaki, Raphael Gaschignard, Romain Ruetschi, Ignacio Vergara, Pascal, Cassie Jones, Pat Monaghan, Jane Lusby, Nicolas Goy, Suhib Sam Kiswani, Henry Goffin, Ted Mielczarek, Random832, Ryszard Sommefeldt, Jesús Higueras, Aurora.

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

Read the next part

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

Become a Patron

Looking for the homepage?
Another article: Image decay as a service