Home Articles Series About

Day 12 (Advent of Code 2020)

Dec 25, 2020 · 24 minute read · rust · advent-of-code

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:

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

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 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?

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.

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

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

    fn add(self, rhs: AngleDelta) -> Self::Output {
        todo!("???")
    }
}
Cool bear's hot tip

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 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:

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!")
        }
    }
}

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

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:

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.

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

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

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:

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

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: Vicente Bosch, Chirag Jain, Ville Mattila, Marie Janssen, Cameron Clausen, spike grobstein, Daniel Franklin, Jon Gjengset, Andrei Dyldin, 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, 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, Clara Schultz, Ivan Dubrov, jer, Wonwoo Choi, Hawken Rives, 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, Ryszard Sommefeldt, Jesús Higueras, Aurora.

This article is part 12 of the Advent of Code 2020 series.

Read the next part

Discuss this article on /r/fasterthanlime

If you liked this article, please support my work on Patreon!

Become a Patron

Looking for the homepage?
Another article: Declarative memory management
@fasterthanlime — /r/fasterthanlime — Patreon — Atom feed