Today I am talking about the Advent of Code 2020 and what I have learnt doing it this year.
Advent of Code 2020
Advent of Code is a set of programming puzzles with one problem released each day during Advent. Each problem has two parts, the second normally being an expansion on the first.
For most of this year, the second problem expands the first by making it infeasible to brute-force the solution and requires clever algorithm design or datastructures. All problems should be able to run within a few seconds as long as your solution is somewhat efficient.
Like last year I participated in the Advent of code and thoroughly enjoyed it. This year it provided a similar level of challenge while keeping the problems interesting and fun to work on.
This year two of the highlights were implementing a linked list (not something I have done since University) and learning about the Chinese Remainder theorem.
Implemented a linked list
One of the problems required moving segments of an array around and inserting it into other positions in the array. Originally I was using an array and re-composing it every time I needed to slice and move the elements. This worked for the smaller part one but for part two it was too slow.
In addition to the slowness of re-creating the array, part of the problem required you to find a specific entry in the array. This meant that you were a O(n) search every loop iteration which was slowing down my solution.
Initially I was going to use a Java linked list however I encounted some issues with it. The main one was that it isn’t a “true” linked list implementation. Since it is generic it doesn’t provide any methods to move the tail pointer to another element and “quickly” alter the list.
By implementing a simple linked list this allowed me to have custom methods to slice out a set of elements and insert them anywhere just updating the tail pointers of the involved elements.
It was a fun little challenge which sped up the problem considerably and reminded me of the benefits of understanding your data structures.
Chinese Remainder Theorem
The Chinese remainder theorem is not something I had previously read about in my number theory work. For one of the days it was noted as a possible solutions instead of brute forcing the solution (which depending on your solution might take days). My initial solution unoptimized solution was going to take a couple days to solve the problem.
Reading up on the theorem proved interesting as it was able to be used as Advent of Code had helpfully ensured all numbers were pairwise coprime. This allowed solving it relatively quickly as it is one of the requirements of using it.
As with all Advent of Code problems, using this required a little manipulation of the problem but once done the solution was pretty quick to implement.
This year I managed to finish most puzzles by the end of each day. Over time as the puzzles increased in complexity I was no longer able to complete them before work and instead did them during lunch or after work.
Again this has been an incredibly enjoyable experience working on the problems. Part 1 is normally simple enough to quickly code a solution which part two typically requiring optimisation of your solution.
I highly recommend trying Advent of Code as the puzzles are novel and allow you to learn about optimisation of problems. Part one is normally simple enough for someone learning to program and then offers
In addition to being fun, the community around Advent of Code also are very happy to help out and discuss the problem. This means you can read about other peoples solutions and get help if you are stuck.