Advent of Code 2020 notes
There is a yearly challenge named “Advent of Code” in which I took part this year . Here are some notes and analysis.
If you’re not familiar with it, Advent of Code is like a Christmas calendar for programmers. Starting from the 1st of December, there are daily tasks available. Each “day” consists of two parts, the first one is a “basic problem” and the second one is usually a slightly modified version of it, usually much harder. All you need to do is to submit a correct answer, you can solve your puzzles in any language, using Excel or just a piece of paper.
You don’t know what part 2 will be until you solve part 1. You often find yourself in a situation that you need to rewrite the entire program.
All my code is available here if you want to take a look, but beware, some of it is disgusting. Of course, I was writing in Rust, because why not.
This is an important question. If I can’t find an answer to it, then eventually I’ll drop it, just as many people did. So my receipt of driving things to completion: ensure that you know why you’re doing something and don’t do it if there is no reason!
Here is my reasoning for participating:
🔗Refresh algorithms in memory
Working as an “enterprise” developer means that 90% of tasks are just about transforming data fetched from somewhere and serving it in a specific format. Not that exciting, right? What is worse is that there is almost no algorithm skill required. Any data structure that you may need is already written and all problems are solved . You just need to search a bit and apply a pre-made solution.
Modern programming is more like a building from blocks. You just need to know those blocks or know where to get some.
On the other side, this type of challenges usually require implementing a very custom logic or super-efficient solution, because the hot loop will be intentionally iterated literally
🔗Relief of a daily programming routine
The Advent of Code gives me a rare opportunity to test my skills in “olympiad programming”. This is a completely different skill than “enterprise programming” because:
- You don’t need to write reliable code, just get an answer
- You won’t read this code ever again so “spaghetti”, “stinky”, or highly obscure code is pretty much okay
- You don’t need to collaborate with anybody, communication skill is not used
- Nobody will see it. No comments thus
- Copy-pasting instead of shared logic is also fine
- Specifications are clear (almost all the time)
- Output is well-documented, test cases are already written
So yeah, I would consider those two completely independent skills.
🔗Change my daily routine
With the pandemic going on (just search for
2020 on the internet), my day now lacks many small things like dressing, commute, and podcasts :) I can’t make myself do pointless things, like walking out before coming back home for work to maintain the routine. After many months of getting up, having breakfast, going to work, and then back to sleep, I began to feel that this is not so healthy.
I needed to break this loop and the best way to do this is to introduce something new, change the schedule, set alarm to a different time, or somehow else change the things or move them around a bit.
Each Advent of Code day unlocks at 7:00 in my timezone, so it was a perfect chance to do that! Now when the challenge is over, I’ll spend this additional morning time writing for this blog.
There is a huge reddit community around Advent of Code.
146 000 participants solved day 1, which is a HUGE number. Even my colleges organized a private leaderboard, though I was the only one who completed all the tasks. It’s amazing to see all this activity going on and share problems and solutions with others. In the morning you write Conway’s Game of Life for 3 and 4 dimensions, a few hours later you see a visualization of it!
I won’t go into every single one of them, just highlight the most remarkable ones. If you want a detailed walkthrough, take a look at this awesome article series by Amos.
🔗Day 1: Report Repair
TL;DR: Find two numbers in a list that sum in
The start was super easy, few lines, and part 1 is done.
For part 2, find 3 such numbers
Copy-paste one line and part 2 is done as well.
I was a bit disappointed, so I decided to implement a general solution for any given
N. This turned out to be somewhat tricky, since I didn’t want to use any side libraries at that moment, so I implemented an array of indexes:
const N: usize = 3; // This is a const fn, so the value is computed during the compile-time! // it just produces a fixed-length array like // [0, 1, 2] const // Tries to increase the index array by one // true => increase successful // false => no, abort, abort! // This probably could be implemented as iterator! // Just iterating over these indexes
🔗Day 4: Passport Processing
TL;DR: Validate a lot of passports by field requirements
Just recently I step across the validator crate by awesome Vincent Prouillet a.k.a
I was really happy with the result:
// Main struct. // Validate trait adds .validate() method, which tells is the struct is valid or not // Validity of fields if determined by an annotation // We can even use custom validation functions (validate_hgt, validate_pid)! // Few validation regexes lazy_static! // Validation function example, the other one is a bit trickier
That’s it, problem solved.
🔗Day 10: Adapter Array
TL;DR: Count all the possible ways to traversal a graph in which edges can connect vertices with no more than 3 value deltas
I didn’t want to deal with the graph problem myself, so I tried to use petgraph. That didn’t work well.
This was the first one on which I stuck for quite a while. The issue is that the input graph has too many branches, so if you’ll try to actually “build” all the paths and then count them, it would take ages to complete.
But petgraph allowed me to get an image of a test graph:
Looking at it for quite a while, I realized that the number of ways you can get to node
7 equals the number of ways you can get into
6 + same for
5 + same for
🔗Day 12: Rain Risk
TL;DR: You need to navigate a boat in a storm first using absolute directions, and then relative
Nothing special or difficult here, but I enjoyed this one! Probably because I implemented it in a way that diff between parts one and two was tiny.
🔗Day 13: Shuttle Search
TL;DR: For a list of periods (bus schedules) for a given time point find which period will be next. For part 2 find a point in time what all periods align next to each other
Part 1 was quite easy, but I stuck with part 2. After lots of trials and errors, I figured out that you need to start by iterating over points in time one by one. Once you met one period, you can start iterating by its value. Once you’ve faced another — you can find the least common multiple for them and continue stepping by it.
All the magic is in this loop:
// tt stands for "time table" — Vector of (u64, u64). First is the index, second is "period" // The vector is sorted so the bus with the biggest route (period) will be the first tt.sort_by; let mut iter = tt.iter; // Extract the first element — it'll be our initial step. let = iter.next.unwrap; t = step - t; for in iter
🔗Day 17: Conway Cubes
TL;DR: Game of life in 3D. And then in 4D
Pretty simple and fun, the video above was created for this day. Part 1, of course =)
I never happened to implement the Game of Life, was just copy-pasting the algorithm from Wikipedia once. By the end of this day, I already implemented 4 versions of it (2 in this and 2 in Day 11: Seating System), but it still was a lot of fun for me!
🔗Day 18: Operation Order
TL;DR: Solve equations where
*have the same priority. For part 2, do the same, but
This can be solved by using a regular expression to insert brackets, but this is not the way .
Mentioning it here just because it was funny :)
🔗Day 19: Monster Messages
TL;DR: Validate messages against… some sort of validation tree? AST ? I don’t know how to call it XD For part 2, do the same, but the tree is now recursive (contains loops). Luckily, there are only two of those and both are on level 1.
Fist part was easily solved by generating a set of all possible solutions, and checking that the message is in this list.
Part 2 ruined this approach completely. Any attempts to optimize that algorithm (e.g. get the list of messages before the recursion) completely failed.
After losing some hair, I had to rewrite everything from scratch “bottom-up” this time. Check the message symbol by symbol. Was pretty tricky, but with a small help of the community I managed to do it
🔗Day 20: Jurassic Jigsaw
TL;DR: Assemble a puzzle from given tiles. Tiles can be rotated or flipped. For part 1 find the edges For part 2 count a specific pattern on the image
Part 1 was rather simple. I’ve put all the borders into a hashmap, and then found all that tiles that have two unique borders. Easy-peasy.
Then I realized that you do need to actually assemble it. Oh, this was hell for me. I struggled the whole day with it, and then the next one and then the next… I managed to solve it only on day 25 when I realized that I can’t complete the challenge without it.
The initial idea was simple enough: get all possible tile borders, put them into a hashmap, and then “pull” it from there one by one. Do you see any problems?
Actually, yes. Since the tile can be flipped, you can get the “unique” border even for the central tile. All of those, actually.
To realize this I even had to make these tiles!
Ok, but how to solve this? Normalization! Luckily, I read about BitVec recently and was using it, so this worked like a charm:
Yeah, a “Normalized” border is just a minimal number between a border and its flipped version. After that, the code just started to work.
Counting monsters was just a meter of tests .
🔗Day 23: Crab Cups
TL;DR: You’re playing in cups with Crab. He has 8 cups and makes 100 moves using a specific set of rules. You need to predict the final arrangement of cups. Part 2 is basically the same. Except Crab now has a million cups and makes 10 million moves!
I spent a lot of time solving part 1 in a very “efficient” way, as I thought. Not using LinkedLists, just swapping elements in-place in a fixed-length array. Surely, it will be faster, right?
No. Turned out, the performance of swapping is terrible. So I rewrote it using LinkedLists, but the performance was just the same. I either had to wait for 14 hours or find a better way. After 8 hours of smashing my head into the
wall flamegraph, I went to reddit looking for guidance. One last time.
The solution… hardly fits into my mind. It’s basically a linked list, but since the elements don’t need to store anything except the link to the next element, we can store it as an array, so the access will be
O(1), we won’t need to go the whole linked list. This is so beautiful!
🔗Day 24: Lobby Layout
TL;DR: Another Game of Life, this time of a hex grid!
While reading the task, I realized that I had no idea how to store a hex grid in memory and navigate on it, so I just searched a bit. My finding was precious: this site with this article. I definitely advise you to check it out, even if you’re not interested in hex grids. It is very interactive and has a lot of stuff about the algorithm used in games. It helped a lot.
The idea is that you can treat a grid as a 3D cube on which you’re looking from the angle:
Simple and beautiful, just as I like it :)
I found these survey results about this year’s challenge.
- Rust is the second popular language with 10.17% usage! Fantastic!
Python is of course the leader.
- GNU\Linux is almost as popular as Microsoft Windows ™
- The AoC author’s answers are quite remarkable, check them out :)
Global stats of participants look like this:
25 9173 3107 **** 24 12310 913 ***** 23 11994 2486 ***** 22 14469 2921 ***** 21 14981 207 ***** 20 11810 4670 ****** 19 16525 3132 ****** 18 23048 1703 ******* 17 23949 684 ******** 16 27362 3746 ******** 15 31912 1763 ********** 14 31278 3755 ********** 13 32393 9711 ************ 12 40511 3273 ************ 11 41507 4458 ************* 10 45585 10374 *************** 9 57769 1375 **************** 8 59329 4641 ****************** 7 58965 5786 ****************** 6 77145 2430 ********************* 5 82055 1749 ********************** 4 86370 10684 ************************** 3 104362 3381 **************************** 2 124164 3820 ********************************* 1 146026 10309 *****************************************
check them out here
Another interesting graph is a conversion rate:
You can clearly see the hardest days I mentioned above: 4, 10, 13, 20.
My results aren’t exactly impressive:
-------Part 1-------- --------Part 2-------- Day Time Rank Score Time Rank Score 25 00:28:15 2140 0 01:55:06 3188 0 24 00:37:24 2221 0 01:15:03 2148 0 23 04:19:55 5735 0 10:56:10 5919 0 22 00:36:59 3554 0 01:30:54 2612 0 21 00:37:52 1491 0 00:45:10 1298 0 20 01:41:02 2280 0 >24h 10961 0 19 03:00:51 3987 0 11:23:30 6776 0 18 00:37:29 1966 0 01:05:34 2077 0 17 02:00:34 4498 0 02:06:09 4080 0 16 00:42:28 4674 0 03:35:23 6316 0 15 00:49:02 5064 0 00:50:05 3476 0 14 00:40:12 3774 0 02:18:15 5185 0 13 00:15:35 3400 0 03:54:02 5303 0 12 01:11:54 6784 0 01:40:15 5748 0 11 01:30:01 6845 0 04:18:42 9623 0 10 00:23:31 6346 0 03:55:36 9770 0 9 00:23:35 5808 0 00:41:18 5736 0 8 00:27:07 6565 0 01:58:50 9691 0 7 00:58:18 5244 0 01:04:09 3546 0 6 00:09:23 3398 0 00:29:42 5495 0 5 00:27:23 4995 0 00:35:38 4628 0 4 00:30:34 5956 0 01:08:03 4940 0 3 00:22:15 5223 0 00:37:14 5674 0 2 00:29:59 5702 0 00:36:03 5144 0 1 01:16:49 6714 0 01:17:52 6101 0
But I’m still pleased that I managed to accomplish this. It was a great experience and I feel that I became a better programmer 😎
Huge thanks to the author!