Advent of Code 2019


Advent of Code is an annual competition consisting of 25 Christmas-themed programming challenges. This is my third year in a row participating in the challenge. I treat the event as a personal challenge rather than an interpersonal competition - my goal is always to complete as many of the challenges as I can. I always end up learning some new algorithms as I work on the puzzles. In the past, I've worked in Java because of my familiarity with it, but this year I opted to use Kotlin as a learning experience.

My Favorite Challenges

The contest consists of 25 puzzles, each of which has two parts. The second parts build on the first parts, and are where most of the learning happens, because of their complexity. Many solutions involve famous algorithms, tricky math, and/or solid problem solving approaches.

This year, there were a series of puzzles with a common theme. These puzzles popped up throughout the 25 days of the competition and built on one another. The early puzzles required contestants to implement an interpreter for a bytecode called "Intcode." The first puzzle introduced opcodes for addition and multiplication. Later puzzles introduced input, output, conditional jumps, and comparisons. The Intcode interpreter also had to support large integers, unbounded memory, and 3 parameter modes - "Immediate," "Relative," and "Position," indicating the manner in which opcode parameter values should be resolved.

After completing the interpreter, some puzzles required using the interpreter in various ways. One puzzle involved networking several virtual Intcode machines together with non-blocking communications between them. Others involved providing ASCII source code to the interpreter, running the interpreter, and viewing the output as ASCII text.

I enjoyed the Intcode puzzles primarily because they each built off of the others. This encouraged extendable and reusable implementations of each new feature. I also enjoyed them because they felt like puzzles I could figure out on my own, without relying on a published algorithm.

Another of my favorite puzzles was Day 12. The puzzle involved a simple physics simulation of the velocities and positions of several moons. The velocity of each moon depended on the others via gravitational acceleration. Part 1 was straight-forward and solvable with brute force, but it gave me a chance to learn about operator overloading and data classes in Kotlin (see below). Part 2 involved finding a cycle in the positions of all of the moons. This was more challenging because directly simulating the movement of the moons for long enough to detect a repeat in their positions proved computationally infeasible. Rather, some math was necessary to simplify the problem.

The first insight was that each dimension of the position and velocities of the moons were independent. That is, a moon's x position would never affect or depend upon its y or z positions or velocities. So finding the period of each dimension independently was possible. After finding the periods for each dimension, the period of the 3 dimensional cycle was simply the least common multiple of the cycles of each individual dimension.

In the end, I was able to earn 46 out of 50 total stars for this years contest - I completed Part 1 of every puzzle and Part 2 of 21 out of the 25 puzzles. My solutions are available on GitHub.

Some thoughts on Kotlin

As mentioned above, I chose to complete this year's puzzles in Kotlin as a learning exercise. This was my first experience with Kotlin, and I enjoyed learning and using it.

Kotlin is a JVM language mady by Jetbrains, the company behind the Intellij IDEA IDE. It was recently named a first-class language for Android development. It's statically typed, concise, and maintains interopability with libraries written in other JVM languages. Kotlin's standard library and feature set made it easy to complete puzzles quickly, and its conciseness made it fun to write. Finally, Kotlin's support for lambdas, map/reduce operations, and by-default immutable data types encouraged writing safe, functional code.

One interesting feature I appreciated was the data class. The data class keyword declares a class with well-defined .equals() .hashCode() and .toString() methods. The compiler provides these methods based on the constructor's declared arguments. Not having to write that boilerplate code encouraged me to write multiple small classes since I knew that it would be easy to use them with standard collections.

I also enjoyed using the type conversion methods built into most standard types. These are methods used to convert one type to another. For example, String has a .toInteger() method and Integer has a .toDouble() method. Using these methods over casting or Integer.parseInt(...) has the immediate effect of making code seem more concise. It also improves consistency; In Java there are many ways to convert types, such as casting, .toString() and Integer.parseInt(). In Kotlin, when you want to convert a type, it's clear that you should use some method of the form .to___(). This approach to conversion extends to custom types as well. If you want to convert an Integer into your own custom numeric type, you can extend the built-in Integer class with a new conversion method. This is because Kotlin allows extending any existing type with new methods.

Kotlin is full of many interesting features that enhance productivity and ease of use. I didn't cover many here, but if your interested, check out

  • string interpolation
  • type aliases
  • inline functions
  • automatic casts
  • multiline strings, and
  • the if-not-null .? operator.

I'd recommend that anyone give Kotlin a try, it's a sure improvement over Java.