Advent of Code 2021

Same procedure as last year? Same procedure as every year!

Each December Eric Wastl invites you on an adventure as Santa’s problem fixer. In this year’s Advent of Code, one of Santa’s elves dropped the keys to the sleigh into the ocean and you now have to retrieve them to save Christmas. Quickly you jump into your submarine and start diving. From December 1st to December 25th each day two puzzles need to be solved to finally find the sleigh keys on the ocean floor.

As with last year’s Advent of Code, Method Park’s employees came to save Christmas. 35 of them started on the 1st of December to get the submarine’s sonar system working. Some of them challenged themselves to be among the first to solve the two daily puzzles. Others took on the challenge to learn a new programming language (Rust was the choice for most of us this year) or improve their knowledge with a familiar one.

Two approaches

The Advent of Code provides a fun way to explore new languages, learn new algorithms and grow together. To facilitate this, you could join one of two meetings each day: one for the early birds and one in the afternoon. Over the course of December, the purpose of these meetings crystallised. The early birds were done with their solutions as the 9 o’clock meeting started, so most of its time was used to discuss different solution approaches. Sometimes this meant realising that your brute force attempt could have been substituted by simple arithmetic. Or discovering that someone on the internet used vim to solve it. One of us was even guided by Github Copilot.

The 15 o’clock meeting was a space to find a pairing partner to tackle the problem cooperatively. You would ask if someone wanted to solve the problem in programming language X. Then you join together to explore a new language and the problem itself. Afterwards we shared our solutions on Github.

The 50 puzzles posed ranged over topics from maths, computer science and submarine life. The difficulty increased with each one. In the beginning, solutions were done in a matter of minutes. Later on, some of them took up to six hours to solve. Especially weekend problems proved to be brain twisters.

Solving problems, one at a time

As you travelled the depths of a cave system you needed to avoid smoking lava tubes. This included treating the two-dimensional input as a topological map of the cave’s floor. Initially, all you needed to do was finding local minimums. Here it came in handy if you already had some functions ready to check each neighbouring grid. Luckily the game of life is a common theme and this wasn’t too hard. Then you wanted to determine how big the lava tube basins were. To achieve this we flood filled the cave floor.

After navigating through an extensive cave network we came close to the ocean floor. To find the keys we used probes to map out the area we are searching. But apparently, Santa cheapened out on some of the equipment. Therefore each probe was able to detect the positions of scanning beacons but was not equipped with a positioning system itself. As each of them was lost in the depths of the ocean our task became to identify which of the 35 probes were covering the same area. By combining these we were able to create an image of the whole area we were scanning. This included rotations in 3D space, identifying unique characteristics of the beacons that could be used for fingerprinting and finally computing the size of the area we had mapped.

Coming closer to finding the keys we had to help a colony of stubborn amphipods cleaning up their living situation. While there were certainly solutions involving graphs, linear optimisation or just brute force, none of them seemed to solve the problem faster than our most useful tools: A brain and Excel. In an homage to the Towers of Hanoi we sorted amphipods according to their colour in different caves.

In the end 4 of us managed to get all 49 stars by solving the puzzles. As a small Christmas present, the 50th star was earned on the 25th of December for solving all previous puzzles.