Advent of Code 2020

2020-12-27

coding

:coding:

This year was the first time I’ve decided or even tried to participate in Advent of Code (AoC) challenge. Since it was the first attempt I had no clue what to expect. I haven’t participated in competitive challenges ever though I’ve solved some similar tasks on Hackerank or other pages. I haven’t competed for time because the every day task is opened at 7AM. Exactly the time when I prepare breakfast for my kids, bring them to school/kindergarten and after return - need to start work on my job (not on AoC). I decided not to stress but focus on completeness instead and solve every problem I’m able to. Do not copy code from libraries, do not look into solutions of other participants if I haven’t solved the task yet. Happy to say - I’ve managed to solve every task manually!

Tasks

I would call 2020 AoC challenge a medium-complexity where some motivation to complete tasks is required. Multiple tasks involves some level of string parsing such as extract tokens and build hashmaps. This is pretty easy with languages as python but might require more boilerplate code for languages as C. The final problems were not as diffitult to implement as cryptic to understand. It also demonivated me a bit in the later days as there were many other things to do before Christmas. Below is a list of tasks with used algorithms to get a better understanding what AoC is about.

Day 1 (easy): Arrays.
Day 2 (easy): Strings.
Day 3 (easy): Matrix.
Day 4 (easy): Regex.
Day 5 (easy): Bitwise operations.
Day 6 (easy): Arrays.
Day 7 (medium): Graphs.
Day 8 (medium): Emulator implementation basics. One of my favorite tasks.
Day 9 (medium): Arrays. Can’t remember actually it it was easy or not so easy to crack.
Day 10 (hard): DP. This was one of two the most difficult problems and not only for me. I am not good at DP and it is definitelly an area where I need to practice.
Day 11 (medium): Game of life.
Day 12 (medium): Matrix operations.
Day 13 (hard): The another most difficult problem. DP. Though some people found a theorem and solved in that way.
Day 14 (medium): Bitwise operations.
Day 15 (easy): Hashmaps.
Day 16 (medium): Hashmaps, backtracking.
Day 17 (medium): Game of life in n-dimmension cubes. Easy to get lost in coordinates.
Day 18 (medium): Stacks. Infix evaluation. Nice problem.
Day 19 (medium): Recursion, regex. Another nice problem.
Day 20 (hard): Obvious how to solve. But a lot of space for bugs as multiple algorithms needs to be applied. Used algorithms: matrix rotation,
Day 21 (easy): Set operations, hashmaps. transpose, bitwise oprations, string search. Very time consuming.
Day 23 (medium): Linked list.
Day 22 (medium): Recursion, deque.
Day 24 (medium): Matrix or set or hashmap.
Day 25 (easy): Loops.

Notes

Below are some general findings from participation in 2020 AoC.

Programming language matters. I’ve picked Python but at the same time I’m not a pro at this language. In parallel I’ve started to read “Fluent Python” to learn using the language in a proper way. Python comes with many useful libraries such as numpy. It is excellent to work with matrices (haven’t used the lib before). I didn’t want to spend time on matrix rotation since I’m pretty sure I would be able to write this algorithm. So numpy.rot90(m) and similar functions were handy. Need to master functools and itertools packages. I haven’t used those in my solutions but it would be possible to reduce number of lines with these things.
Tests helps. Splitting solution into functions and testing separate functions helps to catch bugs. I like python because I simply can write assert my_func() == 1 and validate if function behavior is correct. If I’d compete for time, creating functions and tests is time consuming.
I become lazy after solving about a half of problems. Not that problems became harder but some of those required more time to solve. Some solutions were obvious theoretically and I just wasn’t very motivated to put my hands in the dirt (e.g. Day 20, Day 21). This could be either a question of my motivation or just some problems were boring.
Optimal solution is not needed very often. I’ve over optimized solutions when it was not necessary. In AoC multiple problems can be solved via brute-force or some small optimization of BF. For example the Day 17 task I’ve calculated only a half of cubes, because another half is just a mirror. The same with hypercubes. That increased the complexity my code but as figured out later - it was not necessary. AoC is not such type of competition where every task is validated against time. Input is only one and the same. If you get the result with reasonable time - that is fine. Meanwhile on Hackerank you’d get one input, another and finally x1000 times bigger input will be fed to your code. If it would not complete within given time - you would not get points for that dataset. That is not a case in AoC.
Code can be optimized for input. Since input data is fixed - it is possible optimize it for the code: pre-sort, eliminate unnecessary lines, etc. This approach is also possible in the code. For example if there is possibility of infinite recursion - setting the hard limit for the recursion instead of tracking visited nodes would work.
Belonging to private leader board motivates. We had a board with 11 active members and dedicated chat room. It is much more fun to discuss every problem afterwards with a bunch of fellows and see each other succeeding. Checking that someone from my leader board already solved the problem pushed myself to solve it to. Seeing other folks are struggling gave me understanding I’m not a total potato who is not able to complete particular problem within half hour. 4 of us managed to solve every problem.
Read instructions very carefully - these are cryptic sometimes. I’ve wasted some time when missing small details in a see of sentences. E.g. on Day 22 I’ve forwarded a full deque instead of limited size just because I’ve missed the sentence.

Finalize

In general I liked AoC a lot. It is a very friendly challenge. Friendly in that way that you are not being pushed to optimize every bit of problem. Also you can catch up unsolved problems during weekend or on your own pace. Perfect for pre-Christmas period :-)