I also wouldn't consider knowing properties of the GCD to be a "random math concept". It shows up in a reasonably large number of contexts. For example, in public key cryptography. A specific case is that at one point someone realized they could just collect hundreds of millions of RSA public keys and crack low entropy ones by checking for common divisors. Doing this naively by checking each pair would have been very costly, but they used properties of the GCD to massively reduce the cost by pooling keys [1].
[1]: Page 7 of https://www.quintessencelabs.com/wp-content/uploads/2020/03/...
well that's just not true at all.
I had no idea WTF the Chinese Remainder Theorem was and just worked out the issue iteratively. All you had to know was that if you are trying to find some large number that is divisible by other prime numbers, the deltas between the candidates will be the product of the numbers.
as in, if you are trying to find a number that is divisible by both 37 and 41, you really just need to find numbers divisible by 1517.
I forget what the name for this mathematical concept is, but it's far less obscure than the CRT.
"All you have to know is .. {this magic}" -- that really reminds me of my freshman year math classes where the TAs would just say, "well if you do it THIS WAY..." (when my main question was how the heck you stumble upon looking at the problem that way, vs all the failed ways)
Well you stumble through half a dozen failed ways first, is the usual method. Eventually you gain "intuition" that lets you jump straight to the way that works and you can't explain exactly how you thought up the correct method, but it just feels so natural and anyway, you can explain in great detail why nothing else would work.
I'm teaching calculus this year so I sympathise with both sides. The problem is that the answer to "how did you know to do it that way?" is experience, as in all fields. But students rarely have the time to accumulate experience and intuition before finals, so there's frustration all around.
What I'm saying is I'm not looking forward to grading six hundred finals where many students will inevitably spend too much time on approaches that were obviously (to me) doomed from the start because they haven't stumbled enough to know it yet.
Two buses make different circular routes from the same depot. One bus takes 3 hours to do a loop, the other takes 5. At what times from the start of the day will both buses be at the depot at the same time?
you could write a loop like this:
for t in range(0, 10000):
if t % 3 == 0 and t % 5 == 0:
print("same at", t)
which if you run, you'd see: same at 0
same at 15
same at 30
same at 45
same at 60
same at 75
same at 90
and even if you knew nothing about math, you could see that and think, oh, so they just meet every 15, which happens to be 3 times 5... You don't need to count up one at a time and check remainders, you can just increment by 15 and get the exact same result.. for t in range(0, 10000, 15):
print("same at", t)
That's more or less what I did when I solved it.. saw how the problem simplified to finding the common multiples of numbers, which when they are prime is just the product. apply this process iteratively and you have the solution.But then again people have a much harder time applying concept they know to given situations than if they're told directly to do something.
https://en.wikipedia.org/wiki/Chinese_remainder_theorem#Comp... describes a few algorithms for doing that.
For comparison, let’s say the “sorting theorem” says “if you have n different numbers, you can place them in a sequence so that no number is larger than its predecessor”.
Now, you have two numbers. How do you apply that theorem to place them in a sequence so that no number is larger than its predecessor?
I've only done 2019 and 2020, but found 2020 to be a lot easier. I got stuck for a day or two on one of the 2019 ones. The one point I was briefly stuck in 2020 was when I was using the wrong data structure. (I don't want to spoil anything.)
Project Euler used to say something along the lines of "not everyone can solve every problem, and that's OK". Looks like they've removed that statement though. I remember encountering it early in my career and realizing some problems I cannot solve, even though others can.
For my personal goals, I want to get better at programming and not at math. When I find myself spending more time on the math rather than programming, I just skip the problem. I suspect many people abandon Project Euler for the same reasons I encountered.
With all that said, I agree that not everyone can solve every problem and that is ok.
When I was in college we used this (or an earlier version, that's a different URL than what I recall) in preparation for ACM programming competitions.
IMO AoC should strife to be completable by 80% of programmers (number is out of thin air, but you got the idea).
Project Euler is a different beast.
Of course that's just my opinion.
I think AoC goes for slowly growing difficulty which helps keep more skilled people engaged.
For the other 20% where I don't even know where to start, I look up a solution on reddit, try to understand it and re-implement it myself, and learn something new. The 2020 day 13 problem mentioned by GP was indeed one of those for me last year.
[1]: https://www.reddit.com/r/adventofcode/comments/kcl7d2/2020_d...
What would be the point then, it will be just another leetcode
Its meant to be hard and meant to force you to learn.
See 2019's IntCode puzzles for instance for something very far from Project Euler. They also had the side-effect of benefiting anyone who spent time refactoring their initial versions to create a better interface, a later day (23?) has you run 50 IntCode computers concurrently and communicating with each other. This became very hard to actually implement for many people because of the structure of their simulator and how they'd handled concurrent simulations earlier.
I wish Advent of Code puzzles were strictly algorithm focused without relying on specifics of mathematics. Skipping puzzles is demotivating for the completionist in me that lacks time to re-read math books.
Perhaps a compromise would be to start with an easy input that any pile of if statements can handle, then give a longer input that will break all but the best algorithms as a bonus.
Granted, I don't know the process of AoC in terms of vetting and building their puzzles, but it seems that the person/people involved all share very similar levels and domain of knowledge. Having more people reviewing or involved in the process that have a wider range of skillsets might avoid these situations.
Example from what I was talking about before: Day 13 of AoC2020 was basically "the answer is the Chinese Remainder Theorem". If you remembered that...great you could solve this in 10 seconds (hell some languages have a _function_ for that theorem!). If not....well good luck finding a solution that runs in under 6h. That has nothing to do with _programming_. Its just math, there wasn't even programming involved (literally some solutions were just "parse the input and pass it to mathlib.chinese_remainder()"). That's not satisfying to solve for the majority of people, I feel (opinion, I know).
result = 0
addend = 1
for divisor, desired_offset in [(7, 0), (13, 1), (59, 4), (31, 6), (19, 7)]:
# keep trying numbers until we find the one that, with
# the desired offset added to it, would divide without
# remainder
while (result + desired_offset) % divisor != 0:
result += addend
# adding another addend should not break previous results
# so make it divisible by all previous divisors
addend *= divisor
result %= 7*13*59*31*19 # Is it really needed? Eh.
print(result)It can be demotivating if you check the number of people who solved it quicker you, but just pretend they all cheated off one really really smart person and you'll feel much better :D
[1]: https://adventofcode.com/2020 shows the number order
I didn't read it in depth, but it feels like you could build regexes on the fly to solve it. Perhaps I missed something crucial.
Edit: Ahh, day 13: https://adventofcode.com/2020/day/13
I actually like when it teaches me something new. If you get stuck you could always google for the concepts you need and learn of them, or go to the subreddit and get hints but still solve the programming part yourself.
Part 1 runs in ~0.5 msecs Part 2 runs in ~2 msecs
This year, my rule is that if it looks like the Chinese remainder theorem, then I can just look it up. There's no need to stay stuck on something that's supposed to be fun.
for each ID in list:
next_departure = round_up_to_next_integer(earliest_time / ID) * ID
delay[ID] = next_departure - earliest_time
nearest_bus = ID with lowest delay
return nearest_bus * delay[nearest_bus]
That's it. I can think of only two other algorithms: the one that replaces division on the second line by repeated subtraction, and the one that uses repeated increments and checking whether the result is divided by the ID without a remainder.How do you even use CRT to solve this?
result = 0
addend = 1
for divisor, desired_offset in [(7, 0), (13, 1), (59, 4), (31, 6), (19, 7)]:
# keep trying numbers until we find the one that, with
# the desired offset added to it, would divide without
# remainder
while (result + desired_offset) % divisor != 0:
result += addend
# adding another addend should not break previous results
# so make it divisible by all previous divisors
addend *= divisor
print(result % (7*13*59*31*19))
This algorithm self-evidently works and is indeed "fast enough" if done by the computer.And instead of talking down to people, it can be more productive if you walk through a solution instead of stating "This algorithm self-evidently works" like a jerk.
Also, the last modulo isn't needed.
After every iteration, "result" gives correct remainders for all divisors considered so far, so if the loop ends, the "result" will give correct remainders for all divisors. The only problem is whether it will end or not, and that I just tried experimentally: it stopped, so ok. Not really sure how to explain it further.
> Also, the last modulo isn't needed.
Good to know, I was not sure if I wouldn't step past it due to constantly increasing addend. I knew about this modular reduction from that one time when I needed to align/move/scroll things on a 80x25 grid.
"if you memorized some mathematical concepts and an obscure algorithm and also recognize that this exact algorithm is the only efficient solution to the problem then you can solve this in 5 seconds, otherwise it will never finish running with any other algorithm".
I immediately quit. I'm not doing these to prove I'm smarter than other people or memorized random math concepts, I'm doing this to practice writing code or to learn a new language.
Not sure if this is indicative of other years (This is the farthest I've persisted in the 3 I've tried) but it was EXTREMELY demotivating, and killed every desire to continue or to even try it again next year.
*EDIT*: Apologies, I was incorrect on the Day where this happened. It was actually Day 13, with the Chinese Remainder Theorem being the solution. I must have copy/pasted a solution in frustration and continued past that point. My mistake.