AoC 2021

This year was one of the best since I started doing Advent of Code.
The quizzes have been mostly interesting yet not too expensive in terms of time, with the exception maybe of the last week; in general, the challenge level was increasing every week, with a steeper increase on the last one.
This year I was not able to make any “decent” classification, but I think this is normal, given now the huge success of AoC and the amount of people participating. On the plus side, my sleep deficit never increased too much :)

Unfortunately, I failed my goal to blog about it every day, so I will try to put something from my memory.

Day 1: Sonar Sweep

A nice start. The first part, just an application of the pairwise iterator, which is maybe the most used of the itertools recipes. As a matter of facts, since python 3.x, it’s part of the standard library as cxx, but I already have it as part of the “common” tools, so I still used the recipe version.
The second part was just an implementation of the moving average. I am pretty sure there is already something like that, still I found it easier to implement it myself.
As a matter of facts, there is a recipe for the moving average using deque and itertools:

from collections import deque
import itertools

def moving_average(iterable, n=3):
    # moving_average([40, 30, 50, 46, 39, 44]) --> 40.0 42.0 45.0 43.0
    # https://en.wikipedia.org/wiki/Moving_average
    it = iter(iterable)
    d = deque(itertools.islice(it, n-1))
    d.appendleft(0)
    s = sum(d)
    for elem in it:
        s += elem - d.popleft()
        d.append(elem)
        yield s / n

Day 2: Dive!

The second day reminded me of classic AoC puzzles, but it was still on the easy side.
The problem were very similar – which is not so common in AoC, with the second being just a small complication on the first. Still, I was able to use the same approach in both, which involved using the command pattern.

I am describing the solution as “command pattern”, but I used an imperative approach, with no OO. Not that OO would have bee na bad idea; but of AoC it’s usually slower in the implementation, with no discernible advantages. Still, I think the concept was the same, with just a different way of dispatching, so I am still using the “command pattern” name.

Day 3: Binary Diagnostic

The second part proved to be much more complex than the first one, more than I could actually expect; especially, I had .
Generally, the solution relied a lot on binary to decimal trasnformation, which actually means “interpret a string as a binary number”. I always hated this kind of exercise, so I was initially a bit scared, but turns out that python – as often happens – already got me covered: int("0100", 2) will convert a binary representation.
It turned out to be very useful, also in other days.

Day 4: Giant Squid

Approaching this one, I feared about time complexities. The naive solution is clearly a O(n2), so it was easy to have a second part exploting that fact.
Still, I decided to go for it; the reason was more to have a way to clarify the requirements, since it was a bit complex (especially when waking up at 6am!).
And, actually I was lucky, because second part was just a slight complication.
Extra bonus fun was then refactoring the code, to remove the duplication between the two solutions – I liked, because the refactored approach separates quite neatly the various concerns: playing game and what to do in case of victory.

Day 5: Hydrothermal Venture

A simple one; however, it took me quite a lot of time, because of stupid mistakes while marking the vents – like counting diagonals incorrectly, and similar. I liked that the second part was clearly a minor addition on the code written for the first part and there was no need for further refactoring after completing the exercise.

As a side note, it’s clear that I need to improve my knowledge of regular expressions. Whenever there is some parsing, I am always a bit afraid to use regexp, even if the input is guaranteed to be in a certain fixed format.
Of course, I do know them, and I am quite fluent; but I am not confident enough to use them as much as I would like.

Day 6: Lanternfish

This was quick – less than half an hour to finish.
Once I decided to use Counter and parse the input data using it, everything else was quite straightforward.
Also, the second part was almost a noop; most probably, had I used a different approach, it would have caused an explosion in complexity; however, here, it was just a matter of changing one constant.

Day 7: The Treachery of Whales

Another quick one.
It was clearly an optimization problem; for a reason I did not fully analyze, the first part involved just calculating the median; so after a while, I just tried, and it worked.
The second part instead required using some weighted average; at first, I was again thinking about some general approach, then I tried to just brute force it and calculate all possible solutions. Turned out it was quick enough, so I did not try further for a better solution – which I know exists, but I am not sure it’s a field I want to investigate.

This one took me quite a long time to understand. For the first part, I decided to use some shortcut – as suggested in the text, on the other hand – so it was relatively simple to do, just some effort in parsing the data.
However, the second part required understanding the full description, and it took me a lot of time. To be honest, this was the kind of exercise I dread the most; on the other hand, this is also a good exercise for daily job.
Anyhow, this was the first exercise requiring some whiteboard analysis. The final solution was essentially brute-forced; but it was fast enough, and the code is actually quite nice – albeit a bit too terse, and for this reason, in need of some documentation.

Day 9: Smoke Basin

Here, I had immediately an idea – I should use NetworkX.
NetworkX is a wonderful python library for working with graphs, and it has already served me several times during advent of code.
Unfortunately, I seldom use it; as a matter of facts, only during AoC.
And this is unfortunate, both because I am in love with this library and I would really love to use it in my daily job, and because I completely forgot about its usage.

For this reason, I decided that the first part of the problem was simple enough to solve it directly using a dictionary; but the second one (recognize the largest trees in a forest) I felt that it was screaming to be solved using a better graph representation.

