A rusty Advent of Code 2018

Like any year since 2015, when December rolled around my productivity plummeted. It’s time to waste all my hours perfecting a program solving a problem that no one needs solved. Hello Advent of Code 2018. If you haven’t read my previous posts and haven’t heard of Advent of Code before, consider checking them out first. If you just want to see the actual code, you can find it on Github.

My personal challenge for this year was to implement all of the challenges in Rust. I find Rust to be a beautiful language, but I never have a reason to use it. Its memory safety features make sure that when you have a program that compiles, it also pretty much works. Whether it produces the correct answer, on the other hand, is another story. Also, it is most definitely not immune to stack overflow crashes.

I wanted to try to write my code as much as idiomatic rust as possible, and because I’m writing in such a performant language, I also wanted to make sure I do some benchmarking.

Lines of code written per day, excluding shared code

Set up

For the project, I created a single crate to produce a single binary that would be able to handle all the problems. This at least allows for code-reuse, and easy automatic testing. Originally, I was going to benchmark my code using good ol’ time, but then I found cargo bench and opted to use that instead.

Cargo bench is not supported yet in stable Rust, but the bencher crates mimicks it quite well.

To make development easier and to make it feel more like a proper coding project, I created unit tests for pretty much every day using the examples provided in the problem statement. And to take myself even more serious, I used Travis to ensure that my code worked among multiple Rust versions. I chose to support stable and beta rust, and to aim to support the Rust version that Ubuntu ships.

The final binary accepts one argument: the day to run as an integer. It will then read input from the standard input. The -i flag can be used to specify an input file to use instead. The -2 flag will run part 2 instead of part 1. The -t flag will report the runtime of the algorithm. cargo bench dayXX will run the benchmark for that particular day.

Highlights

Not every day is as interesting as the next, but some days require actually being smart. Some days I actually got up at 5:30 CET to get ready for the problems. I am not a bright man at 5:30. Below are some of the things I found interesting. Above, you can see the lines of code that I spent on each day, so you can take that as an indication of how nasty some problems were.

Day 4: Different, but still the same

Part 2 tends to be vastly different from part 1, and generally a more difficult or extreme version. Not today. Below is all of the differences between both parts.

The question was (roughly summmarized): given the sleep schedules of some guards, part 1: which guards sleeps the most, part2: which guard sleeps the longest.

// Part 1
let scores: HashMap<usize, u32> = sleepers.iter().map(|(k, v)| (*k, v.iter().sum())).collect();
// Part 2
let scores: HashMap<usize, u32> = sleepers.iter().map(|(k, v)| (*k, *v.iter().max().unwrap())).collect();

The first one sums, the other one takes the maximum. Briliant.

Day 5: Stacks or something like it

Today, we had to build a molecule, by either annihilating the last atom in the molecule, or appending a new one. Atoms anihilate if they are the same (letter) but different polarity (case).

While string are probably fine for this, I wanted to have an efficient solution, so I figured the following:

• To access the last element of the atom, I will need a stack.
• The size of the stack is at most equal to the number of elements I have currently processed. This worst-case is met when no annihilations take place.

So, we read our input into a vector of bytes. Then we iterate through that vector, keeping track of two pointers:

• a pointer pointing to the character we are currently reading, and
• a pointer pointing past the last element we currently have in the final molecule.

The first one simply walks through the vector. For the second one:

• If the stack is empty, append the current atom
• else, if the last atom annihilates with the currently read one, decrease it
• else, append the currently read molecule.

Then, for the annihilation comparison, I originally had some nice code because Rust has methods like .to_ascii_lowercase for u8. That turned out to be somewhat slow, so instead I opted for the hacky (a ^ b) == 32, which is true for all uppercase-lowercase pairs, and for a random different assortment of ascii values. Those values aren’t in the input, however.

Day 9: Missing standard library features

On the nineth day, the exercise was to simulate some marble game, where you put down marbles in some local pattern, and occasionally remove one. This means we have an ordered collection where we want to arbitrarily add and remove elements. Classic linked list application.

Unfortunately, the Rust Linked List implementation fairly useless, since it doesn’t support either of those things. You can roll your own with a bit of help from the intrusive collections crate, and I did, but it makes for really hard-to-read code.

It turns out, that if you squint hard enough, you realize that you don’t actually need a linked list, and you just need a growable ringbuffer. If you squint even more, you can even see that you can use a double ended queue as just that. Using a VecDeque, my code became three times shorter and two times slower. An acceptable trade-off.

Day 13, 17, and, to a lesser extend, 24

The story-like simulations this year were… not fun. I’ve been stuck for ages by missing “lexicographically first”, “it will not choose if it can do no damage” and such. In my LOC graph, you can see that these days take ridiculous amounts of code and they’re just tedious, not hard. If there are fewer of them next year, I won’t be sad.

Day 18: Hashmaps beat intelligence every day

If anyone enjoys the Conway’s Game of Life, then they will enjoy this puzzle. Our world is a lumbered forest, where lumberyards and open areas spawn according to simple rules.

The challenge for part 2 was to simulate not a few generations, but one billion (or one milliard for my fellow Europeans) of them. The obvious optimization is to see whether you reach a particular state twice. There’s roughly two ways of doing this:

1. keep track of every state you’ve ever seen and when you’ve seen them, or
2. use a smart algorithm to find cycles without an infinite amount of memory.

Initially, I opted for the second option, and implemented Floyd’s tortoise and hare algorithm. It finds cycles with constant memory (your state, twice) and does so reasonably quickly: it finds the lowest N such that N is larger than the number of steps to start the cycle and N is a multiple of the cycle’s length. Doing so, it does about 3N simulations.

