Day 12 (Advent of Code 2020)
This article is part of the Advent of Code 2020 series.
Time for the Day 12 problem!
In this problem, we have a ship. And we have navigation instructions:
- Action
N
means to movenorth
by the given value. - Action
S
means to movesouth
by the given value. - Action
E
means to moveeast
by the given value. - Action
W
means to movewest
by the given value. - Action
L
means to turnleft
the given number of degrees. - Action
R
means to turnright
the given number of degrees. - Action
F
means to moveforward
by the given value in the direction the ship is currently facing.
Reading these, I was a bit confused at first - does moving the ship north if it's facing east change its direction? The answer is no - it's a ship from the future, that can move sideways.
Here's an example of navigation instructions:
F10 N3 F7 R90 F11
Here we have: forward 10, north 3, forward 7, turn right 90, forward 11.
It's worth noting that L
and R
instructions are always followed by
multiples of 90 (quarter angles).
The question we need to answer for Part 1 is - what's the Manhattan distance between the ship's starting position (in yellow) and its final position (in blue)?
For this example, it's 25:
So, let's make up some types 😊!
We're going to need some sort of two-dimensional vector, to represent both position and movement:
Rust code#[derive(Clone, Copy, PartialEq, Eq, Debug)] struct Vec2 { x: isize, y: isize, }
And we want to be able to add them, at the very least.
Ooh, are we going to implement Add
again?
Sure, we could do that:
Rust codeimpl std::ops::Add for Vec2 { type Output = Self; fn add(self, rhs: Self) -> Self::Output { Self { x: self.x + rhs.x, y: self.y + rhs.y, } } }
But that looks awfully mechanical - almost like it could be generated automatically... if only we could find a crate for that?
Oooh look what I found.
Let's give derive_more
a try!
Shell session$ cargo add derive_more --no-default-features --features add Adding derive_more v0.99.11 to dependencies with features: ["add"]
Hold up - cargo-edit can do that??
Yes it can! Let's look at the generated [dependencies]
section of our Cargo.toml
:
TOML markup[dependencies] derive_more = { version = "0.99.11", features = ["add"], default-features = false }
And now we can just derive Add
!
Rust codeuse derive_more::*; // 👇 new! #[derive(Clone, Copy, PartialEq, Eq, Debug, Add)] struct Vec2 { x: isize, y: isize, } #[test] fn vec2_add() { let a = Vec2 { x: 3, y: 8 }; let b = Vec2 { x: 2, y: 10 }; assert_eq!(a + b, Vec2 { x: 5, y: 18 }); }
Now, normally I'd show a cargo test
shell session here, but truth is, if I
just want to run one test? I use the "Run Test" inline command provided by
rust-analyzer in vscode:

And I'd get this:
Shell session> Executing task: cargo test --package day12 --bin day12 -- vec2_add --exact --nocapture < Compiling day12 v0.1.0 (/home/amos/ftl/aoc2020/day12) Finished test [unoptimized + debuginfo] target(s) in 0.47s Running target/debug/deps/day12-35a7c5988354f23f running 1 test test vec2_add ... ok test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out Terminal will be reused by tasks, press any key to close it.
From now on in this series I'll only show test results if they actually fail. Seems fair?
Fair enough!
While we're at it, we may want to derive Sub
as well, and add a manhattan
method that computes the sum of the absolute value of both coordinates:
Rust code// 👇 new! #[derive(Clone, Copy, PartialEq, Eq, Debug, Add, Sub)] struct Vec2 { x: isize, y: isize, } impl Vec2 { // Vec2 is copy, so it's fine to take `self` fn manhattan(self) -> usize { (self.x.abs() + self.y.abs()) as _ } }
Now we can write a test that checks we would've gotten the right answer for the example!
Rust code#[test] fn manhattan_example() { let start = Vec2 { x: 0, y: 0 }; let end = Vec2 { x: 17, y: -8 }; assert_eq!((end - start).manhattan(), 25); }
Next up - just a Vec2
isn't enough to describe the state of our ship. We
also have a direction!
Well, there's only four possible directions, so it seems like an enum
would
work?
Right on.
Rust code#[derive(Clone, Copy, PartialEq, Eq, Debug)] enum Direction { East, South, West, North, }
We should also decide, in terms of 2D coordinates - which vector is associated with each direction?
There's a couple options at our disposal: I'm fairly sure we want East
to
be (1, 0)
- but we could pick North
to be (0, 1)
or (0, -1)
,
depending on whether North is +Y
or -Y
, respectively.
It gets even worse in 3D - nobody can quite agree "what's up", as it were. Here's an infographic by the wonderful Freya Holmér, of Shapes fame among other things:

