Comment by macintux
Comment by macintux 3 days ago
Someone else in the thread lamented the problems as "too easy" and I wondered what world I was living in.
Comment by macintux 3 days ago
Someone else in the thread lamented the problems as "too easy" and I wondered what world I was living in.
>The people doing official collegiate level competitive programming would find AoC problems pretty easy.
I used to program competitively and while that's the case for a lot of the early day problems, usually a few on the later days are pretty tough even by those standards. Don't take it from me, you can look at the finishing times over the years. I just looked at some today because I was going through the earlier years for fun and on Day 21/2023, 1 hour 20 minutes got you into the top 100. A lot of competitive programmers have streamed the challenges over the years and you see plenty of them struggle on occasion.
People just love to BS and brag, and it's quite harmful honestly because it makes beginner programmers feel much worse than they should.
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.
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!
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.
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.
It's just bluffing, lying. People lie to make others think they're hot shit. It's like the guy in school who gets straight A's and says he never studies. Yeah I'll bet.
They... sort of are though? A year or two ago I just waited until the very last problem, which was min-cut. Anybody with a computer science education who has seen the prompt Proof. before should be able to tackle this one with some effort, guidance, and/or sufficient time. There are algorithms that don't even require all the high-falutin graph theory.
I don't mean to say my solution was good, nor was it performant in any way - it was not, I arrived at adjacency (linked) lists - but the problem is tractable to the well-equipped with sufficient headdesking.
Operative phrase being "a computer science education," as per GGP's point. Easy is relative. Let's not leave the bar on the floor, please, while LLMs are threatening to hoover up all the low hanging fruit.
You say in your comment: "Anybody with a computer science education ... should be able to tackle this one" which is directly opposed to what they advertise: "You don't need a computer science background to participate"
"Anybody with a computer science education who has seen the prompt Proof. before should be able to tackle this one with some effort, guidance, and/or sufficient time."
I have a computer science education and I have no idea what you're talking about. The prompt "Proof." ?
Most people who study Comp Sci never use any of what they learned ever again, and most will have forgotten most of what they learned within one or two years. Most software engineers never use any comp sci theory at all, but especially not graph theory or shit like Dijkstras algorithms, DFS, BFS etc.
Holy fuck. I should just grow coconuts or something in the remote Philippines.
> Most software engineers never use any comp sci theory at all, but especially not graph theory or shit like Dijkstras algorithms, DFS, BFS etc.
But we are talking about Advent of Code here, which is a set of fairly contrived, theoretical, in vitro learning problems that you don't really see in the real software engineering world either.
> The prompt "Proof." ?
See this paper on the Stoer-Wagner min-cut algorithm from graph theory, for the last problem in a previous year's Advent of Code: https://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Handou...
> I have a computer science education and I have no idea what you're talking about.
A post-secondary computer science education? I don't mean bootcamp. I mean a course of study in mathematics.
I have a bachelor's degree in Computer Science, which I assume is what you are referring to by "computer science education".
My only assumption is that you're really out of touch with the ordinary world of humanity if you think most people are aware of stuff like this:
https://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Handou...
Realize in anything, there are people who are much better than even the very best. The people doing official collegiate level competitive programming would find AoC problems pretty easy.