Advent of Code 2020: Day 12

, 8 min read
advent of code 2020

Part 1

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:

1
2
3
4
5
6
7
8
    Action N means to move north by the given value.
    Action S means to move south by the given value.
    Action E means to move east by the given value.
    Action W means to move west by the given value.
    Action L means to turn left the given number of degrees.
    Action R means to turn right the given number of degrees.
    Action F means to move forward by the given value in the
	direction the ship is currently facing.

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:

1
2
3
4
5
6
7
std::vector<std::pair<char, int>> directions;
std::fstream myfile("input", std::ios_base::in);
std::string line;
while (std::getline(myfile, line))
	directions.push_back(
		{line[0], std::stoi(line.substr(1, line.size() - 1))});
myfile.close();

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 vector of 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,

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
std::pair<int, int> pos = {0, 0};
for (auto d : directions) {
	if (d.first == 'N')
		pos.second += d.second;
	else if (d.first == 'S')
		pos.second -= d.second;
	else if (d.first == 'E')
		pos.first += d.second;
	else if (d.first == 'W')
		pos.first -= d.second;
	else if (d.first == 'F') {
		pos.first += (*current_dir).first * d.second;
		pos.second += (*current_dir).second * d.second;
	}
}

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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
else if (d.first == 'L') {
	int num = d.second / 90;
	for (int i = 0; i < num; i++) {
		if (current_dir == dir.begin())
			current_dir = std::prev(dir.end());
		else
			current_dir = std::prev(current_dir);
	}
} else if (d.first == 'R') {
	int num = d.second / 90;
	for (int i = 0; i < num; i++) {
		current_dir = std::next(current_dir);
		if (current_dir == dir.end())
			current_dir = dir.begin();
	}
}

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.

1
 std::list<std::pair<int, int>> dir = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};

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 list.

We just have to loop over this vector of inputs, move our ship and finally calculate the distance we have moved from the origin,

1
 ans1 = std::abs(pos.first) + std::abs(pos.second);

and that’s it. The first ⭐!

The full code can be found on github

Part 2

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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
    Action N means to move the waypoint north by the given value.
    Action S means to move the waypoint south by the given value.
    Action E means to move the waypoint east by the given value.
    Action W means to move the waypoint west by the given value.
    Action L means to rotate the waypoint around the ship left
	(counter-clockwise) the given number of degrees.
    Action R means to rotate the waypoint around the ship right
	(clockwise) the given number of degrees.
    Action F means to move forward to the waypoint a number of times
	equal to the given value.

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
pos = {0, 0};
std::pair<int, int> wp = {10, 1};
for (auto d : directions) {
	if (d.first == 'N')
		wp.second += d.second;
	else if (d.first == 'S')
		wp.second -= d.second;
	else if (d.first == 'E')
		wp.first += d.second;
	else if (d.first == 'W')
		wp.first -= d.second;
	}
}

Next we must change the forward direction such that the ship moves along the direction that the waypoint is pointing in:

1
2
3
4
	else if (d.first == 'F') {
		pos.first += wp.first * d.second;
		pos.second += wp.second * d.second;
	}

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:

1
2
3
4
5
6
else if ((d.first == 'L') || (d.first == 'R')) {
	if (d.first == 'L')
		wp = rotate(wp, d.second);
	else
		wp = rotate(wp, -d.second);
}

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 ⭐⭐!

The full code can be found on github

Reflections

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

Back to my advent calendar

Comments

Back to all posts