Advent of Code 2020: Day 12, 8 min read
advent of code 2020
Your ferry made decent progress toward the island, but the storm came in faster than anyone expected. The ferry needs to take evasive actions!
Unfortunately, the ship’s navigation computer seems to be malfunctioning; rather than giving a route directly to safety, it produced extremely circuitous instructions. When the captain uses the PA system to ask if anyone can help, you quickly volunteer.
The navigation instructions (your puzzle input) consists of a sequence of single-character actions paired with integer input values. After staring at them for a few minutes, you work out what they probably mean:
Figure out where the navigation instructions lead. What is the Manhattan distance between that location and the ship’s starting position?
You can read the full text here. This is a classic advent of code puzzle. For this puzzle, our input describes some instructions on how the ship should move. We just need to set the ship up at the correct starting location, pointing in the right direction and propagate through time. It isn’t essential to load all of the instructions into memory, we could read and process them one at a time. However, it’s Saturday, so for an easy life we’ll put them into a
vector in case it is useful for part 2.
The initial code to load and parse the instructions is quite simple:
The first value in the line is the letter for the instruction, the remainder of the line is the number of times to repeat it. We are using a
pair’s which are data containers I find really useful for advent of code puzzles. Now we just loop through these directions and process what we should do next,
The code above processes the five simple instructions. We have “N”, “S”, “E” and “W” in which we just simply step in the direction. I’m taking the first value of my
pair as the E-W axis, and the second value as the N-S. The final instruction above just moves us in the direction we are facing, which initially is East.
The 2 more complicated instructions are below:
In this code I’m trying to do 2D rotations while avoiding doing any maths so I have all of the possible 2D directions in a
list. There are other 2D directions possible, but we start facing East and only ever rotate in increments of 90 degrees.
A right turn corresponds to iterating to the next direction in the list (forwards), and conversely, for a left turn, we iterate left (backwards). The only complication is dealing with the edges, where we must wrap around to the other side of the
We just have to loop over this
vector of inputs, move our ship and finally calculate the distance we have moved from the origin,
and that’s it. The first ⭐!
Before you can give the destination to the captain, you realize that the actual action meanings were printed on the back of the instructions the whole time.
Almost all of the actions indicate how to move a waypoint which is relative to the ship’s position:
After these operations, the ship’s Manhattan distance from its starting position is 214 + 72 = 286.
Figure out where the navigation instructions actually lead. What is the Manhattan distance between that location and the ship’s starting position?
You can read the full text here. This is a little more involved. I prefer to imagine this waypoint as a direction vector that the ship is travelling in when we say forward.
The movements “N”, “S”, “E” and “W” haven’t really changed. However, except moving the ship, we now move the waypoint.
Next we must change the forward direction such that the ship moves along the direction that the waypoint is pointing in:
Now, with the easy parts out of the way we need to do 2D vector rotations on vectors that don’t necessarily point along an axis (as they did in part 1). I decided to deal with this by writing a floating point 2D vector rotation with sin and cosine functions, and then integerising the output. This is not the most elegant way of performing the rotation, but it was quick to implement. The final two steps are:
We just invoke the quick, dirty rotation function and update the waypoint vector such that it now points in the correct direction. That’s it ⭐⭐!
I think the solutions we have implemented today pretty much optimal, other than the fact we load all of the instructions into memory; instead, we should process them one at a time and discard.
Our solution for both parts of the problem scales as
O(N) for both time and space complexity. This can easily be reduced to
O(1)-space. Other than that, there isn’t too much more optimisation to discuss today, the algorithm was straight forward.
I think my code could have been more readable. Chained
if statements are not the easiest to read, and my rotation function is a little ugly. I might try and improve the clarity if I get bored tomorrow.
I have no affiliation with AoC. I’m just a fan of the programming puzzles. If you enjoy them too, please feel free to join in and support the creators