4 ms·

> if you memorized some mathematical concepts and an obscure algorithm and also recognize that this exact algorithm is the only efficient solution to the proble

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

boutell 5y ago
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.
- justinsaccount 5y ago
  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.
shever73 5y ago
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.
- Someone 5y ago
  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 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#Computation https://en.wikipedia.org/wiki/Chinese_remainder_theorem#Comp... describes a few algorithms for doing that.
  - anandoza 5y ago
    Well, you can apply the theorem to the problem. Or apply its principles to the problem.
    - Someone 5y ago
      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?
dunham 5y ago
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.)
- smcl 5y ago
  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 :)
gknoy 5y ago
> 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)
- solveit 5y ago
  > 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.
- justinsaccount 5y ago
  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.

boutell 5y ago

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.

justinsaccount 5y ago
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.

shever73 5y ago

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.

Someone 5y ago
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 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#Computation https://en.wikipedia.org/wiki/Chinese_remainder_theorem#Comp... describes a few algorithms for doing that.
- anandoza 5y ago
  Well, you can apply the theorem to the problem. Or apply its principles to the problem.
  - Someone 5y ago
    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?

dunham 5y ago

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

smcl 5y ago
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 :)

gknoy 5y ago

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

solveit 5y ago
> 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.
justinsaccount 5y ago
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.