Advent of Rust 12: Typo the Ship Around

It’s once again time for another chronicle of teaching myself the Rust programming language, by doing the programming puzzles on Advent of Code 2020. That’s all I have to say by way of introductions!

Day 12, Part 1

Today’s puzzle looks a lot like Day 8, the virtual machine: here, also, we have to read a bunch of instructions in from a file, simulate executing them, and the answer is something about the state of the system. Instead of a virtual machine the system is a ship, and the instructions are directions for moving the ship: move north, south, east, or west, turn left or right, and move forward in the direction the ship is facing. The answer to the puzzle is the Manhattan distance that the ship has travelled.

I take the code from Day 8 as a starting point and build something similar:

#[derive(Debug)]
enum Direction {
    North(u8),
    South(u8),
    East(u8),
    West(u8),
    Left(u16),
    Right(u16),
    Forward(u8),
}

impl Direction {
    fn from_string(line: &str) -> Self {
        let parameter = &line[1..];
        match line.chars().next().unwrap() {
            'N' => Direction::North(parameter.parse().unwrap()),
            'S' => Direction::South(parameter.parse().unwrap()),
            'E' => Direction::East(parameter.parse().unwrap()),
            'W' => Direction::West(parameter.parse().unwrap()),
            'L' => Direction::Left(parameter.parse().unwrap()),
            'R' => Direction::Right(parameter.parse().unwrap()),
            'F' => Direction::Forward(parameter.parse().unwrap()),
            _ => panic!("Bad instruction {}", line),
        }
    }
}

struct Ship {
    latitude: i16,  // north-south distance
    longitude: i16, // east-west distance
    facing: i8,     // east = 0, increasing clockwise, degrees / 90
}

impl Ship {
    fn new() -> Self {
        Ship {
            latitude: 0,
            longitude: 0,
            facing: 0,
        }
    }

    fn go(&mut self, dir: &Direction) {
        match dir {
            Direction::North(dist) => self.latitude += *dist as i16,
            Direction::South(dist) => self.latitude -= *dist as i16,
            Direction::East(dist) => self.longitude += *dist as i16,
            Direction::West(dist) => self.longitude -= *dist as i16,
            Direction::Left(angle) => {
                self.facing -= (*angle / 90) as i8;
                self.facing += 4;
                self.facing %= 4;
            }
            Direction::Right(angle) => {
                self.facing += (*angle / 90) as i8;
                self.facing += 4;
                self.facing %= 4;
            }
            Direction::Forward(dist) => match self.facing {
                0 => self.go(&Direction::East(*dist)),
                1 => self.go(&Direction::South(*dist)),
                2 => self.go(&Direction::West(*dist)),
                3 => self.go(&Direction::North(*dist)),
                _ => panic!("Bad internal state: facing = {}", self.facing),
            },
        };
    }

    fn manhattan_distance(&self) -> i16 {
        self.latitude.abs() + self.longitude.abs()
    }
}

fn main() -> Result<(), io::Error> {
    let file = fs::File::open("input")?;
    let mut ship = Ship::new();
    read_lines(file)
        .map(|s| Direction::from_string(&s))
        .for_each(|dir| ship.go(&dir));
    println!("{}", ship.manhattan_distance());
    Ok(())
}

Some differences with Day 8’s solution are:

  • I wonder if I can give the enum a from_string method, and indeed I try it and it works.
  • I don’t have to save all the directions in a vector, because I don’t have to jump to an earlier or later instruction; I can just execute each one as soon as I read it.

This went smoothly and gave me the right answer. Aside from the usual dance of letting the compiler tell me where I forgot to borrow variables, I also forgot to put Direction:: on the enum values (too used to enums in C.) It’s also notable that I forgot, as I do in many other programming languages, that the modulo operator (%) can give you a negative result; that’s the reason why I add 4 before taking the modulo of 4.

One Rust thing that still confuses me; I’m not sure why you can get a slice of a string with &line[1..], but not get the first character with &line[0]. This is why I somewhat awkwardly use line.chars().next().unwrap() in Direction::from_string.

Day 12, Part 2

Part 2 of the puzzle reveals that each instruction is actually supposed to do something totally different. Most instructions don’t actually move the ship, they move a “waypoint” north, south, east, or west, or rotate it around the ship. Only the Forward instruction moves the ship, in multiples of the waypoint’s distance.

So I just need to write a second version of the Ship::go() method, which I’ll call move_waypoint(), that implements the new meanings for the instructions instead of the old ones. I will add additional fields to the Ship struct to keep track of the waypoint’s distance north and east of the ship, which may be negative.

To rotate the waypoint, I hoped I could do something like this:1

(self.waypoint_n, self.waypoint_e) = match (*angle / 90) {
    0 => (self.waypoint_n, self.waypoint_e),
    1 => (self.waypoint_e, -self.waypoint_n),
    2 => (-self.waypoint_n, -self.waypoint_e),
    3 => (-self.waypoint_e, self.waypoint_n),
    _ => panic!("Bad angle {}", *angle);
}

However, destructuring assignment is apparently not present yet in a released version of Rust, so this doesn’t work! I’m surprised, as pattern matching seems to be pervasive everywhere else in the language. Instead I google “rust swap variables” but then settle on two temporary variables, because let (new_waypoint_n, new_waypoint_e) = ... does work.