It turns out, however, that the cost of simulations is decidedly non-zero. Even with the default HashMap, it turns out that it was faster to serialize the state to a string, and maintain a HashMap of state -> first seen, and just store every single state you encounter. Rust’s string hash (for strings of 2.5k) is apparently really good.

Day 16, 19, and 21: A new assembly language

As with every year so far I think, we have a new assembly language that we need to debug. First we need to decipher it, and then we have two reversing exercises.

Day 19 turned out to be yet another very inefficient way of finding divisors in a large number. But, because reverse engineering it took me ages with the new program-counter-variable stuff, I wrote an ElfSembly to C transpiler that attempted to convert most of the jumps to actual goto-statements, and turned all conditionals into actual if-statements. It works by capturing all writes to the instruction pointer variable, and then checking whether we can (compile-time) see what would be written to that variable. I also cheat a bit; I assume that a conditional is always right before the jump that it controls for simplicity, but that seems to work.

When day 21 rolled around, this compiler allowed me to solve part 1 in about 5 minutes, since GCC managed to completely unroll most of the loops. Which was unfortunate, since I decided to sleep in that day, and only started around 11:00 CET. Part 2 was another curious reversing exercise, encoding what I can only describe as a random number generator.

Day 20: Reversing regex

Given a regex that matches some strings of N(orth), E(ast), S(outh), and W(est). Lucklily, the expressions did not contain repetition, only groups and options. So, we can just keep track of all the positions we could be, and move all of them. Not too hard, but a lot of fun.

Day 22: A* > Dijkstra

Dijkstra’s path finding algorithm is nice for its simplicity and how efficient it is in the general case. Today’s part 2 was not a general case. Dijkstra computes all shortest paths that are shorter than the path to a particular destination. It does so by “expanding” a node in the order based on the distance traveled to get there. Unfortunately, this means that it does a lot of extra work when there are infinitely many nodes so it does a lot of work it doesn’t need to.

A* improves upon exactly this. For the evaluation order of nodes, it not only takes in account the distance traveled, but also an estimate of the remaining distance. For technical reasons, this estimate may not overshoot the actual remaining distance (otherwise, the algorithm may terminate early) but in the case of today’s problem, we can just take the manhattan distance to our goal as this estimate. Using this strategy gets our time down from multiple seconds to a few milliseconds.

Day 23: Where I was lucky and others weren’t

This was without a doubt the hardest problem of the day. And that’s not just me saying that; the leaderboard also took ages to fill, with the last entry getting in at 1:40:41. However, not all problem inputs are created equal, and mine was somewhat simple apparently.

The problem was as follows: given some antennae in 3D-space (each with their own signal radius): what is the is closest point to the origin that is in range of the most antennae.

If your problem input was easy, you could determine the largest group of antennae that had some mutual overlap by assuming that if a group has full pairwise overlap, they have some mutual overlap. This, however, is only true for manhattan spaces up to 2D as quite a few people on Reddit have proven.

Ignoring that completely, the assumption above reduces our problem to a max-clique problem, for which various algorithms exist. I implemented Bron—Kerbosch version two, but most other algorithms should work.

When you have the largest clique, the minimal distance from the origin (which was the quetion) is located on one of the origin-facing sides of the antenna whose radius is furthest away from the origin. The actual distance is then easily found as the manhattan distance of from the origin to that antenna, minus its radius.

Of course, the method described above is completely wrong, and apparently you were supposed to solve this using Satisfiability modulo theories and then plug your work into some general purpose solver, but I find that to be cheating.

Implementing my max-clique algorithm, I once again stumbled across a shortcoming of Rust, being that I cannot remove elements from a collection while I’m iterating it. Especially when the element I want to remove is my current element. This results in one additional .clone() in my implementation.

Performance

I’ve discussed performance quite a bit above, but left out the actual metrics. Those are here:

Measurements were taken on the Travis runner, using the bencher crate. Day 21 part 1 and day 25 part 2 can serve as the baseline. The latter does nothing, and the former is actually solved compile-time, reducing the work to a single .to_string() operation.

While the error bars don’t show too much on this graph (it is logarithmic after all) there is a large variance in the runtime’s standard deviation relative to the average runtime for a particular day. The days that suffer the most from this are the days that make extensive use of hash maps.

Rust’s hash-maps are non-deterministic: a value’s hash varies over different runs. This is intentional, and is a mitigation for collision attacks which can be used as an attack vector for DoS attacks. However, this also means that the number of collisions that I suffer is non-deterministic, thus creating wildly varying timings.

Looking through the most costly implementations with perf, we can see that in pretty much all cases most time is spent computing hashes. This is because Rust’s hash is not very efficient for short keys, such as integers. There are alternative hash implementations — such as the fnv crate — that can be dropped in as a replacement hash, but then I would have to add yet another crate for no fundamental reason. In one case, I managed to boost performance by not #[derive]ing the hash function, implementing it myself so I could merge two fields. That somewhat worked, but also added quite a few lines of code.

Final thoughts

Once again, I’ve thoroughly enjoyed the Advent of Code, and will be competing next year. Rust has been a nice companion. On some days, I could get away with a slow algorithm since my Rust’s performance would compensate. On other days, I noticed that I’d rather be using Python so I could code with more hand-waviness, since my code has been quite long this year.

Overall I’ve learned a lot about Rust and need to find a new project to work it into. Any suggestions?