So, I had to read quite a bit of the documentation (and of my previous usages in old AoC code) to make it working; still I had to somehow implement a function to recognize the largest trees in a forest, which I am pretty sure is available somewhere in there.
That said, I am happy to have used it, since it allowed me to model the problem in a cleaner way.

Some day, I have to write a post about basic NetworkX usage :)

Day 10: Syntax Scoring

A typical AoC puzzle.
The solution was pretty simple, you just have to maintain a stack.
Also, the second part was very similar to the first one, allowing to immediately reuse the code there, with just a different rule to calculate the result.

Day 11: Dumbo Octopus

This one tricked me!
Today’s exercise is a clear variation on the game of life; as such, I thought it would have had the classical two-step approach, where the first step is relatively simple, and then the second step would require some optimization technique to escape from the algorithmic complexity.
So, during implementation, several times I stopped thinking about a possible better approach, then postponing it for a second iteration.
And then… the second iteration never arrived. I just had to try, and actually the pattern converged quickly enough to a solution.
It was definitely one of the most anticlimactic exercises I have done in AoC :)

Day 12: Passage Pathing

Graph, paths: I immediately thought (again) at NetworkX. However, it looks like there’s no such functionality in there; I spent quite some time searching for it, but with no result. So I had to implement on my own – just your typical depth-first traversal algorithm.
I still used NetworkX to represent the graph; however, navigate through it was non-trivial, and required some learning, and the documentation was not clear for me. Again, I think that I need to write about it, so that next time I will remember how to use it. In particular, in NetworkX, a graph is a dictionary-like structure, where for each node you get the list (sequence, actually) of all neighbours.

The second part was just a small variation of the first, and came out very quickly. I just did a copy-paste of the code, and then refactored in a second moment.

Day 13: Transparent Origami

Another nice puzzle. For the second part, I cheated a bit, and skipped the OCR phase, instead transcribing the result manually. Thanks to that, the second part took me just few seconds.
However, a quick ddg search revealed a package doing exactly that: advent_of_code_ocr – which as the name implies, was created exactly for AoC. And it worked just fine, allowing to improve the code. A nice tool to add for next year’s AoC, and kudos to @bsoka for sharing it!

Day 14: Extended Polymerization

This was the first day requiring some extensive amount of time.
The first part was relatively simple, but it was also clear how the complexity would have been increased.
Anyhow, I tried the naive approach – few days before, it worked anyway. This time, no luck.
Eventually, I went for a completely different path – even parsing data in a different way, representing data differently: no longer as a string, but as a counter with all existing tuplets.

The naive implementation was just iterating over the string, splitting into tuplets, and inserting the correct new letter. With all my efforts, the memory complexity of this solution was simply too high, so eventually I had to give up.

Eventually, a new approach dawned on me: we are only interested in counting the possible pairs (“elements”), and we are not really interested in their order. Also, there is a limited number of possible pairs.
So we can just take the single instance of the pair and the number of times it appears; and then we can just move on from there.
I like this new solution quite a lot; the only problem is that the code is not very readable, but with such weird requirements, it’s difficult to make some sense in it.

Day 15: Chiton

Another one solved using NetworkX. It was clearly a Dijkstra exercise on a directed graph, where the weight of the edge was the “risk level” of the target node.
The second part would have been straightforward… if it weren’t for some silly bug I introduced; and when it was taking too much time, I wrongly interpreted it and tried to analyze performance, instead of functionality.
That said, it was a nice exercise, and again, NetworkX was a huge help.

Day 16: Packet Decoder

This is not really my favourite type of exercise; it’s essentially an exercise in parsing data according to a specification. And there are always some small items in the specification (in this case the padding) that are somewhat obscure and you have to guess, and try to fill with your interpretation.
I always felt weaker in this kind of exercise. I still remember reading the BMP file format specification, and feeling a sense of panic at it. Well, here it took me quite some time to do, but eventually I did it; moreover, the approach was good enough to quickly manage the second part as well, with almost no additional code required.

On the learning side, I had finally the chance to play a bit with python’s __new__ protocol. I am not a fan of classmethods, and usually, I try to use staticmethods, or even normal functions whenever possible However there are cases where classmethods make sense. In this case, I implemented a factory using it; and the result is actually definitely nice. Essentially, __new__ get the class as input; but it is not really required to use it; and then it can alter it and force a different one.
This turned out to be a nice trick, something I think I will use in the future, as a more pythonic way to implement the abstract factory pattern.
For example, where “Base” is also acting a fallback implementation:

class Base:

    def __new__(cls, *args, **kwargs):
        behavior = args[0] or kwargs.get("foobar")
        if behavior == 'foo':
            cls = Foo
        if behavior == 'bar':
            cls = Bar

        return super().__new__(cls)

class Foo(Base):
  pass

class Bar(Base):
    pass

Day 17: Trick Shot

A quick one. It is a clear homage to the old theme of the artillery games, of which I remember especially my experience with Scorched Earth.
Also, it reminded me an evening, spent coding with friends in a kind of code competition, writing some AI to play the artillery game against each other. We lost, and by good margin, but it was fun.

