Comment by alexfoo

Comment by alexfoo 3 days ago

4 replies

The group of people for which the problems are "too easy" is probably quite small.

According to Eric last year (https://www.reddit.com/r/adventofcode/comments/1hly9dw/2024_...) there were 559 people that had obtained all 500 stars. I'm happy to be one of them.

The actual number is going to be higher as more people will have finished the puzzles since then, and many people may have finished all of the puzzles but split across more than one account.

Then again, I'm sure there's a reasonable number of people who have only completed certain puzzles because they found someone else's code on the AoC subreddit and ran that against their input, or got a huge hint from there without which they'd never solve it on their own. (To be clear, I don't mind the latter as it's just a trigger for someone to learn something they didn't know before, but just running someone else's code is not helping them if they don't dig into it further and understand how/why it works.)

There's definitely a certain specific set of knowledge areas that really helps solve AoC puzzles. It's a combination of classic Comp Sci theory (A*/SAT solvers, Dijkstra's algorithm, breadth/depth first searches, parsing, regex, string processing, data structures, dynamic programming, memoization, etc) and Mathematics (finite fields and modular arithmetic, Chinese Remainder Theorem, geometry, combinatorics, grids and coordinates, graph theory, etc).

Not many people have all those skills to the required level to find the majority of AoC "easy". There's no obvious common path to accruing this particular knowledge set. A traditional Comp Sci background may not provide all of the Mathematics required. A Mathematics background may leave you short on the Comp Sci theory front.

My own experience is unusual. I've got two separate bachelors degrees; one in Comp Sci and one in Mathematics with a 7 year gap between them, those degrees and 25+ years of doing software development as a job means I do find the vast majority of AoC quite easy, but not all of it, there are still some stinkers.

Being able to look at an AoC problem and think "There's some algorithm behind this, what is it?" is hugely helpful.

The "Slam Shuffle" problem (2019 day 22) was a classic example of this that sticks in my mind. The magnitude of the numbers involved in part 2 of that problem made it clear that a naive iteration approach was out of the question, so there had to be a more direct path to the answer.

As I write the code for part 1 of any problem I tend to think "What is the twist for part 2 going to be? How is Eric going to make it orders of magnitude harder?" Sometimes I even guess right, sometimes it's just plain evil.

volkadav 2 days ago

Sorry to focus on just one aspect of your (excellent) post, but do you have recommendations for reading up on A*/SAT beyond wikipedia? I'm mostly self-taught (did about a minor's worth of post-bacc comp sci after getting a chemistry degree) and those just hasn't come up much, e.g. I don't see A* mentioned at a first glance through CLRS and only in passing in Skiena's algorithms book. Thank you!

  • alexfoo 2 days ago

    Not sure. I covered them during my Comp Sci degree in the mid/late 90s. I'm probably not even implementing them properly but whatever I do implement tends to work.

    Just checked my copy of TAOCP (Vol 3 - Sorting and Searching) and it doesn't mention A* or SAT.

    Ref: https://en.wikipedia.org/wiki/The_Art_of_Computer_Programmin...

    A quick google shows that the newer volumes (Volume 4 fascicles 6 and 7) seem to cover SAT. Links to downloads are on the Wikipedia page above.

    Maybe the planned 4C Chapter 7 "Combinatorial searching (continued)" might cover A* searching. Ironically googling "A* search" is tricky.

    Hopefully someone else will chip in with a better reference that is somewhere in the middle of Wikipedia's brevity and TAOCP's depth.

CobrastanJorji 2 days ago

Yeah, getting 250 or so stars is going to be straightforward, something most programmers with a couple of years of experience can probably manage. Then another 200 or so require some more specialized know-how (maybe some basic experience with parsers or making a simple virtual machine or recognizing a topology sort situation). Then probably the last 50 require something a bit more unusual. For me, I definitely have some trouble with any of the problems where modular inverses show up.

ctxc 2 days ago

That's a pretty crazy background. I wish you'd put your profile in your bio so I could follow you!