fasterthanlime

Dec 25, 2020 17 min #rust · #advent-of-code

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:

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

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!

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

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

And now we can just derive Add!

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:

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

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

#[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.

#[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.

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

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:

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

impl std::ops::Add<AngleDelta> for Direction {
    type Output = Self;

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

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:

#[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.

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:

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!

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

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:

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

#[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)

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

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

$ cargo run --quiet
Advance(10)
Move(North, 3)
Advance(7)
Rotate(AngleDelta(1))
Advance(11)

Let's compare against our original instruction:

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:

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!

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.

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:

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

$ 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 😎

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:

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

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:

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

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

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

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

Thanks to my sponsors: Cole Kurkowski, Christian Bourjau, Chris Thackrey, AdrianEddy, Ernest French, Helge Eichhorn, Daniel Wagner-Hall, Neil Blakey-Milner, compwhizii, Paul Horn, Sam, Mason Ginter, Ivo Murrell, Sawyer Knoblich, Http 418, Tyler Bloom, Jacob Cheriathundam, Aalekh Patel, Paige Ruten, belzael and 227 more Cole Kurkowski, Christian Bourjau, Chris Thackrey, AdrianEddy, Ernest French, Helge Eichhorn, Daniel Wagner-Hall, Neil Blakey-Milner, compwhizii, Paul Horn, Sam, Mason Ginter, Ivo Murrell, Sawyer Knoblich, Http 418, Tyler Bloom, Jacob Cheriathundam, Aalekh Patel, Paige Ruten, belzael, Miguel Piedrafita, Astrid, Luiz Irber, Adam Gutglick, budrick, Brandon Piña, Joonas Koivunen, Alex Krantz, Sarah Berrettini, David E Disch, Andrew Neth, Ahmad Alhashemi, Tobias Bahls, Xirvik Servers, Andy Gocke, John VanEnk, Steven McGuire, Matt Jadczak, Blake Johnson, Valentin Mariette, Max Heaton, Mattia Valzelli, Marcus Griep, Luke Konopka, Aiden Scandella, Tyler Schmidtke, playest, Jörn Huxhorn, Morgan Rosenkranz, Evan Relf, Tiziano Santoro, Jarek Samic, Torben Clasen, C J Silverio, Aleksandre Khokhiashvili, Alejandro Angulo, Niels Abildgaard, Isak Sunde Singh, Johnathan Pagnutti, Xavier Groleau, Marcin Kołodziej, Rufus Cable, Chris Sims, WeblWabl, René Ribaud, clement, Johan Andersson, Corey Alexander, Matt Heise, Marty Penner, Dennis Henderson, Jelle Besseling, James Leitch, pinkhatbeard, Borys Minaiev, Luke Yue, David Cornu, hgranthorner, Richard Stephens, Ramen, Lucille Blumire, std__mpa, Vincent, Marco Carmosino, SeniorMars, L0r3m1p5um, Jack Duvall, old.woman.josiah, Chris Biscardi, Zaki, Yuriy Taraday, Gran PC, avborhanian, Michal Hošna, Daniel Silverstone, nyangogo, Scott Sanderson, David Barsky, Cass, Romain Ruetschi, Mike Cripps, Chirag Jain, Matt Jackson, Mark Old, Matěj Volf, Romet Tagobert, henrique-pinto, Chris Emery, callym, Eugene Bulkin, Colin VanDervoort, Theodore Rose, Tom Forbes, Michael Alyn Miller, Thor Kamphefner, Horváth-Lázár Péter, Yann Schwartz, Yufan Lou, genny, Jonathan Adams, zaurask, Michał Bartoszkiewicz, Scott Steele, Romain Kelifa, Dom, Herman J. Radtke III, Dirkjan Ochtman, Olly Swanson, Beth Rennie, Guillaume Demonet, joseph, Philipp Hatt, Olivia Crain, Daniel Strittmatter, Berkus Decker, Josh Triplett, David White, Timothée Gerber, Kristoffer Winther Balling, Johan Saf, Peter Shih, Radu Matei, Jon Gjengset, Christoph Grabo, Ben Wishovich, Antoine Rouaze, Jan De Landtsheer, Joshua Roesslein, Matthew T, Paul Schuberth, James Rhodes, Duane Sibilly, Garret Kelly, Marcus Griep, Daniel Papp, jer, Santiago Lema, Guy Waldman, Josiah Bull, Marc-Andre Giroux, Ronen Ulanovsky, Lev Khoroshansky, Makoto Nakashima, prairiewolf, Victor Song, Manuel Hutter, Richard Pringle, Michael, Tabitha, Marcus Brito, Raine Tingley, Integer 32, LLC, Lena Schönburg, Yves, Jean-David Gadina, Mikkel Rasmussen, Paul Marques Mota, Alex Doroshenko, Zachary Thomas, Mario Fleischhacker, Foxie Solutions, ZacJW, ofrighil, Hadrien G., Andronik, Chris Walker, Dimitri Merejkowsky, bbutkovic, Julian Schmid, Henrik Tudborg, Philipp Gniewosz, Ben Mitchell, Max von Forell, Lennart Oldenburg, Sindre Johansen, Enrico Zschemisch, Max Bruckner, Alan O'Donnell, Ronen Cohen, Dylan Anthony, jatescher, Michael Mrozek, James Brown, Tanner Muro, Lyssieth, Steven Pham, Kamran Khan, qrpth, Raphaël Thériault, Jean Manguy, you got maiL, Ives van Hoorne, Braidon Whatley, Diego Roig, Justin Ossevoort, Shane Lillie, Geoffroy Couprie, Pete Bevin, xales, Leo Shimonaka, Nikolai Vincent Vaags, Sean Bryant, Senyo Simpson, Zoran Zaric, Marie Janssen, Benjamin Röjder Delnavaz, anichno, Andy F, Geoff Cant, Walther, David Souther, Chris, Marky Mark, Nicholas Bishop, Boris Dolgov, Ross Williams, Bob Ippolito, Moritz Lammerich, villem, Guillaume E, Noel, Zeeger Lubsen, Ryan, notryanb, Nicolas Goy, Jake Demarest-Mays, Sylvie Nightshade

Comment on /r/fasterthanlime

If you liked what you saw, please support my work!

Donate on GitHub Donate on Patreon

Here's another article just for you:

ktls now under the rustls org

Sep 26, 2024

5 min #rustls · #ktls · #rust

What's a ktls

I started work on ktls and ktls-sys, a pair of crates exposing Kernel TLS offload to Rust, about two years ago.

kTLS lets the kernel (and, in turn, any network interface that supports it) take care of encryption, framing, etc., for the entire duration of a TLS connection... as soon as you have a TLS connection.

For the handshake itself (hellos, change cipher, encrypted extensions, certificate verification, etc.), you still have to use a userland TLS implementation.

Read more