Here though, we'll just pick North
to be (0, 1)
(which means our origin
is conceptually "bottom left") and stick with it. The problem is carefully
formulated so that it doesn't really matter - the Manhattan distance will be
the same no matter what coordinate system we use. Good job, Advent of Code
writers! 🙌
Rust codeimpl Direction { fn vec(self) -> Vec2 { match self { Direction::East => Vec2 { x: 1, y: 0 }, Direction::South => Vec2 { x: 0, y: -1 }, Direction::West => Vec2 { x: -1, y: 0 }, Direction::North => Vec2 { x: 0, y: 1 }, } } }
Now we have a bit of an issue though - how do we turn? Again, we have two options as to what an "angle delta" means. The problem statement says "R" means turning "Right", but depending on where you're facing, it's not that obvious: a ship facing north turning right will face right, sure. But what about a ship facing south? Should it now fast left? Or right?
The example given disambiguates that for us. When facing east and turning right, our ship ends up facing south, so: turning "right" means turning "clockwise".
The confusion doesn't end there - there's multiple units for angles, including radians and degrees (the example uses degrees here), and we also get to decide what "angle 0" means. As a kid, it always made more sense to me to have angle 0 be "north", but in Trigonometry, apparently angle 0 is "east".
Waiiiiiit is that why you arranged the enum variants in that specific order?
Yes it is!
So now, how do we turn? It would be super handy if we could apply an "angle delta" (delta meaning "difference") to a direction and get another direction.
Let's make a new type:
Rust code/// Represents an angle, in multiples of 90° #[derive(Clone, Copy, PartialEq, Eq, Debug)] struct AngleDelta(isize);
And now we can implement the Direction + AngleDelta
operation:
Rust codeimpl std::ops::Add<AngleDelta> for Direction { type Output = Self; fn add(self, rhs: AngleDelta) -> Self::Output { todo!("???") } }
In this series, this is the first time we implement Add
between two
different types. Before, it was always between two of the same type, because
the Rhs
type parameter defaults to Self
in Add
's definition:
Rust codepub trait Add<Rhs = Self> { /// The resulting type after applying the `+` operator. #[stable(feature = "rust1", since = "1.0.0")] type Output; /// Performs the `+` operation. /// /// # Example /// /// ``` /// assert_eq!(12 + 1, 13); /// ``` #[must_use] #[stable(feature = "rust1", since = "1.0.0")] fn add(self, rhs: Rhs) -> Self::Output; }
But how should we implement this method? If the angle is 90, then:
- If we were facing East, we're now facing South
- If we were facing South, we're now facing West
- If we were facing West, we're now facing North
- If we were facing North, we're now facing East
But the angle could also be 180, or 270, or 360, or -90! That's a lot of cases to deal with.
To simplify our work, we're going to explicitly define a representation
for our enum
, and simply work with numbers in the 0..=3
range:
Rust code#[derive(Clone, Copy, PartialEq, Eq, Debug)] #[repr(u8)] enum Direction { East = 0, South = 1, West = 2, North = 3, }
Now our Direction
is the same size as an u8
- it just has Super Enum
Powers, which allows us to write match
expressions with only four arms,
because having a Direction
whose underlying value is not in 0..=3
is
undefined behavior.
We can easily convert a Direction
to an isize
, because any Direction
is always a valid isize
.
Rust codeimpl Into<isize> for Direction { fn into(self) -> isize { self as _ } }
The other way around isn't that straightforward - if we have an isize
with
value 6
- that's not a Direction! In other words, it's a fallible
conversion, for which we can use the TryFrom
trait:
Rust codeimpl std::convert::TryFrom<isize> for Direction { type Error = &'static str; fn try_from(value: isize) -> Result<Self, Self::Error> { if (0..=3).contains(&value) { Ok(unsafe { std::mem::transmute(value as u8) }) } else { Err("direction out of bounds!") } } }
Oooh, unsafe
code. Isn't that dangerous?
Yeah! If we used 0..=4
instead, we could build illegal values of Direction
and cause undefined behavior.
Better test it then!
Rust code#[test] fn direction_try_from() { use std::convert::TryFrom; assert_eq!( <Direction as TryFrom<isize>>::try_from(0).unwrap(), Direction::East ); assert_eq!( <Direction as TryFrom<isize>>::try_from(2).unwrap(), Direction::West ); assert!(<Direction as TryFrom<isize>>::try_from(-1).is_err(),); assert!(<Direction as TryFrom<isize>>::try_from(4).is_err(),); }
This passes! Now, implementing Add
is slightly easier. In Part
3, we struggled with modulos, but thankfully,
someone pointed out we could just use rem_euclid.
So we're going to!
Rust codeimpl std::ops::Add<AngleDelta> for Direction { type Output = Self; fn add(self, rhs: AngleDelta) -> Self::Output { use std::convert::TryInto; let angle: isize = self.into(); (angle + rhs.0).rem_euclid(4).try_into().unwrap() } }
Let's test this as well:
Rust code#[test] fn test_direction_add() { // From example assert_eq!(Direction::East + AngleDelta(1), Direction::South); // Turning "left" (counter-clockwise) assert_eq!(Direction::East + AngleDelta(-1), Direction::North); // Doing a 360° assert_eq!(Direction::East + AngleDelta(4), Direction::East); }
Finally, the ship's state is going to be described by its position and direction:
Rust code#[derive(Clone, Copy, PartialEq, Eq, Debug)] struct ShipState { pos: Vec2, dir: Direction, }
And with that, we're good to go!
Amos, aren't you forgetting something?
Mh?
Where's our parser?
Oh right! Our parser. Well, the problem statement lists 7 different instructions, but really we only have 3 distinct instructions:
- Move in a set direction
- Rotate by a given angle delta
- Move forward (which depends on the direction of the ship)
Rust code#[derive(Clone, Copy, PartialEq, Eq, Debug)] enum Instruction { /// Moves in given direction Move(Direction, isize), /// Turns Rotate(AngleDelta), /// Moves forward Advance(isize), }
And, sure, let's parse it:
Rust codefn parse_instructions(input: &str) -> impl Iterator<Item = Instruction> + '_ { input.lines().map(|line| { let command = line.as_bytes()[0]; // Safety: this will panic if `line` starts with multibyte character let number: isize = (&line[1..]).parse().unwrap(); match command { b'N' => Instruction::Move(Direction::North, number), b'S' => Instruction::Move(Direction::South, number), b'E' => Instruction::Move(Direction::East, number), b'W' => Instruction::Move(Direction::West, number), b'L' => Instruction::Rotate(AngleDelta(-number / 90)), b'R' => Instruction::Rotate(AngleDelta(number / 90)), b'F' => Instruction::Advance(number), c => panic!("unknown instruction {}", c as char), } }) } fn main() { for ins in parse_instructions(include_str!("input.txt")) { println!("{:?}", ins); } }
Shell session$ cargo run --quiet Advance(10) Move(North, 3) Advance(7) Rotate(AngleDelta(1)) Advance(11)
Let's compare against our original instruction:
Shell sessionF10 N3 F7 R90 F11
Seems good! Now we need a way to apply our instructions to our ShipState
.
A method?
Or we could misuse operator overloading?
But before we do... we have a way to turn a Direction
into a Vec2
, but we
often move several units into one direction, not just one - so it'd be very
neat if we could multiply a Vec2
with an isize
:
Rust codeimpl std::ops::Mul<isize> for Vec2 { type Output = Self; fn mul(self, rhs: isize) -> Self::Output { Self { x: self.x * rhs, y: self.y * rhs, } } }
And now we can implement a cursed operation... ShipState + Instruction
!
Rust codeimpl std::ops::Add<Instruction> for ShipState { type Output = Self; fn add(self, rhs: Instruction) -> Self::Output { match rhs { Instruction::Move(dir, units) => Self { pos: self.pos + dir.vec() * units, ..self }, Instruction::Rotate(delta) => Self { dir: self.dir + delta, ..self }, Instruction::Advance(units) => Self { pos: self.pos + self.dir.vec() * units, ..self }, } } }
I gotta say - I thought we were writing a bit too much code just for part 1,
but this last impl
is a thing of beauty!
And then, well, then we
fold
.
It's the perfect fit! We have an initial state, and we keep applying modifications
to it, from each instruction yielded by an iterator.
Rust codefn main() { let start = ShipState { dir: Direction::East, pos: Vec2 { x: 0, y: 0 }, }; let end = parse_instructions(include_str!("input.txt")).fold(start, |state, ins| state + ins); dbg!(start, end, (end.pos - start.pos).manhattan()); }
Oooohhh, beautiful! ✨
Let's try it with the sample values:
Shell session$ cargo run --quiet [src/main.rs:185] start = ShipState { pos: Vec2 { x: 0, y: 0, }, dir: East, } [src/main.rs:185] end = ShipState { pos: Vec2 { x: 17, y: -8, }, dir: South, } [src/main.rs:185] (end.pos - start.pos).manhattan() = 25
And now with my puzzle input:
Shell session$ cargo run --quiet [src/main.rs:185] start = ShipState { pos: Vec2 { x: 0, y: 0, }, dir: East, } [src/main.rs:185] end = ShipState { pos: Vec2 { x: 1615, y: -655, }, dir: East, } [src/main.rs:185] (end.pos - start.pos).manhattan() = 2270
Correct! It's the start of a whole new streak 😎
Part 2
The second part, as is tradition, flips everything around. Ah, the old Advent of Code switcheroo. There's now a "waypoint", with a position relative to the boat, and it rotates around the boat. Moving forward now means moving towards the waypoint, but the waypoint also moves with the boat...
So basically, our state is now this:
Rust code#[derive(Clone, Copy, PartialEq, Eq, Debug)] struct ShipState { pos: Vec2, dir: Direction, waypoint: Vec2, }
And waypoint
really is a second kind of direction, with a magnitude (or
amplitude, or length) that can be more than 1.
Here, when moving forward (towards the waypoint), the ship would actually
move a distance of sqrt(8^2 + 16^2) = ~17.9
units.
Also, the N
, S
, E
, W
instructions now move the waypoint north,
south, east or west.
So it's not a future ship after all?
Guess not!
To apply those rules, we need a new operation: to rotate a Vec2
by the
given AngleDelta
.
It's relatively simple - first, we'll use rem_euclid
to map any possible
AngleDelta
value to the 0..=3
range, and then:
- If the angle is 0, we don't need to change anything
- If the angle is 1, we set it to (y, -x)
- If the angle is 2, we set it to (-x, -y)
- If the angle is 3, we set it to (-y, x)
Let's implement it:
Rust codeimpl Vec2 { fn rotate(self, d: AngleDelta) -> Self { let Self { x, y } = self; match d.0.rem_euclid(4) { 0 => Self { x, y }, 1 => Self { x: y, y: -x }, 2 => Self { x: -x, y: -y }, 3 => Self { x: -y, y: x }, _ => unreachable!(), } } }
...and add a quick test:
Rust code#[test] fn test_rotate() { let v = Vec2 { x: 3, y: 1 }; assert_eq!(v.rotate(AngleDelta(0)), v); assert_eq!(v.rotate(AngleDelta(4)), v); assert_eq!(v.rotate(AngleDelta(-4)), v); assert_eq!(v.rotate(AngleDelta(1)), Vec2 { x: 1, y: -3 }); assert_eq!(v.rotate(AngleDelta(2)), Vec2 { x: -3, y: -1 }); assert_eq!(v.rotate(AngleDelta(3)), Vec2 { x: -1, y: 3 }); }
And now, we're ready for the big time! Instruction parsing is still the same,
only <ShipState as Add>::<Instruction, Output = Self>
changes:
Rust codeimpl std::ops::Add<Instruction> for ShipState { type Output = Self; fn add(self, rhs: Instruction) -> Self::Output { match rhs { // moves waypoint Instruction::Move(dir, units) => Self { waypoint: self.waypoint + dir.vec() * units, ..self }, // rotates waypoint (relative to ship) Instruction::Rotate(delta) => Self { waypoint: self.waypoint.rotate(delta), ..self }, // advance towards waypoint Instruction::Advance(units) => Self { pos: self.pos + self.waypoint * units, ..self }, } } }
Let's try our new version with the short, example input:
F10 N3 F7 R90 F11
Shell session$ cargo run --quiet [src/main.rs:212] start = ShipState { pos: Vec2 { x: 0, y: 0, }, dir: East, waypoint: Vec2 { x: 10, y: 1, }, } [src/main.rs:212] end = ShipState { pos: Vec2 { x: 214, y: -72, }, dir: East, waypoint: Vec2 { x: 4, y: -10, }, } [src/main.rs:212] (end.pos - start.pos).manhattan() = 286
That checks out!
Now for the real puzzle input:
Shell session$ cargo run --quiet [src/main.rs:212] start = ShipState { pos: Vec2 { x: 0, y: 0, }, dir: East, waypoint: Vec2 { x: 10, y: 1, }, } [src/main.rs:212] end = ShipState { pos: Vec2 { x: 68489, y: 70180, }, dir: East, waypoint: Vec2 { x: 33, y: 50, }, } [src/main.rs:212] (end.pos - start.pos).manhattan() = 138669
That's correct!
Streak, streak, streak!
I'm afraid it's a little cold for that.
🙄
Until next time, stay warm!
This article was made possible thanks to my patrons: Steven McGuire, Chad Birch, Chris Emery, Bob Ippolito, John Van Enk, metabaron, Isak Sunde Singh, Ali Yazdani, Philipp Gniewosz, Mads Johansen, lukvol, Ives van Hoorne, Jan De Landtsheer, Daniel Strittmatter, Evgeniy Dubovskoy, Alex Rudy, Romet Tagobert, Douglas Creager, Gus W, Corey Alexander, Molly Howell, knutwalker, Zachary Dremann, Sebastian Ziebell, Julien Roncaglia, Amber Kowalski, T, Juniper Wilde, Paul Kline, Kristoffer Ström, Astrid Bek, Yoh Deadfall, Justin Ossevoort, taziden, Harsh Shandilya, Tomáš Duda, Jeremy Banks, Rasmus Larsen, Torben Clasen, Sam Rose, C J Silverio, Walther, Pete Bevin, Shane Sveller, Thomas Schultz, Ivan Dubrov, jer, Wonwoo Choi, João Veiga, Richard Pringle, Adam Perry, Benjamin Röjder Delnavaz, Matt Jadczak, tavr, Mara Bos, Jonathan Knapp, Maximilian, Seth Stadick, brianloveswords, Sean Bryant, Ember, Sebastian Zimmer, Fernando, Makoto Nakashima, Geert Depuydt, Geoff Cant, Geoffroy Couprie, Michael Alyn Miller, o0Ignition0o, Zaki, Raphael Gaschignard, Romain Ruetschi, Ignacio Vergara, Pascal, Jane Lusby, Nicolas Goy, Ted Mielczarek, Someone, Ryszard Sommefeldt, Aurora.
This article is part 12 of the Advent of Code 2020 series.
If you liked this article, please support my work on Patreon!