Hacker News Reader

Comment by bussierem | Hacker News Reader

I really enjoyed the early part of this last year, but I got to Day 19 and suddenly it became

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

View on HN

Interesting. I think one of the main benefits of AoC is it tends to teach you things. So I would have gotten stuck, read peoples answers on the subreddit the next day, and the problem would have stuck in my memory as one that taught me something new.

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

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

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

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

Does every problem need to be solvable by everyone?

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.

It's pretty daunting when you're invested into something, spent a plenty hours only to realize that you're not in those 5% who's going to complete this challenge.

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.

For what it's worth, I'm not a (professionnal) programmer, and I can usually solve 80% of the AoC problems intuitively. That's OK for me.

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.

Honestly, I didn't even understand how the CRT applied even after knowing it was required. This visualization[1] is what eventually helped me solve it.

[1]: https://www.reddit.com/r/adventofcode/comments/kcl7d2/2020_d...

While I agree with the sentiment of creating accessible content I think if you make the problems so easy 80% can solve them, what fraction will have fun doing so? Wouldn't say 50% find them trivial and boring/unsatisfying?

I think AoC goes for slowly growing difficulty which helps keep more skilled people engaged.

I for one want that 5% to have interesting challenges, even if I can't be a part of that 5%. Unique achievements should be meaningful and celebrated, not removed for fear of upsetting the majority who cannot achieve them.

> IMO AoC should strife to be completable by 80% of programmers

What would be the point then, it will be just another leetcode

Why is there a lack of "git gud" in some of these programming circles.

Its meant to be hard and meant to force you to learn.

What's the main difference (besides submitting an answer faster than anyone else) between Project Euler and AoC? I find both rather similar (and I can do Project Euler any time of the year)

Project Euler problems seem to be all math based, at least as far as I've seen. Advent of Code problems have numbers as results (most of the time), but aren't always based on some mathematical formulation(s).

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.

Project Euler was one of the first programming puzzle sites. I give credit to them for my interest in programming puzzles. However, I quickly abandoned them once I found other sites that was less math focused.

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.

What other sites do you recommend with less math-focused problems?

https://www.spoj.com

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.

Just the popular ones now but 10 years ago, they were really novel. Leetcode, Hacker Rank and of course, the best one is Advent of Code.

https://adventofcode.com/

I had the same feeling about https://projecteuler.net/ but PE is very clear about being math focused so that's on me.

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.

We should avoid certain questions because they're demotivating to some people?

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.

I think it's more that the puzzles should avoid having a "correct solution" in the form of a known algorithm. If the puzzle can basically only be solved by remembering a specific algorithm, and any other algorithm (or attempt) will grind for hours, then the puzzle isn't about algorithms, or about coding, it's about whether or not you memorized a part of a math textbook and can recognize that it applies to the problem.

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

Is this CRT? Not exactly sure, but it does not run for six hours:

    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)

This is exactly my thoughts on it. Granted I was never strong in math, and that's partly on me, but the early days (and even most mid days) of AoC are usually all about algorithms design and efficiency, but then sometimes you get these random "pick the right math formula" ones and just like you said, I have to "skip" them and it's so demotivating.

I see it as on opportunity to expose yourself to a bunch of things in mathematics and computer science. Also, I'm pretty sure that you could get to the solution you're referring to without knowing any number theory at all.

I was the same as you for a few minutes - I was demotivated and when I found out what was behind it I thought "huh I never learned this and I'm not sure how I would have ever learned this" and felt a little bit defeated. But then I read a little bit on the subreddit, read the wiki on CRT, put together a solution and moved on. It's meant to be a bit of fun, if you have to skip one challenge (or cut a couple corners) it's no big deal - you can always come back to it later :)

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

It actually was on day 19, it's just that puzzle #13 was the 19th puzzle given out [1]. I'm not sure why the numbers didn't come in order last year.

[1]: https://adventofcode.com/2020 shows the number order

If you look at the 'map' on the left side and also follow the plot in the puzzle descriptions, you can see that you were island hopping, so top to bottom is not the order the puzzles came out in.

Oh yeah, that's right.

Link to last year's Day 19: https://adventofcode.com/2020/day/19

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

Part 2 complicated it, but yes. I just built regexes on the fly for Part 1. I wonder if they mean Day 13. The underlying math is based on the Chinese Remainder Theorem, but it is solvable without knowing it (or, in my case, "knowing" it, once I saw others mention it it came back but my math degree was a long time ago). A solution could be discovered incrementally without knowing the math by trying to optimize the naive version.

I did mean Day 13, thank you -- I updated my post accordingly. Sorry about the confusion!

Apologies, I updated my post. It was Day 13 where this happened. Not sure why I stopped at Day 19, tbh.

Day 13 you really needed to know of Chinese remainder theorem; I would say this was probably the only day in the last couple of years so dependent on non-trivial maths. I would still recommend AoC though.

yep, that's what I did. simply converted the input into a regex and matched it. part 2 had to add a little special casing but ultimately not that difficult.

I loved day 19 because I managed to use some Automata theory I studied at uni. Something like, I cannot simply use a regex because it's a context-free grammar. Then I learned about recursive regexes and how they could be used to parse a cfg. Aaah fascinating, really.

I often find that part1 can be solved by most, but part2 sometimes needs a clever trick, experience or some knowledge. Doing only part1 or skipping some day is perfectly fine, though. So I don't really get your anger.

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.

I solved day 13, both parts, and I'm pretty far from an algorithm wiz, I also never used Chinese Remainder Theorem.

Part 1 runs in ~0.5 msecs Part 2 runs in ~2 msecs

Last year I figured it out from first principles, like some of the other commenters, but that problem was one of the hardest for me (like the tile rotating problem, which was excellent).

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 Day 13, I played around with the numbers and eventually noticed that you could increment by the product of the numbers you consumed so far.

I like AoC because it is the least 'know the specific maths trick' of the various coding challenges out there; there are normally a couple of problems like that each year, but most can be worked out if you can think even if you don't have a huge body of maths knowledge.

At the time, I had the same thought process as you. I did eventually come back and do the rest of the days though which were surprisingly trivial in comparison! I seem to recall some people did manage to solve that day using brute force with a non modular approach though.

I'm quite surprised, I spent hours on multiple different solution and every single one was brutally slow.

My memory is hazy, but I seem to recall it involved a lot of parallelization and running it for a couple of days on high end gear along with luck. So definitely not the intended approach! :)

Excuse me, what? You don't need to know CRT or indeed anything about the number theory except that you can divide numbers, the solution is simply:

    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?

Are you looking at part 1 or part 2? GP is talking about part 2.

Can't find part 2 on the site, had to google...

    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.

The key insight that many people, particularly those without the stronger math background, miss is that you can increase the addend like you (and I, in my solution) have done. So they either leave it at 1 (and the solution is around 1-2 trillion, IIRC, so that's not happening quickly) or they do one optimization which is to set it to the first divisor (7 in your example, which still leaves you with hundreds of billions of loop executions), but don't adjust it with each newly matched bus line.

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.

> walk through a solution instead of stating "This algorithm self-evidently works" like a jerk.

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.

fwiw the Chinese Remainder Theorem is taught in basic cryptography courses. ig it could be obscure for someone outside the field though

> Not sure if this is indicative of other years

It is.

Reply on news.ycombinator.com