My notes about Advent of Code 2020 (Python/Rust)
I’m a bit late to the party, but one of the highlights of the end of year 2020 for me has been to solve all of 2020’s Advent of Code problems. I shared my solutions on Github. This draft with a few notes about the things I learnt has been lying on my drive for a while, it was time to dust it off.
My favorite problems of 2020
Not all problems are awesome but many will provide a great high to those who chase this kind of thing. The problems are well balanced for people who want a challenge but who are not into competitive programming.
Here are some of the cool problems with a reasonnably clean solutions (haha, not quite. rereading my code 4 months later, it’s super messy), and/or where I have learnt something. In some instances (eg day 2 or 10b), after solving the problem I looked for a better solution thanks to the community.
- 1 using a hand rolled algo vs using itertools
- 2 using a PEG − Parsing expression grammar in Rust. Thanks Fasterthanlime for showing me the light!
- 7 The counting part was fun, it involves graph traversal using BFS and DFS.
- 8a (parsing and running a simple programming language). The first part is straightforward, the 2nd part does not add much
- 10b dynamic programming (10b2 has some notes from Jonathan Paulson’s… speedrun?)
- 13b (solved with chinese remainder theorem, which requires extended gcd)
- 14b (generating every possible bit combinations)
- Turns out 15 is the Van Eck Sequence. Many went for a brute force solution, which is OK on todays machines (<20s in python).
- 18 involved evaluating a math expression. There are many ways to do so. I implemented 2 solutions: one that patched operators then ran eval, and another with the Shunting-yard algorithm (with the expected precedences) in order to convert the infix expression into RPN, then evaluate the RPN stack.
- 19 involved the CYK algorithm. I never managed to implement it, it was easier to turn the rules into a regex
- 20a. Classic backtracking, but with a lot of setup in order to generate the neighbouring states and and performing validity checks. After 300 lines of code and many hours, it felt super great to beat this one! Look at this beauty:
Some cool links
- the subreddit where the community gathers
- Jonathan Paulson’s channel. One of the best competitors codes then explains its solutions every day. That’s very impressive to watch, and the explanations are a goldmine to learn things.
- mjpieters has idiomatic Python solutions in notebooks
- Advent of Code serie in rust, by fasterthanlime. A great introduction to how experienced rustaceans think in the language.
- Visualization of the waiting room (day 11)
- Visualization of the bags (day 7)
- Some behind the scene details on the issues on the first days, and about how AoC works under the hood.
- Upping the ante is a category where some extra constraints are added to the problems, like longer inputs that discards bruteforce or new rules
- Getting Crafty shows some very creative ideas.
- How To Leaderboard, by Betaveros, the… leader of the leaderboard.
- tourist is one of the best competitive programmers. He streams CodeForce problems, and that’s… another level entirely.
- cp-algorithms which provides A LOT of great information regarding algorithms used for competitive programming.
- ecnerwala, second on the leaderboard, speedrunning (!) the AoC problems for 2019.
Other nice retrospectives:
- julia idiomatic solutions: https://blog.kdheepak.com/advent-of-code-2020-retrospective.html
- notes on AoC in Rust: https://explog.in/notes/aoc.html