Advent of Code, day 24 + 25: Think out of the box

Bugs in recursion

Lets first talk about Day 24 – “Planet of Discord”. This puzzle reminded me of the fascinating Conway’s Game of Life that dates back to 1970.

Part one was about finding a repeating pattern in the ever-changing constellation of bugs. Now my loop detector that I had prepared earlier on day 12 to solve “The N-Body Problem” came in handy. So this part was quickly resolved. So let’s continue with the typical more advanced part.

In part two, another dimension, namely recursion, has been added to the universe. This reminded me to the so called Droste effect, dating back to 1904. In fact, in this case we are dealing with a variant in which recursion is applied both inwards and outwards. It is comparable to both infinite zooming in and infinite zooming out. To solve this puzzle, however, only a limited number of levels had to be evaluated, because there exist only a finite number of bugs at any given moment in time.

Difficulties and illusions

Now, lets talk about Day 25 – “Cryostasis”. The last puzzle of this year showed that the sting was in the tail for me.

It might have something to do with waking up at 5:30 am (and drinking coffee at 5:45 am) every day in December, which is not exactly my usual time to get up, especially on the shortest days of the year. This is the aspect that I was most afraid of beforehand, but during the game it became a natural part of my modus operandi as well as trying to complete the puzzle before dawn, which I usually did, but not always.

Due to social activities on Christmas Eve, I only had 3 hours of sleep, which didn’t help either.

I could always predict the difficulty of the next puzzle. At least I thought so. This year there was a real advent calendar next to my desk with small cosmetic gifts whose doors could only be opened when solving the puzzle of the day. Somehow I had told myself that the size and shape of the door were indicative of the difficulty of the corresponding puzzle. In the end this turned out to be an illusion. In various ways I have calculated the difficulty of each puzzle based on the global statistics and my personal statistics. I have compared these results endlessly with the dimensions of the doors, but I have not found a consistent correlation.

Anyway, there were only 24 doors, so I had no idea what to expect from the last puzzle.

Alan Turing’s legacy

The IntCode™️ computer must be put to work for the last time. I myself called it the Turing machine, which is a bit of a misnomer. This one has a finite tape, so actually it should be called a finite-state machine. Furthermore, it has a head that can move to random positions. I think it’s a brilliant find. It is amazing how the creator of Advent of Code, Eric Wastl, manages to conjure up more novelties every year. Although tempting I haven’t tried to automatically decompile the input tape and express it in a 3rd-generation programming language.

It is a dimension that adds a little magic to the puzzles. This category of puzzles is especially interesting because they do require some extra investigation. It is not entirely clear what to expect in advance, so some research is needed to find out what is actually going on. It is more labor intensive, while other puzzles mainly depend on pure thinking. In all cases, a lot of creative thinking is required to solve all problems.

Lost in Euclidean space

To solve the last puzzle, a starship must first be explored in detail, for which multiple approaches are conceivable. Initially I tried to map all rooms on a normal two-dimensional grid. That produced rather confusing results and for unclear reasons I decided to add a third dimension to travel, as it were, to different floors in a three-dimensional Euclidean space. This proved to be hopelessly complicated and fruitless and I had to use multiple “hacks” to solve the puzzle in this way, but it was quite difficult and clearly not the most efficient way.

Because I was not particularly satisfied with my first approach, I started to think about alternatives. There simply had to be a much simpler solution.

On the one hand, there is a more abstract approach, without even trying to visualize the rooms on a map. Applying the concept of opposite wind directions ‘north and south’ and ‘east and west’ is sufficient and it is not necessary at all to worry about the position of the droid in an imaginary grid. It’s just a matter of applying a smart way to walk through the ship and discover all the rooms.

Finally a good visualisation

On the other hand, I still could not abandon the more visually oriented approach. I struggled for a while with what to do with the room that turned out to have different names and doors, depending on the direction I entered. It was clear that I had to think outside the box. Then I suddenly remembered the recursive structure that was used the day before.

I had this typical Eureka moment. Most participants will recognize this type of experience.

I just had to give up the stubborn belief that the grid should be perfectly uniform. Somehow I was terribly biased and simply assumed that every room has the same shape and size. Finally, I was able to figure out how the interior of Santa’s ship could look like.

Weights on the scale

Once you have come all the way to the “Pressure-Sensitive Floor”, after collecting some items and overcoming various pitfalls, a loud, robotic voice says that I am ejected back to the “Security Checkpoint”.

Alert! Droids on this ship are lighter|heavier than the detected value!

The challenge now is to find out which combination of items has a total weight that exactly matches the correct value. After a couple of attempts, finally a loud, robotic voice says that I may now enter the cockpit.

Analysis complete! You may proceed. Oh, hello! You should be able to get in by typing ***** on the keypad at the main airlock.

Partially ordered

Although it is possible to find a (minimal) solution for the actual weights of the different items that can be found in the different rooms, this is not necessary to solve the puzzle.

Also note that the set of all subsets defines a so called partially ordered set. This implicates that given a collection of items that are classified as too heavy or too light, not all of its subsets and supersets need to be evaluated. But a binary search algorithm cannot be applied in this case because the subset / superset relation does not define a linear order.

Time to recalibrate

After entering the correct password, the only action left was to “align the Warp Drive again” to reach the 50th star. Now I can see all the Easter eggs and I have time to recalibrate my Circadian rhythm.

So I made it to the end again. Last year I participated for the first time and I didn’t really know what to expect. This year I was much better prepared and benefited a lot from the experience and quickness I gained last year, as well as some library functions that I created to solve standard problems. For example, I no longer have to write out Dijkstra’s algorithm on the spot.

This year some puzzles required some mathematical knowledge, especially Day 22 – “Slam Shuffle”, which couldn’t be solved without mastering modular arithmetic. That turned out to be a tricky one for some participants, but I was actually pleasantly surprised by this type of puzzle. Another one that was particularly interesting was Day 18 – “Many-Worlds Interpretation”. It not only requires a fairly high level of abstract thinking. It is also the puzzle for which most optimizations were needed to solve with a calculation time of less than 10 seconds.

Although I did not succeed in collecting any points on the global leaderboard and the battle for the victory at Xebia was not as exciting as last year, I am nevertheless proud to end the competition at the top of our private leaderboard. I just have to say that I had a lot of fun again (and sometimes a bit of frustration) and I am already looking forward to next year’s edition.