2021 let’s go.
i should hop on this train
2 Likes
I’m doing it for the first time. I’m not a developer but I have done a fair amount of PHP/Python/Bash scripting in past jobs, but haven’t written much in a few years. First two days of the exercise have been very approachable so far, I’m very interested to see if I can keep up as it continues.
Doing it the first time myself; I should be ashamed of myself. I got an off by one error on day 1 puzzle one because I forgot to cast my numbers to ints (I’m using python).
I did succeed at day 3, but I’m not too happy with my solution or the amount of time it took me to finish.
1 Like
When part 1 is extremely easy, you know the twist for part 2 is going to be hard.
I ended up wasting a lot of time trying to implement very foolish solutions. I eventually arrived at something that worked, but was further delayed by off-by-one errors.
I went and checked the subreddit to see what other people did. The most common solution was even simpler and clearly better than mine. But I’m still pleased with what I did. It worked, produced a correct result, was fast enough. I kind of like that my solution was different from everyone else, even if it is technically worse.
I was definitely on guard when the part 1 problem was so straightforward. When my part 1 implementation was never going to succeed for part 2 I was quite satisfied that the refactor took about the same amount of time to code up as the coding for part 1 and generating the solution for part 2 ended up taking less than 1/10th the amount of run time as generating the solution for part 1 thanks to my new approach.
Day 10 was great for me.
Spoilers
I always love a chance to use a stack.
I’ve now made it further than last year 
while also learning rust
one thing that really helps this time, is I found a youtuber to follow along with Advent of Code 2021 Day 1 (Rust) - YouTube
at first having videos to see how to do something in rust, and now to do the puzzle on my own, and then check out how they did it
I think otherwise I would have ended up stuck on day 6 
1 Like
and also, I was kinda scared of part 2 today, while doing part 1, but turns out it’s easy, if part 1 runs fast enough
Day 15 - My code “worked” but part 2 was too slow. It wasn’t actually the core algorithm that I got wrong, it was one part of it. I ended up Googling and learning a new thing in order to make it work. If someone wants to count that as fail/cheating/etc. whatever. I learned a new thing, and that’s a win.
FYI the thing I learned about was heapq.
I’m surprised I’m still keeping up, never thought I’d make it this far in my first year. I am not a software developer and I haven’t written this much code in years. It’s been interesting watching your videos, which usually I do after I have solved the problem for the day and it is helpful to hear your thinking as you approach the problem and often I will be thinking “oh, he’s about to realize the same thing I did… There it is!”
I 100% agree with your comments about the variable names and readability of code you find online generally. Why do people think it is better or more clever to use variable names ‘p’ and ‘s’ or ‘foo’ or something!? Ok, maybe it saves some bytes in the storage of the code, but it just makes following the logic of the code so much more difficult. Descriptive variable and function names are totally my jam.
Finally, as a non-developer I am feeling like many problems of the past few days have been increasingly trending towards exercising ‘well-known’ Computer Science problems & algorithms (for certain definitions of ‘well-known’). I’m not saying AoC should or shouldn’t develop some problems in this vein, but it is making the activity much less fun for a non CS person like myself. In some cases I am able to vaguely identify the inside baseball CS principle at play (other times the meme’s on the AoC subreddit point me in the right direction) but the development of my solution, especially to solve part 2 in a timely manner or feasible speed, results in me reading a wiki or blog about the necessary algorithm and trying to translate that on-the-fly understanding to code. Kind of fun once or twice but if this is going to dominate the remaining days I might have to tap out.
You know the P=NP that programmers are always going on about? Suddenly it’s relevant.
What is P? P is a set of problems. A P problem is a problem where we already know how to find the answer quickly with a computer. Someone discovered the algorithm. We also know how to verify the answers of P problems with a computer very quickly. So if someone asks a question that is “in P” and also gives you the answer, we know how to get a computer to quickly and correctly determine if that answer is correct.
What is NP? NP is a set of problems. Just like P, if someone gives you an NP problem and also gives you the answer, you can quickly verify whether the answer is right or wrong. However, there is no known way to find the answer quickly if it is unknown.
So the question everyone is always asking is does P=NP? If P=NP that means that all those pain in the ass problems we can verify quickly, but not solve quickly, actually have algorithms to solve them quickly, we just haven’t figured them out yet. Much more likely is that P!=NP, which means those problems don’t have efficient algorithms to solve them, and it just takes a long time when the data is large. If you can prove P=NP (algorithms must exist even if we don’t know them yet) or P!=NP (for even one NP problem prove an efficient algorithm can’t exist) you will be famous forever.
How is this relevant to Advent of Code?
Let’s imagine that someone who isn’t a computer scientist wants to come up with an Advent of Code puzzle. They have no particular algorithm in mind when they make the puzzle. Here’s an example.
Ok, so you’re santa, and you have a naughty/nice list. It’s 2021, so the list is a spreadsheet. The list says the name of each child, their address, naughty or nice, and whether or not their parents leave cookies.
You’re hungry, what town should you visit to get the most cookies?
What town is the nicest?
What house has the most children?
What is the naughtiest family?
I hate cookies now. What route do I take to visit the most children in one hour while avoiding all cookies?
Obviously as a puzzle, the puzzle maker needs to know the answer and needs to be able to verify the answer given by the puzzle solver. That means all possible questions are going to be in P or NP.
If you ask the puzzle solver an NP question, then that means nobody has discovered an efficient way to solve the problem. The only solution anyone will be able to come up with is brute force. We know we can verify a correct answer quickly, so just keep trying answers until we find the right one.
If you ask the puzzle solver a P question, that means there’s an algorithm to solve it. It’s already been discovered. Even if you didn’t have it in mind when you asked the question, it exists. Programmers know about it already, and they will use it.
Obviously, every AOC question is going to intentionally ask a question that is in P, because otherwise it’s rather silly.
It’s still possible that P=NP. It’s also possible that P!=NP, but you asked a question with a problem that we thought was in NP, but is actually P (the algorithm for that one problem just wasn’t discovered yet). But to ask such a question is to ask the puzzle solver to perform a major well funded research project. If we’re asking someone to solve a puzzle in an hour or so, we have to stick to P questions. And if it’s a P question, then it means there’s an algorithm we know already, whether the question asker knew about it or not.
Me: expresses opinion about a preference
You: let me write a manifesto about P & NP
Of course a coding exercise with automated success verification has limitations about the nature of those problems so that they can be verified. In the earlier days it was also likely that many participants used a very similar approach in each of their solutions. But it is conceivable that it could be accomplished in different ways, even if less efficient or taking longer for the computation than the ‘ideal’. Or, if there was an important algorithm ‘required’ at the core of the solution it was fairly straightforward to learn or intuit.
For day 15 it was frustrating that even the smaller data set in part 1 could not be solved without implementing A*/Dijkstra and thus all you did and what I and many others did was pull up a tutorial for A* and implement that algorithm into our own solutions. This is less satisfying as a fun coding exercise for me. I am not saying AoC is bad, you have a different opinion than me, great! And you don’t need to mansplain PNP to me, I took CS classes 20 years ago and learned then that while coding is an exciting and powerful tool that I want to have access to, I don’t geek out over coding theory & algorithm memorization/optimization as hard-core CS people do.
2 Likes
What I’m saying is that what you are asking for is impossible without making the entire exercise rather pointless. There’s nothing the puzzle makers can do differently. Your complaint is with the design of computers, math, and the universe itself.
Please, keep telling me why my preferences are wrong.
Preferences are fine, but your preference seems to be “I would prefer if the law of conservation of energy wasn’t true and I could build a perpetual motion machine.” There’s not much more to say.
Except that is not at all what I said. I don’t want to change anything about the universe, just expressing that as things change they are going away from what I prefer so maybe I will stop doing the thing that is becoming less enjoyable. That’s a nice strawman you’ve built there.
2 Likes