Day 12 (Advent of Code 2020)

Time for the Day 12 problem!

In this problem, we have a ship. And we have navigation instructions:

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

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.

Rust code
impl 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,
        }
    }
}

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"]

TOML markup
[dependencies]
derive_more = { version = "0.99.11", features = ["add"], default-features = false }

And now we can just derive Add!

Rust code
use 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?

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!

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.

Cool bear's hot tip

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 code
impl 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".

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 code
impl std::ops::Add<AngleDelta> for Direction {
    type Output = Self;

    fn add(self, rhs: AngleDelta) -> Self::Output {
        todo!("???")
    }
}

Rust code
pub 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 code
impl 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 code
impl 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!")
        }
    }
}

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 code
impl 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!

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 code
fn 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 session
F10
N3
F7
R90
F11

Seems good! Now we need a way to apply our instructions to our ShipState.

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 code
impl 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 code
impl 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
            },
        }
    }
}

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 code
fn 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());
}

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

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.

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 code
impl 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 code
impl 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

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!

Until next time, stay warm!

This article was made possible thanks to my patrons: Alexander Payne, Fredrik Østrem, David Barsky, Yufan Lou, Stephen Molyneaux, Barret Rennie, Thomas Corbin, MW, Jacob Cheriathundam, Michael Watzko, Embark Studios, Eugene Bulkin, Marcus Griep, Petar Radosevic, Tool Army, Tully, Santiago Lema, Spencer Gilbert, Jörn Huxhorn, Garrett Ward, DEX, Christian Oudard, Ronen Cohen, Thor Kamphefner, Kamran Khan, Cole Kurkowski, Arjen Laarhoven, Vicente Bosch, Chirag Jain, Ville Mattila, Marie Janssen, Vladyslav Batyrenko, Cameron Clausen, spike grobstein, Jon Gjengset, Paul Marques Mota, Jakub Fijałkowski, Mitchell Hamilton, Brad Luyster, Max von Forell, Jake S, Dimitri Merejkowsky, Chris Biscardi, René Ribaud, Alex Doroshenko, Vincent, Steven McGuire, Chad Birch, Chris Emery, Bob Ippolito, John Van Enk, metabaron, Isak Sunde Singh, Philipp Gniewosz, Mads Johansen, lukvol, Ives van Hoorne, Jan De Landtsheer, Daniel Strittmatter, Evgeniy Dubovskoy, Alex Rudy, Shane Lillie, Romet Tagobert, Douglas Creager, Corey Alexander, Molly Howell, knutwalker, Zachary Dremann, Sebastian Ziebell, Julien Roncaglia, Amber Kowalski, T, queenfartbutt, Paul Kline, Kristoffer Ström, Astrid Bek, Yoh Deadfall, Justin Ossevoort, Tomáš Duda, Jeremy Banks, Rasmus Larsen, Torben Clasen, C J Silverio, Walther, Pete Bevin, Shane Sveller, Clara Schultz, jer, Wonwoo Choi, Hawken Rives, João Veiga, Richard Pringle, Adam Perry, Benjamin Röjder Delnavaz, Matt Jadczak, Jonathan Knapp, Maximilian, Seth Stadick, brianloveswords, Sean Bryant, Ember, Sebastian Zimmer, Makoto Nakashima, Geoff Cant, Geoffroy Couprie, Michael Alyn Miller, o0Ignition0o, Zaki, Raphael Gaschignard, Romain Ruetschi, Ignacio Vergara, Pascal, Jane Lusby, Nicolas Goy, Ted Mielczarek, Aurora.