Dec 25, 2020

14 min #rust · #advent-of-code

Day 12 (Advent of Code 2020)

From the series Advent of Code 2020

14

👋 This page was last updated ~4 years ago. Just so you know.

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.

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

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

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:

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 😎

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:

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

You're reading the Advent of Code 2020 series.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

Comment on /r/fasterthanlime

(JavaScript is required to see this. Or maybe my stuff broke)

Here's another article just for you:

A dynamic linker murder mystery

Jul 08, 2020

23 min #rust · #linkers · #linux · #postmortem

I write a ton of articles about rust. And in those articles, the main focus is about writing Rust code that compiles. Once it compiles, well, we’re basically in the clear! Especially if it compiles to a single executable, that’s made up entirely of Rust code.

That works great for short tutorials, or one-off explorations.

Unfortunately, “in the real world”, our code often has to share the stage with other code. And Rust is great at that. Compiling Go code to a static library, for example, is relatively finnicky. It insists on being built with GCC (and no other compiler), and linked with GNU ld (and no other linker).