As usual in this AoC, I tried the naive solution, knowing it was for sure good enough for the first part, and at worst, could give some good hint for the second part. Actually, the approach was fast enough to be used even for the second part; eventually, I optimized it with a smaller range to search for all trajectories, so that it could always run in the runner. I could optimize it automatically, but I was happy it could be finished in few minutes, so I did not investigate further.

Day 18: Snailfish

This was one of the hardest, like the fourth hardest, and required a lot of time to solve; fortunately, the second part was just a small increase in complication.
For some reason, the “explode phase” failed my attacks for long; my final approach, while working, still looks way too complex. I am pretty sure there is a simpler and better approach, most probably modeling data in a different way.

This is the first time when I had to write a fairly amount of test cases; and it was good that there was enough examples to create them. I was tempted to add pytest to the project, but eventually let them as simple ad-hoc functions.

Day 19: Beacon Scanner

Another tough one, at least for me. This is one of the areas where I know I am weaker; and all the rotation matrixes were quite difficult to derive and use.
Maybe, if I had added numpy as dependency, I could have done it much faster; but I did not want to learn it now. Also, the solution is clearly suboptimal, as it’s way too slow. But hey, it works :)

Day 20: Trench Map

A relatively easy one. The pattern here is a common one, à la Conwayàs game of life: create a function calculating the next iteration of the “map”, and then if necessary discard the previous one. In this case, the algorithm was actually quite slow; fortunately, it was not so slow to require improvements or rework.

Day 21: Dirac Dice

Again, it was clear that the first part was just an introduction for a second part with an impossible algorithmic complexity. And that happened.
I worked quite long to make it work, but with no success. Then I tried to just cache it, and much to my surprise, it simply worked. For the cache, I leveraged the excellent functools.cache decorator: just one line of code, and I got a simply working memoization.

Day 22: Reactor Reboot

We are now entering the last phase, with exercises that were much harder, and I had to systematically interrupt in order to do other stuff. Like, work, or Christmas – sometimes I wonder why people expect those to be more important than AoC.

In this case, the second part required a completely different approach than the first one. Finding it required quite a lot of whiteboard work (where I simplified the problem to a 2d representation), but it was eventually a satisfying experience. Tiresome, but satisfying.
I have then refactored the code, using only the new approach also for the first part; with the new approach, it turned out that the first part is slightly more complex than the second :)

Day 23: Amphipod

This was one of the most challenging, but at the same time my favourite.

The solution was clearly a matter of finiding the shortest path on a graph; however, defining the graph and the weight was not a trivial task. Defining all possible states was out of question, because of the sheer number; and then, I was struggling on a good definition.

The general idea was simple: this is a graph, where the start is the initial state, and the end is the desired state. Then, we just need to use something like A* to go from one state to another; we need to generate available states (movements) and costs.
In particular, we need to:

  • Represent the state in a good structure
  • Implement the “move”
  • Implement the pathfinding algorithm

Initially, I wanted to use NetworkX, but then, defining the graph dynamically would have required some non-trivial work with generators and memoization; eventually, I simply started to implement the Djikstra algorithm (which, using python’s heapq become a trivial matter) and create the state and its cost on the fly. The algorithm is a tad slow – and unfortunately that slowness hid some bugs that took me quite a lot to find – but it works in a reasonable amount of time.

And that was an issue, because I did not implement all requirements!
In the short version it worked fine, but it took a lot of debugging (and time!) to understand that the longer version was no longer working!

Definitely my favourite exercise, and solution, for this year’s AoC.

Day 24: Arithmetic Logic Unit

I knew this was the last day with a complex exercise; and actually it was maybe the most complicated one.
Also, it was a weird one, with little or no test data, and that had a “mathematical” solution. I tried to explore using a solver like S3, but it was definitely out of question in such short timespan. Eventually, my implementation was correct; and again, it was just had some trivial bug preventing it to find a solution. Once fixed the bug, it started converging reasonably fast – even if it’s still a “slow” one – by far the slowest of the bunch.
Note that there are better approach, and I checked a couple of them; they find a solution much faster than my approach. Still, I am not sure that I completely understand them, as they use some relationship within data that somehow require a different kind of analysis.

Overall, not really my favourite exercise; the fact that I had to finish it using breaks during Christmas dinner did not help. That said, I have to admit that the “decompiler” part was indeed quite fun.

Day 25: Sea Cucumber

For the last day, as usual we have only one part, with the second just checking that the all the previous ones have been completed. It was also quite an easy one, with yet again the same kind of pattern as in day 20, with the additional complexity that now each iteration is actually split in two parts with different rules.

And with this, even this AoC has been completed.
Overall, a better experience than last year, and one of my favourite – not too demanding, and more on the “fun” side.

Main take-aways for this year:

  • Become more fluent using regular expressions.
  • Better at linear algebra. Not sure if it will have an impact on anything else than AoC, but I always felt that as something I forgot too fast.
  • heapq is an underrated module in standard library.
  • NetworkX is cool, and I need to becoem a bit more proficient with it.

I am looking forward for next year!