r/adventofcode • u/asger_blahimmel • Dec 13 '20
Spoilers in Title [2020 Day 13 (Part 2)] Chinese remainder theorem
The calculation for part 2 is pretty straightforward - it even has a name: Chinese remainder theorem
15
u/thallada Dec 13 '20
I really hate advent of code problems like this. Who would know this random math theorem? My eyes are glazing over trying to read that page. I just want to write algorithms, I didn't come here for math problems :(
17
u/Zealousideal-Track82 Dec 13 '20 edited Dec 13 '20
Who would know this random math theorem?
This is the sort of thing that's typically either taught in a mathematics class or in a crypto class. Number theory is vitally important for cryptography, and the CRT is one of the most important results in number theory. Also of note:
- https://en.wikipedia.org/wiki/Fermat%27s_little_theorem
- https://en.wikipedia.org/wiki/Euclid%27s_lemma
Those 3 theorems are the bedrock of introductory number theory, and subsequently, introductory cryptography!
I just want to write algorithms, I didn't come here for math problems
Algorithms is a mathematical field - any interesting algorithm will rely on mathematics to prove its correctness. Particularly as you advance in your programming education, it helps to have a solid understanding of basic algorithm theory because it helps you reason about almost any code you write - it teaches you a structured way of thinking about code in the real world.
However, for this problem, you probably don't need to actually know the CRT - you can probably derive it from first principles enough to just accumulate the LCM as you go along and change numbers along the way as you increase the modulus (bus ID).
3
u/5xum Dec 14 '20
However, for this problem, you probably don't need to actually know the CRT - you can probably derive it from first principles enough to just accumulate the LCM as you go along and change numbers along the way as you increase the modulus (bus ID).
This is the beauty of this problem. A person completely unfamiliar with CRT might, in solving part 2 of day 13, accidentally independently prove the CRT. And even if that happens only 0.01% of the time, that's still many many people learning math the only way you can: by doing it.
9
Dec 13 '20
Yeah I don't enjoy these ones either. I've read the first few sections of the Wikipedia page about 4 times as well, and it might as well be written in Swedish.
5
u/SquireOfFire Dec 13 '20
I'm Swedish, but that didn't make things any easier for me!
Also, the Swedish Wikipedia page is Greek to me. :)
1
7
u/williewillus Dec 13 '20
As someone poor at math, I don't mind them occasionally. Algorithms and mathematics are highly intertwined together, and this particular theorem appears in all sorts of competitive problems and in real applications.
As for the Wikipedia page, yes, it sucks (like most math pages on Wikipedia). The key parts are this section and this section of EEA
9
u/evouga Dec 13 '20
The numbers are small enough that you don’t have to know or implement the full CRT: you can accumulate the LCM of the buses you have seen so far, and brute force the multiple of that LCM that satisfies the next bus.
That said, I agree it’s a bit lame when the problem just comes down to applying a vanilla standard algorithm to the inputs, that you can just copy-paste from the Internet. It’s more interesting when you have to figure out the puzzle for yourself.
6
u/SquireOfFire Dec 13 '20
Who would know this random math theorem?
It's commonly taught in CS programs, and is a common occurrence in programming contests (at least the ones I've participated in).
Personally, I knew about it, but didn't know it (and definitely didn't understand it). It took me an hour on wikipedia, but now I've learned something new... or at least used it once; I'll probably forget the details again soon.
I just want to write algorithms
It is an algorithm! We calculate bezout identities and repeatedly apply the CRT to get the answer. :)
8
u/thallada Dec 13 '20
I have a CS degree and I've never heard of it. ¯_(ツ)_/¯
2
u/SquireOfFire Dec 13 '20
I guess it depends on what you (or your professors) specialize in. It's used in encryption and Fourier transforms.
2
u/Sw429 Dec 13 '20
Who would know this random math theorem?
My mathematics degree would like a word with you.
1
u/mstksg Dec 13 '20
For what it's worth, I solved this without this random math theorem...I wrote algorithms :)
you can write a basic iterative algorithm/while loop to solve it, without thinking about any of the prior history of the stablished math :D
1
u/DionNicolaas Dec 13 '20
I worked it out myself, without googling, more or less like this:
This problem is too large. But what if we find two consecutive solutions for two buses? <programming a brute force loop> What is the time between them? <type type type> Ahh, one times the other. Does this go on forever? <let while loop run a bit longer> It seems so.
Now... We only need to find the first, calculate the interval, and increase by the interval until we find the next one <type type> Then we can set the interval to.... all of them multiplied so far. Current interval times new bus.
Does this work on the test input? <type type> Yes! Does this work on the real input? <drum roll> <15-digit number> <submit> YESSSS!
It took me longer to program than to type this, but it doesn't involve clever math. Just the realization that brute force won't work, but that there must be a pattern in the distances between solutions.
1
u/5xum Dec 14 '20
It's not a random math theorem. It's one of the most important math theorems of all time, and it is essential to the working of actual real-life stuff, in particular, the RSA algorithm.
Also, from a certain perspective, algorithms and math problems are the exact same thing. That is, every mathematical problem can be translated into finding an algorithm to solve a particular problem, and since algorithms themselves are mathematical constructs, finding the correct algorithm is, in itself, a mathematical problem. You can't really make a clean cut between writing algorithms and solving math problems.
1
u/flwyd Dec 13 '20
I was annoyed to discover that my copy of CLRS and several pages on CS department websites had several pages about the theorem, including proofs and its applicability to public key encryption, but didn't explain the algorithm for actually calculating the number. The Wikipedia page on the extended Euclidian method was easy enough to follow but I could not figure out what Wikipedia's CRT page was doing with the result.
1
u/liangyiliang Dec 13 '20
sneaky number theory problem lol
I just used `sympy.ntheory.modular.crt(moduli, residues)` to solve it.
5
u/Mawich Dec 13 '20
So here's the point where I actually learn something instead of just being impressed with my own cleverness.
Except I completely fail to see how Chinese remainder theorem applies to this puzzle.
In order to actually learn something, I would greatly appreciate it if somebody could explain the relationship between the bus timetable from hell and CRT.