When running the program, I first get a panic due to integer overflow, so I change the type of latitude and longitude to i32. After fixing that, I do get an answer, but the website tells me it’s too high.

I print out each step:

println!("direction {:?} - ship ({}, {}) - waypoint ({}, {})", dir, ship.latitude, ship.longitude, ship.waypoint_n, ship.waypoint_e);

Aside from initially confusing myself about the output because I’m implementing R(n) as L(360 – n), I don’t see anything wrong with it. At this point I’m stumped; I try the example input from the puzzle description, and it gives the correct answer.

Since I had an integer overflow error before, I wonder if there was some other integer conversion error somewhere. I change all of the numeric types to be i32 everywhere; may as well, because it gets rid of the casts. But I get the same answer.

I look over my code, look over the debug output, and just can’t figure out what might be the problem! I know this is probably some typo that is sitting in a blind spot. After a long time I follow the suggestion on the “you got the wrong answer” page, and do something very uncharacteristic: read the Reddit thread. I hope that if I’m interpreting the instructions wrong, I might get a hint without reading too many spoilers. I find this comment from someone who had a typo in the West part of their code, and remarked that the example input didn’t have any West instructions, so the example still worked fine. I made almost the exact same mistake, can you spot it?

Direction::East(dist) => self.waypoint_e += *dist,
Direction::West(dist) => self.waypoint_e += *dist,

In hindsight I could have known by looking at the very first line of the debug output:

direction West(5) - ship (0, 0) - waypoint (1, 15)

The waypoint initially starts at north 1, east 10, so moving the waypoint west should make the waypoint east distance 5, not 15. Once that mistake is corrected, I get the correct answer!

Here’s the move_waypoint() function, or see the full code in the repository.

fn move_waypoint(&mut self, dir: &Direction) {
    match dir {
        Direction::North(dist) => self.waypoint_n += *dist,
        Direction::South(dist) => self.waypoint_n -= *dist,
        Direction::East(dist) => self.waypoint_e += *dist,
        Direction::West(dist) => self.waypoint_e -= *dist,
        Direction::Left(angle) => {
            let (new_waypoint_n, new_waypoint_e) = match *angle / 90 {
                0 => (self.waypoint_n, self.waypoint_e),
                1 => (self.waypoint_e, -self.waypoint_n),
                2 => (-self.waypoint_n, -self.waypoint_e),
                3 => (-self.waypoint_e, self.waypoint_n),
                _ => panic!("Bad angle {}", *angle),
            };
            self.waypoint_n = new_waypoint_n;
            self.waypoint_e = new_waypoint_e;
        }
        Direction::Right(angle) => {
            self.move_waypoint(&Direction::Left(360 - *angle));
        }
        Direction::Forward(times) => {
            self.latitude += self.waypoint_n * *times;
            self.longitude += self.waypoint_e * *times;
        }
    }
}

Afterword

Being confounded by a typo that you just can’t see is the great equalizer, it happens to everyone from time to time, no matter their level of experience … having said that, you can take steps to ensure it’s less likely to happen. For example, usually when I’m writing code, I’m verifying each piece individually against the expected results in unit tests. If I’d had a unit test for the West instruction, I’d have immediately been able to tell where the problem was. A test-first approach would have helped as well; as you can see above, once I saw the result of the faulty West instruction, it was too easy to say “oh, that looks right,” but if I’d had to write the test first, I would have had to actually think about what the result should have been.

Certainly I’m not writing unit tests here, and it’s not clear whether it’s worth it for a one-off puzzle. (I’m not even sure what unit-test frameworks are available in Rust, maybe I should find out!)

What I do find interesting is that this is the first such bug that I’ve written, during this learning exercise. More often when I have this kind of frustration, it’s because of something like dereferencing a null pointer that I thought couldn’t be null. I’m aware of the possibility that this could be wishful thinking or Rust hype, and not backed up by actual data, but I might have expected to run into more of those along the way, if writing in a language that has null pointers.


[1] In theory these are cosines and sines, but I calculated this by rotating my thumb and forefinger around in the air

2 thoughts on “Advent of Rust 12: Typo the Ship Around

  1. If I have a function that consists of only a match {} statement over an enum, I like to “use” the enum into scope. eg, your go() function:

    fn go(&mut self, dir: &Direction) {
    use Direction::*;
    match dir {
    North(dist) => self.latitude += *dist as i16,
    South(dist) => self.latitude -= *dist as i16,
    East(dist) => self.longitude += *dist as i16,
    West(dist) => self.longitude -= *dist as i16,
    Left(angle) => {
    self.facing -= (*angle / 90) as i8;
    self.facing += 4;
    self.facing %= 4;
    }
    Right(angle) => {
    self.facing += (*angle / 90) as i8;
    self.facing += 4;
    self.facing %= 4;
    }
    Forward(dist) => match self.facing {
    0 => self.go(&East(*dist)),
    1 => self.go(&South(*dist)),
    2 => self.go(&West(*dist)),
    3 => self.go(&North(*dist)),
    _ => panic!(“Bad internal state: facing = {}”, self.facing),
    },
    };
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.