Advent of Code 2017

This month I wrote code in C++ to answer the Advent of Code questions.

Part 1 - think, research, make and learn

I read about the Advent of Code on Hacker News on December 8, so a bit late to the party. The problems require a knowledge of only basic mathematics and can generally be solved with no more than a few dozen lines of code.

For each problem I tried to think of a way to do just enough to get the correct answer. Sometimes the way to solve the problem seemed obvious. Usually, after reading the problem, I'd spend a few minutes thinking what sort of data structure could model the the problem space and would efficiently support the sort of manipulations that would be needed.

I solved all the problems correctly first time, except day 18 where I made the registers 32-bits instead of 64-bits and didn't notice the overflow and day 24 where I typed in the wrong number by mistake.

The days that stood out to me were

• Day 11 - I wasn't sure how to represent the hexagonal cells so I searched for something like "hex grid distance" and found http://keekerdc.com/2011/03/hexagon-grids-coordinate-systems-and-distance-calculations/ and https://www.redblobgames.com/grids/hexagons/, where I learned of the idea of giving each hexagon an (x, y, z) co-ordinate, which makes distance calculations simple.
  
• Day 16 - When it came to part 2, I estimated my solution would take about 5 days to get an answer on my computer. It took some time staring at the problem and my code trying to think "what am I missing." Eventually the thought occurred to me "what if after one of the iterations the string has returned to the starting state?" Sure enough that's what happens, so the solution was then simple. When it's an artificial problem, like an exam question, you know that there is a solution and if you look long enough you'll find it.
• Day 20 - I spent time thinking about how to be sure the simulation had reached a state where no further particle collisions were possible. Then I gave up and just ran the simulation a load of ticks and saw no more collisions and that got the correct answer. But my solution felt unsatisfying.

Eventually I'd obtained 50 gold stars and felt pretty good about myself.

Part 2 - read other's solutions and learn

Then I looked at the AofC leader board and was shocked. One person solved the first question in 57 seconds. I'm pretty sure after 57 seconds I hadn't finished reading the question. Those guys on that leader board are in a different league.

I looked at the subreddit and the GitHub advent-of-code-2017 tag to find other people's solutions. One can learn a hell of a lot by looking at how other people solved the same problems.

I wasn't happy with a number of my solutions, so I thought I'd revisit some of them. For example, I was particularly unhappy about Day 20, particles. I got two gold stars for my answers, but they were flukes because both parts of my solution were wrong. Here's what I should have done...

To get an answer to day 20 part 1 a quick and dirty algorithm might be

    repeat N times {
        update all particles
    }
    find the closest particle to <0,0,0>

where N is a number you guess at, say 1000 updates. Note that by quick I mean quick to code, not necessarily quick to execute.

To get an answer for part 2 a quick and dirty algorithm might be similar

    repeat N times {
        update all particles
        remove any particles in the same place
    }
    count the particles that remain

Again, N is a number you guess at. Guess too small and you get the wrong answer because not all particles that will eventually collide have yet collided. Guess too big and you'll be pointlessly waiting a long time for particles to collide that never will.

One improvement we could make to the algorithm for part 2 is to repeat not for a fixed number of times, but only until the particle collisions stop. We again have to guess how long to keep updating after the last collision before we decide there won't be any more. Here's the method

    repeat until there have been no collisions for N cycles {
        update all particles
        remove any particles in the same place
    }
    count the particles that remain

These approaches are good enough to get the right answer in the spirit of a fun Advent of Code exercise. Essentially, these were my original solutions, except I had a spurious method to determine N: I thought I need only wait until all particles were headed away from <0,0,0>. It didn't occur to me that, because the acceleration could have a different sign to the velocity, a particle headed away from <0,0,0> could later change direction and head back.

I've also implemented a possible "proper" solution that does not require a guess at a sufficient value for N.

One proper solution to part 1 is to recognise that the particle with the lowest acceleration will be nearest <0,0,0> in the long term, which makes the code very simple:

    find the particle with the minimum acceleration

However, if there is more than one particle with joint-lowest acceleration we'll need to find which of these has the lowest velocity, but only after updating the particles until none of them are slowing down. At that point for all particles their velocity is either stable or increasing and they will never change direction. Now we can look for the particle with the least velocity.

And finally, if there is more than one particle with joint-lowest velocity we'll need to find which of these is nearest <0,0,0>.

What is a "proper" solution to part 2? One idea might be to use the same quick and dirty algorithm, but instead of guessing how many updates we need to do before there will be no further collisions, we keep updating until none of the particles are slowing down, and therefore about to change direction, and then we keep updating until the distance between every pair of particles is either static or increasing. At that point we know there can be no more collisions.

For my input data, my proper solution to part 1 is about twice as fast as my quick and dirty solution. But then again, my proper solution to part 2 takes seven times longer than my quick and dirty solution. The reason for that is that we need to check the distance between every pair of particles, and for n particles there are n(n-1)/2 unique pairs. My input data starts with 1,000 particles. After updating particles until none are slowing there are 542 particles still alive, which means 146,611 pairs. It takes time to check that the distances between all of these pairs is not decreasing.

The code for all my original solutions is in catchpa.cpp here, and the revisited solutions are in january.cpp. It takes 1,191 milliseconds to execute all 49 revisited solutions on an i9-7900X @ 3.3GHz, which I was happy with. But I've since seen Voltara's solutions that run in 195 milliseconds!

Advent of Code was fun and I learned a little more about how to write a program.

index of blog posts