Advent of Code retrospective

Advent of Code retrospective

Background

Advent of Code is an annual programming contest in December. It runs from the 1:st of December to the 25:th with a new problem in two parts released at 6 AM (CET) each day. The second part of each problem is only revealed when the first part is complete.

The problems are of very different kinds but generally are quite easy in the beginning to then get harder and harder until it reaches a plateau around day 16-18. The second part of each problem is usually a twist on the first part that makes the problem more difficult.

Each problem is a problem statement contained in a background story that is developed throughout the month. Each problem also contains some input, usually a file but could be as simple as a word or a number. The input is the same for both parts of the same day and to solve a part an answer is submitted that is usually just a number or a word. How you arrive at the answer is entirely up to you, the code is not submitted or checked in any way by the system. This has led to some people solving the problems in different languages each day, or solving all problems in Excel for example.

Solving a part gives you a gold star, so there are 50 in total each December to collect. For each star there is a global leaderboard of the 100 fastest people to get that star. It is also possible to create private leaderboards to compare us normal people that don't make it on that list. :)

Advent of code is built and maintained by Eric Wastl. If you haven't tried it, I can highly recommend it, it is a lot of fun.


Interesting problems last year

Last year was a lot of fun, as usual. A big change from the previous years was that there was no problem that built on a previous day's problem. 2019 there were a series of problems that built on each other where a Intcode-computer processor was gradually built.

There were a few days that I would like to share some thoughts about:


Day 10 - Adapter array

The story is that you need to charge a device on a plane with a specific input (jolts) needed to the device and 0 output delivered from the seat. Luckily, you have a lot of adapters that you can bridge the gap over a few jolts. The first part was just to find a permutation of all the adapters so that all could connect to the previous adapter and your device could charge from the last adapter. Part 2 was to find in how many ways the adapters could be connected so that they charged the device.

The second part was especially fun. I solved it with dynamic programming where I created an array of Longs where each index represented the number of possible connections up to the adapter with that index. So my solution was to loop over all indexes and for each index sum up the values in previous indexes that this adapter could connect to. If the adapter could connect to the seat (i.e. handle 0 jolts) the value increased by one. The final answer is the sum of values of the indexes of the adapters that can be plugged into the device. The problem statement was quite helpful here that the number of possible solutions was more than a trillion, so it was clear that a brute force solution would not work.


Day 12 - Rain risk

This problem's input contained instructions for how to move a ship around on an infinite grid. Here I had a lot of help of some utility code I had written for earlier years problems. There are usually a few problems that involve moving around objects on a grid so I have written a few classes to represent positions on a grid and directions to move in that can be used together to solve problems like these. Keep that in mind after having solved a day's problems that some code you have written for that day might be worth extracting for use in another day's problem.


Day 20 - Jurassic Jigsaw

Usually the problems on weekdays can be solved in under an hour so that it is possible to solve them before going to work. The problems that require more code are usually left for the weekends and this problem was no exception. The problem had multiple parts but the main idea was that you were given a number of tiles that could be put together in a big puzzle. A tile was 10x10 pixels and the edges of the tiles fit together by being the same, although we had to flip and rotate the tiles to get them to fit together.

For part 1 of the problem the only thing asked was to identify the four tiles in the corners of the completed puzzle and I thought that solving the entire puzzle would take a lot of time so I wrote a simpler version that just checked the edges of the tiles for the tiles that had two unique edges (i.e. didn’t fit with any other tiles), those must be the corners. That worked, but took a while to write, and of course for part 2 the answer involved finding patterns in the completed puzzle, i.e. we had to put all the pieces together anyway.

It took me more than 2,5 hours to finish both parts and in the end I had code that represented the tiles and the possibility to rotate and flip them how I wanted.

It was quite stressful to write it, but I knew it would take some time so I tried to do it in steps that I could verify along the way. I also felt quite foolish that I had not written that solution directly for the first part, but so be it.

Once I realized I had to write something for solving the entire puzzle, doing it in steps was the right idea. There were some smaller bugs along the way, but I could find them quite early this way and once I had finished the last step and ran the code I got the right answer right away, that was a huge relief. I was not looking forward to debugging the code to find what I had missed.

Final words

Last year was the first year I set an alarm for all 25 days of the contest and I remember getting quite comfortable with it. It meant I really had to make sure I went to bed at a decent time for most of the month. I’m not saying I didn’t enjoy sleeping in on the 26:th, but I don’t remember it being as hard as I had imagined getting up every morning at 5:45.

It was a lot of fun and I am really looking forward to this year's problems.

Connecta med oss för att hålla dig uppdaterad med nya jobb.

Alla jobb
Teamtailor

Karriärsida från Teamtailor