Advent of Code 2020

Last year I was lured into participating in Advent of Code, a programming contest/challenge that presents a two-part puzzle each day during December until Christmas proper, just like an advent calendar. This year, as it turns out, I was active in luring other people into participating.

I like the concept because it can be as competitive as you like (in my case, not at all) and you don't have to complete one day's puzzle to be able to see the next one. It's fun to discuss the problems, solutions and possible optimizations and implementation variations with friends and colleagues.

A bit of code

Warning: This code is "as-is", complete with wonky formatting, glaring flaws, messy design and spurious comments. Most solutions are spur of the moment, "stream of thought" code geared at solving the problem at hand. They're not written for beauty, maintainability or even for being the very best solution.

• Day 1, solved in Python 3.
  Not much to say about this, a basic warm-up task, although I also experimented with a binary search.
  I also solved part one of this task in pure Amiga Shell script, which is a lot more finicky than it might sound at first.
  I also did a third solution for part one in Ivy, a sort-of-APL for people with normal keyboards. The code is here. The input was parsed with awk:
  awk 'BEGIN {s="input = "} { s=s" "$1; } END { print s }' < 1.raw > 1.ivy
• Day 2, solved in Python 3.
  Not much to say about this either. A pretty standard solution, I think.
• Day 3, solved in Python 3.
  This one is pretty run-of-the-mill too, I think.
• Day 4, solved in Python 3.
  I actually got the answers using a slightly less polished version of this, with a combination of regular expressions for extracting the data and some lambdas for checking intervals. Then I decided to spend some time on it and do all the validation using regex. I can always use more regex practice.
• Day 5, solved in POSIX sh.
  The first part of this day was so perfect for a shell pipeline I just had to solve it with one, and part 2 was easily solved by adding a short function at the end of the pipeline.
• Day 6, solved in Python 3.
  Nothing special here either. I think I could've gotten better performance by not solving both tasks in the same loop, but then I wouldn't have solved both tasks using the same loop.
• Day 7, solved in Python 3.
  Really fun day! Here I used a DAG with bidirectional lookup to describe the relations between bags, and a dict to store the mandatory amount of child bags in each parent bag. I think it worked pretty well.
• Day 8, solved in Python 3.
  This is clearly over-engineered. Remembering last year's IntCode computer, I feared we'd see a repeat this year and prepared myself with a proper class. Turns out I was wrong, but that was actually a bit of a relief.
  The second part was solved using the Ken Thompson method: "When in doubt, use brute force."
• Day 9, solved in Python 3.
  At first I used a deque here, but after some measuring, it seems lists are just as performant for this case, so I switched. Other than that, nice with a bit of code re-use from day one.
• Day 10, solved in Python 3.
  Another fun day! Things certainly got a bit trickier. Once more I decided to use a DAG, this time to represent all possible combinations of adapters.
  The combinations are too many to count with simple recursion, but since there are so many repeating relations, using memoization/dynamic programming to store already traversed paths is really fast.
• Day 11, solved in Python 3.
  As a programming task, this kind of cellular automata is mostly busywork. As an homage to John Conway, it was a nice inclusion this year.
  Since the program runs kind of slowly, I decided to add a little easter egg of sorts. A few messages are printed on screen in an attempt to amuse anyone waiting for the actual result.
• Day 12, solved in Python 3.
  This felt like more busywork. As someone not very well-versed in trig or complex numbers, I found the pattern for doing rotations by drawing a bit on paper.
• Day 13, solved in Python 3.
  A tricky day, but also educational and fun! When inspecting the bus lines and playing around with the generated values in various ways, I noticed they were all primes. This eventually led me to the Wikipedia page about the Chinese Remainder theorem.
  This page consists mostly of dense mathematical prose and a large portion of the Greek alphabet, neither of which I'm very comfortable with. So I simply stole the code from Rosetta Code.
• Day 14, solved in Python 3.
  Even though I'm using strings for this, it runs faster than a lot of solutions I've seen that actually twiddle with the bits proper. I'm reasonably pleased; this isn't one of my stronger areas.
• Day 15, solved in Python 3.
  Using a pre-filled list of integers instead of a dict speeds things up considerably. Even though the list is likely to be larger than needed, according to my completely unscientific measurements using htop, it seems to compare pretty fairly memory-wise as well. I also did a quick hack in C which of course runs much faster.
• Day 16, solved in Python 3.
  This solution could certainly be shortened by at least one step. I was starting to feel a bit burned out when I sat down with this task; writing it felt more like work than play.
  Because of this, day 16 will be my last solution for AoC 2020, at least for now. It was a fun year this far and I see no reason not to check it out next year, too.

2021-10-23: Decided to give a few of the remaining days a shot to see how I felt about doing them, testing the waters in preparation for AoC 2021. Not too bad but also not overly inspired. The jury's out, for now.

• Day 18, solved in Python 3.
  A fairly naïve approach, counting parenthesis and recursing until the innermost is found, evaluating it and then continuing by doing the same with the remaining expression.
• Day 19, solved in Python 3.
  I for one think a 461,514 character regular expression is perfectly reasonable. Don't you?