Advent of Code 2020 Review

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.

Personal Stats

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.

	Part 1		Part 2
Day	Time	Rank	Time	Rank
25	>24h	12028	>24h	8983
24	09:40:33	9306	10:12:32	8098
23	16:27:38	11842	18:39:33	8776
22	15:28:39	14006	18:07:56	11522
21	>24h	13068	>24h	12838
20	11:03:32	8161	15:06:20	4551
19	12:24:15	10415	14:49:24	8442
18	13:05:28	15086	18:10:58	15560
17	13:36:03	14385	14:08:18	13796
16	12:48:24	19872	16:34:40	17374
15	14:41:00	22592	14:42:57	20548
14	03:54:35	10759	15:23:43	18138
13	07:43:35	20453	10:33:59	12396
12	05:49:53	15215	06:47:20	13700
11	03:39:10	11740	04:06:21	9322
10	03:25:26	17566	12:32:58	21742
9	02:54:49	15600	03:04:23	14076
8	04:16:49	20703	05:10:44	18689
7	05:25:59	17473	05:51:41	14514
6	03:59:15	18884	04:04:30	17054
5	05:15:30	20994	05:18:31	19532
4	03:40:47	20678	03:59:20	14769
3	03:46:47	21022	03:53:13	19277
2	02:36:21	14321	02:42:47	13419
1	16:49:51	61909	16:53:57	57241

Final Comments

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.

All my code for this year and previous years is on Github so feel free to have a look through how I solved the problems.