Hacker News Reader

Comment by justinsaccount | Hacker News Reader

> 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

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.

View on HN

> 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.

"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)

> 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.

It's not really magic though. Here's a simpler variation of the problem:

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.

it's funny to me how your problem is literally an applied fizz buzz.

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.

Yes, I worked it out similarly and I saw comments on the twitters recently from others who did. Also usually the tough stuff is in the second part of each day, which I feel is pretty fair and provides a way to feel reasonably good about your result if you're not completely successful.

Yeah, I always liked how I could generally solve something a "dumb" way for part 1, but would likely need to refactor it to be a bit smarter to solve part 2.

Yep, that's pretty much how I solved it too. I had (and still have) no idea how to apply the Chinese Remainder Theorem. Looking back at my solution, I just iterated through the input, which I'd mapped to a Python list.

Nitpick: there’s no way to apply the Chinese Remainder Theorem. It merely states that “if one knows the remainders of the Euclidean division of an integer n by several integers, then one can* determine uniquely the remainder of the division of n by the product of these integers, under the condition that the divisors are pairwise coprime.”* (https://en.wikipedia.org/wiki/Chinese_remainder_theorem) It doesn’t say how to determine that number.

https://en.wikipedia.org/wiki/Chinese_remainder_theorem#Comp... describes a few algorithms for doing that.

Well, you can apply the theorem to the problem. Or apply its principles to the problem.

No, you can’t. It only says the problem has a unique solution. It doesn’t even say an efficient algorithm for computing it exists, or even whether an algorithm exists. Neither of those are very hard to prove, but the theorem won’t help you there.

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?

least common multiple. It's also what popped into my head when I first saw the fizzbuzz problem.

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.)

Yeah 2019 had a couple of mind-benders involving mazes - there are two Part 2s that I need to motivate myself to come back to because my fumbling that got me the respective Part 1 solution was useless for Part 2 (Day 18 and Day 20). Looking back at them they shouldn't be too hard, I just think that at that moment I didn't have the time to spare and never felt like coming back to them. Maybe if I'm bored between Xmas and New Year :)

Reply on news.ycombinator.com