Advent of Code - 2019
The Advent of Code is a yearly event where people compete to solve 25 algorithmic problems during the lead up to Christmas. Below are a brief description of each problem I solved and my analysis and solution for that problem.
Day 1
Day 1 was a gentle introduction to this years competition. The problem was to read in numbers as input, calculate some function of that number, and output the sum of all the functions. Nothing much else to do about this one, except to do it.
Day 2
Day 2 on itself was not too difficult of a problem, however, it did setup for me to be brought low when the intcode computer returned on Day 5. The problem was to implement an emulator for the intcode computer specification given in the problem. On the face of it this problem seems intimidating and is definitely in contrast to the simplicity of the first problem. Though, once you sit down to actually implement the problem it all comes together fairly easily. I did spend some length of time thinking if there was any better way to determine the state of the intcode computer without directly emulating it, before coming to the conclusion that it was probably undeciable.
Day 3
Today’s problem was to find the intersection of two curves in a 2D plane that minimized some metric. For this problem I’m not sure of the most efficient way to approach it (although I think it might involve a Segment Tree), but I see two approaches that are good enough for the problem set. The first compares each straight line segement of both curves pairwise, and determines mathematically if they intersect. The second traverses the first curve and stores every point it passes through, then it traverses the second curve checking to see if it passes through a point that the first curve also passed through. The first solution is better for few, long curve segments and the second is better for many, short curve segments. In the moment I ended up settling on the latter approach.
Day 4
Today’s was a stark change of pace, being relatively short and simple compared to the 3 days previous. The goal was to find how many 6 digit number sequences between two given bounds satisfy a set of constraints. I suspect that there is alot of room for finesse in executing this problem, however, the brute force solution of checking every candidate number was easily fast enough for this case. For my final program I settled on a recursive algorithm which generates numbers that satisfy one of the conditions to further shrink the search space. I suspect it is possible to calculate the answer in constant time with a closed form equation, using a combinatorial argument, but coming up with the equation looks like it’d be very unpleasant.
Day 5
As I foreshadowed on Day 2, Day 5 was the day I was brought low. The problem was to implement additional addressing modes and operations to the intcode computer introduced in Day 2. In theory this should have been simple enough, the new operations could simply added into the main switch statement and a couple if statements should be a sufficient, if unwieldy, solution for addressing modes. What followed was a number of errors bought about by hasty and unwieldy design choices and misunderstanding of the problem task. First of all, wrapping each parameter in an if statement to handle the addressing modes proved to be much more unwieldly and repitious than expected, and in hindsight could’ve been very easily moved into a funtion. Next, my choice of handling for addressing modes also led me to apply my arithmetic operations in parts, first overwriting the target memory address and then adding/multiplying that memory address. This is a terrible idea, as many operations want to read from a memory location and write back to it afterwards, so overwriting it’s value in the middle causes problems. Finally, my misunderstanding of the question lead me to waste time on an obviously wrong answer to try and work out the trick. The critical line in the problem statement was, “Non-zero outputs mean that a function is not working correctly; check the instructions that were run before the output instruction to see which one failed”. When I read this I thought the problem was asking me to modify the instructs prior to the outputs to make them all 0, where actually an output of not all zeroes is just plane wrong. This was a great source of confusion for me for a while.
Against all odds, I managed to cobble together a passing solution. However, at this point it is abundantly clear that my first passing solution is sorely in need of refactoring. Here, for your viewing pleasure, are both versions of my solution.
Day 6
Entering Day 6 I was slightly concerned as the word on the street seemed to be that this day was the great filter. That, in the past, Day 6 had been the difficulty break point that culled the weak once and for all. Todays problem was, given a tree representing planets and their orbits, calculate the total number of direct and indirect parent child relationships(orbits) in the tree, and the distance between two specific vertices. Being that the first five days of problems were more ad-hoc or mathematical, I can see why the shift to more traditional competitve programming problems would make a tonal shift for the competition as a whole. The kid gloves are coming off. The problem itself was fairly standard, first I ran a BFS through the tree starting from the root to calculate the depth of every vertex. Then, the total number of orbits is given sum of the depths of every vertex. Next to find the distance between two vertices we first find their lowest common ancestor, then the distance between them is given by the sum of the differences in level between the ancestor and the two vertices.
Day 7
Once again we see the return of the intcode computer. And once again I have not had the chance to properly tidied up my implementation of it, and so once again I am left to continue to build this tower of spaghetti code higher still. Although, even if I had taken the time to refactor Day 5’s creation I’m not sure how helpful it would have been, as todays problem required the ability to create multiple intcode computers, chain them together, and run them in “parallel”. As a Go programmer I probably could’ve made a very elegant solution for this using goroutines and channels, unfortunately I’m not familiar enough with Go’s concurrency to whip it out on the fly like that(but watch this space for a potential future concurrent implementation). Instead I quickly coded up a computer type and did a crude impression of blocking IO to maintain all the computers in parallel.
Day 8
Keeping with what seems to be this years pattern today’s problem was realtively short and simple, probably to give everyone a brief reprieve from tomorrow’s intcode problem. In this problem you had to read in a image given in several layers, and determine what the final image is. Thankfully the image dimensions are given to you as part of the problem, which means the crux of this problem is being able to parse the image into distinct layers. I did this by treating the images as flat, so I could parse each layer with a simple for loop. The real question left after today is will intcode really comeback tomorrow, and if so, will I be able to fixup my current intcode implementation before then?
Day 9
Just as predicted Day 9 saw another return of the intcode computer, and even though I saw it coming, my intcode emulators remains just as unwieldy as always. Luckily, today’s additions were small and simple. The addition of a relative addressing mode, alot of typing but nothing we haven’t seen before, an instruction to manage the relative base address, and the ability for the program to extend into memory outside of the size of the original source code. That last quality is the one that has the most play to it, my first thought was to keep memory as a slice, and just extend it everytime we access uninitialised memory, however for the sake of brevity, and potentially some memory savings, I opted to replace the slice with a map. This meant I could keep all my other code the same, and any out of bounds memory accesses would just add keys to the map. Interestingly, the second part of this problem was very basic, only requiring a change of input. According to the problem description this is the final form of the intcode computer, so if I’m lucky this is the last we see of the intcode computer and I can put this monster to rest.
Day 10
Today’s problem proved to be a bit of a stumbling block for me. Most of the problem came from alot poorly remembered linear algebra. The two key challenges in the problem are being able to calculate line of sight from a point in a 2D grid, and ordering points based on their argument. Rather than solving these problems with floating point numbers, like using trigonometry I instead opted to use linear algebra to avoid floating point errors. The first step can be solved using the dot product to check whether or not two points are colinear, while the second can be solved using the crossproduct to determine relative positioning of points. After much time and effort this lead me to my final solution, however, I’m pretty sure it’s not 100% correct and I just managed to fluke the right answer. As such I think todays problem is another good candidate for a revisit and tidy up after the competition.
Day 11
After a brief hiatus from doing these write ups, I’m back to, hopefully, finish giving my thoughts on this years advent of code problems. At this point the competition has been over for a couple of weeks so my recollection of some problems may be sketchy, but we push on undeterred. For todays problem we were required to simulate the movement of an intcode robot painting a 2D grid, first to determine how many cells it paints atleast once, and to determine what it ultimately paints. I opted to represent the grid using a map from integer pairs to an int representing that cells current colour. This is nice as it means all the cells which aren’t touched by the robot are zeroed by default, and to find the number of painted cells by checking the length of the map. However, this approach makes it slightly more complex to output the final state of the grid, as we have to manually track the the bounds of the grid, ie the most distant cell the robot has painted in any direction, before we can print it. This also led to some confusion as these bounds are doubly inclusive, instead of the usual inclusive-exclusive, but otherwise the implementation is straightforward with a working intcode computer.
Day 12
This problem was a big step up in difficultly and the first time I had to consult the Advent of Code subreddit for inspiration on how to proceed. The problem was a simplified version of the famous n-body problem in physics, in this case for 4 bodies. In a nutshell, the problem is to simulate the movement of a number of bodies. Each body has a velocity which changes according to the positions of the other bodies in the system. The first part of the problem was relatively easy, requiring us to simulate the system for 1000 steps and then calculate the final energy of the system. The second part is where the difficulty sets in, requiring us to find how long it takes for the system to return to a state it has been in previously. This part had me stumped for quite a while as the period of this system is so long that finding it by simulation is infeasible, and I wasn’t about to solve the n-body problem analytically. There were two key insights I got from reddit that enabled me to do this problem. First, each of the axes in the system is independent of eachother, so if we can find the period of the system along each axis individually then we can compute the total period as the LCM of each axis period. And second, each state the system can be in has a unique parent, this means that the first state we will see repeated is the initial state. With this in mind we can simulate the system until we have seen a loop in each of the axes and then return the LCM of all these to get the overall period. In the below solution I use the big library for this last calculation, however, I did this in an attempt to fix an unrelated error, and suspect it’s not necessary.
Day 13
In Day 13 we added display functionality to the intcode computer. In line with this, the first half of the problem was to count how many tiles of a certain type the computer drew to the display before it exited. In the second part you then had to use the display to beat a game of breakout. This was another situation where my somewhat hacky intcode computer caused problems for me as it made it hard to order input to the computer inbetween output to the screen, as the compute function must take some input to run, even when the intcode computer isn’t reading it. This meant I very quickly gave up on trying to win manually and made an AI to play the game for me. For those who are wondering, I did eventually end up rewriting my intcode computer and I expect that version would’ve worked much nicer here.