Advent of Code 2020 - Day 12

This is a running series of posts on the Advent of Code 2020. The introductory post has the details, including the accompanying GitHub repo, in case you reached this directly.

Part 1

In this puzzle we just need to keep track of the position of a ship that follows a sequence of commands. Commands consist of a letter and an integer as argument (immediate to parse). Following the path of the ship is only a matter of keeping straight what each command does.

We need two values to keep the state: a 2-vector for the position, and the angle of the heading. At each step we apply the corresponding command:

• N, S, W, E: move in the specified direction as many units as given in the argument, a matter of adding or subtracting for the proper component of the position.
• L, R: modify heading by as many degrees as given in the argument, which just needs to add or subtract that to the current heading (modulo 360 to keep it in range).
• F: move in the heading direction as many units as given in the argument; basic trigonometry to apply cosine to the x coordinate and sine to the y coordinate (and remember to convert to radians).

Finally, just add the absolute values of the components to get the answer.

Part 2

The 'waypoint' now becomes a vector rather than just a heading, and the R and L commands now rotate this vector; F moves in the direction of the waypoint, and the argument specifies how many times its length.

We could still use some trigonometry to determine the initial waypoint angle and length, then do as in Part 1, but multiplying by the waypoint length (which cannot change) the coordinate updates of the F command. But where's the fun in that?

Python has built-in complex numbers, and they have a couple of interesting properties: their addition works just like 2d vector addition, which matches what we expect of the N, S, W, E commands; if we add in that multiplication by a scalar results in scaling, we can apply the F command trivially. And multiplication of complex numbers results in a rotation (plus scaling); by properly designing the multiplicand, we can obtain the desired rotation for the L and R commands.

In particular, we want a unitary complex number forming the desired angle (using negative angles for rotating right), or exp(i*angle) in polar notation, which corresponds to cos(angle) + i*sin(angle) in Cartesian notation.

With this in mind, redefining the effects of commands results in:

• N, S, W, E: add to position the argument times the corresponding complex unitary vector.
• L, R: multiply the waypoint vector by the corresponding complex rotation as explained above.
• F: add to position argument times the waypoint vector.

Finally add the absolute values of the real and imaginary parts of the position. abs(position) exists, but it results in the length of the complex vector, which is Euclidean rather than Manhattan distance.