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

Advent of Rust 11: Can I Pretend to Write Python Instead?

I’m starting to run out of substantially different lead paragraphs to write about this latest installment of the chronicle of trying to teach myself the Rust programming language by completing the programming puzzles on Advent of Code 2020, so let’s just get to it!

Day 11, Part 1

Today’s puzzle is a thinly disguised version of the Game of Life, with slightly different rules, and with an extra complication: some cells are seats that can be occupied, and some are empty floor that cannot. The description claims that with these rules, the input will always converge to a steady state, and the answer to the puzzle is how many cells are occupied when the steady state is reached.

If I were going to implement the Game of Life in Python I’d certainly reach for NumPy’s ndarray so the first thing I google is “rust ndarray” and am pleasantly surprised to find an ndarray package. I take a look at its documentation and especially ndarray for NumPy users. It looks like it’s not nearly as mature as NumPy and is missing a few key features, and the documentation is not as full of nice examples as other pacakages. But maybe I’ll try to use it for this problem and see how far I get.

The first problem that I run into is that I’m not sure how to add ndarray to my program! I know to put it in Cargo.toml, but most of the packages I’ve used have had examples on the front page of their documentation saying exactly what I have to add to my source file, e.g. use itertools::Itertools;. Maybe I’ll leave it out and see if the compiler can tell me what to write…

I wrote a lot of code with NumPy back in the day when I was analyzing data in the laser lab.1 It takes me a while to get back to thinking in terms of ndarray and slices (in the NumPy sense, not the Rust sense — slices are writable views of an array, or views of a subset of an array), but once I do, I have a clear idea of how to solve the puzzle.

I will store the occupied and unoccupied cells in one array, and the tiles (seats and floors) in another array, so that I can use the tiles array as a mask for the other one by multiplying it. Then, for each iteration of the game:

  • Create an array of the count of the neighbours of each cell.
  • Add the neighbour counts to the occupied cells, make a new array with ones where the result is 0, and multiply by the tiles mask. This array has ones where a person will arrive to occupy the seat, and zeroes elsewhere.
  • Make a new array with ones in the cells where the neighbour count is ≥ 4, and multiply by the tiles mask. This array has ones where a person will depart from an occupied seat, and zeroes elsewhere.
  • Make a new array of the occupied cells, plus the arrivals array, minus the departures array. Check if it is equal to the previous array of occupied cells, and if it is, we have reached the solution.

I also decide that this would be a good place to use the loop expression that I learned a couple of days ago.

Calculating the neighbour counts is something that I would do in NumPy by creating an array of zeros, and doing eight additions with slices. For example, to count the top neighbours, I’d take a slice of the occupied seats array consisting of everything except the bottom row, and add it to a slice of the neighbour counts array consisting of everything except the top row. This sounds complicated but it’s a fast way of saying “add one to every cell, if the cell below it is occupied”. If you do that for each of the eight directions, then you have a neighbour count.

neighbours[:, 1:] += seats[:, :-1]

I try to do the same thing in Rust:

neighbours.slice_mut(s![.., 1..]) += seats.slice(s![.., ..height - 1]);

But I get an impenetrable wall of errors:

error[E0271]: type mismatch resolving `<ndarray::ViewRepr<&mut i8> as ndarray::RawData>::Elem == ndarray::ArrayBase<ndarray::ViewRepr<&i8>, _>`
  --> puzzle11.rs:35:39
   |
35 |     neighbours.slice_mut(s![.., 1..]) += seats.slice(s![.., ..height - 1]);
   |                                       ^^ expected `i8`, found struct `ndarray::ArrayBase`
   |
   = note: expected type `i8`
            found struct `ndarray::ArrayBase<ndarray::ViewRepr<&i8>, _>`
   = note: required because of the requirements on the impl of `std::ops::AddAssign<ndarray::ArrayBase<ndarray::ViewRepr<&i8>, _>>` for `ndarray::ArrayBase<ndarray::ViewRepr<&mut i8>, ndarray::Dim<[usize; 2]>>`

error[E0277]: the trait bound `ndarray::ArrayBase<ndarray::ViewRepr<&i8>, _>: ndarray::ScalarOperand` is not satisfied
  --> puzzle11.rs:35:39
   |
35 |     neighbours.slice_mut(s![.., 1..]) += seats.slice(s![.., ..height - 1]);
   |                                       ^^ the trait `ndarray::ScalarOperand` is not implemented for `ndarray::ArrayBase<ndarray::ViewRepr<&i8>, _>`
   |
   = note: required because of the requirements on the impl of `std::ops::AddAssign<ndarray::ArrayBase<ndarray::ViewRepr<&i8>, _>>` for `ndarray::ArrayBase<ndarray::ViewRepr<&mut i8>, ndarray::Dim<[usize; 2]>>`

error[E0271]: type mismatch resolving `<ndarray::ViewRepr<&i8> as ndarray::RawData>::Elem == ndarray::ArrayBase<ndarray::ViewRepr<&i8>, _>`
  --> puzzle11.rs:35:39
   |
35 |     neighbours.slice_mut(s![.., 1..]) += seats.slice(s![.., ..height - 1]);
   |                                       ^^ expected `i8`, found struct `ndarray::ArrayBase`
   |
   = note: expected type `i8`
            found struct `ndarray::ArrayBase<ndarray::ViewRepr<&i8>, _>`
   = note: required because of the requirements on the impl of `std::ops::AddAssign` for `ndarray::ArrayBase<ndarray::ViewRepr<&i8>, _>`
   = note: required because of the requirements on the impl of `std::ops::AddAssign<ndarray::ArrayBase<ndarray::ViewRepr<&i8>, _>>` for `ndarray::ArrayBase<ndarray::ViewRepr<&mut i8>, ndarray::Dim<[usize; 2]>>`

error[E0277]: the trait bound `ndarray::ViewRepr<&i8>: ndarray::DataMut` is not satisfied
  --> puzzle11.rs:35:39
   |
35 |     neighbours.slice_mut(s![.., 1..]) += seats.slice(s![.., ..height - 1]);
   |                                       ^^ the trait `ndarray::DataMut` is not implemented for `ndarray::ViewRepr<&i8>`
   |
   = help: the following implementations were found:
             <ndarray::ViewRepr<&'a mut A> as ndarray::DataMut>
   = note: required because of the requirements on the impl of `std::ops::AddAssign` for `ndarray::ArrayBase<ndarray::ViewRepr<&i8>, _>`
   = note: required because of the requirements on the impl of `std::ops::AddAssign<ndarray::ArrayBase<ndarray::ViewRepr<&i8>, _>>` for `ndarray::ArrayBase<ndarray::ViewRepr<&mut i8>, ndarray::Dim<[usize; 2]>>`

error[E0067]: invalid left-hand side of assignment
  --> puzzle11.rs:35:39
   |
35 |     neighbours.slice_mut(s![.., 1..]) += seats.slice(s![.., ..height - 1]);
   |     --------------------------------- ^^
   |     |
   |     cannot assign to this expression

I eventually solve this by poking around until it works. The “cannot assign to this expression” message gives me a clue that I need to store the mutable slice in a separate variable, and then eventually I add a & operator:

let mut slice = neighbours.slice_mut(s![.., 1..]);
slice += &seats.slice(s![.., ..height - 1]);

It seems like either it’s not possible for packages to give error messages that are as good as the compiler’s error messages, or maybe the ndarray package is just not mature enough that they have spent time on refining that.

Another thing that I have trouble with, coming from Python, is that I naively try this:

let arrivals = (&neighbours + &seats == 0) * &tiles;

But this doesn’t compile, because I can’t compare an array with 0. I have to use mapv(|count| count == 0). This would have been horrifying in NumPy because it would be so much slower to call a Python function for each element of the array, but in Rust I suppose it doesn’t matter because it’s compiled! In addition to that, I can’t just multiply an array of numbers by an array of booleans like I could in NumPy, so I have to actually do mapv(|count| (count == 0) as i8).

It’s interesting to note i8 is the type I’ve chosen for my arrays, not u8, because I have to subtract the departures array. I learned a few days ago that it’s awkward to subtract unsigned types in Rust, probably for the best. Speaking of types, I also get a panic on the following line:

break seats.sum();

As an aside, from this panic, I learn to run with RUST_BACKTRACE=1 because the panic occurred in ndarray instead of in the standard library, so I need a backtrace to see what line in my code is causing the panic, instead of what line in ndarray it is occurring at.

It seems that if you take the sum of an i8 array, then the sum is also expected to be an i8. This is inconvenient because it overflows the data type, as might often happen! In Python the sum of a NumPy array is a Python integer no matter what data type the array has:

np.int8([127, 127, 127, 127]).sum() == 508

The sum() method of ndarray doesn’t seem very useful this way! I get around it by converting the array to a larger type with seats.mapv(|e| e as i32).sum(), but that seems wasteful.

In the end, here’s the program that gives me the right answer:

use ndarray::{s, Array2};
use std::fs;

enum Tile {
    FLOOR = 0,
    SEAT = 1,
}

fn main() -> Result<(), io::Error> {
    let file = fs::File::open("input")?;
    let tiles = read_board(file);
    let mut seats = Array2::<i8>::zeros(tiles.raw_dim());

    let occupied = loop {
        let neighbours = calc_neighbours(&seats);
        let arrivals = (&neighbours + &seats).mapv(|count| (count == 0) as i8);
        let departures = &neighbours.mapv(|count| (count >= 4) as i8) * &seats;
        let new_seats = (&seats + &arrivals - &departures) * &tiles;
        if seats == new_seats {
            break seats.mapv(|e| e as i32).sum();
        }
        seats = new_seats;
    };

    println!("Answered: {}", occupied);
    Ok(())
}

fn calc_neighbours(seats: &Array2<i8>) -> Array2<i8> {
    let shape = seats.shape();
    let width = shape[0];
    let height = shape[1];
    let mut neighbours = Array2::<i8>::zeros(seats.raw_dim());
    // Add slices of the occupied seats shifted one space in each direction
    let mut slice = neighbours.slice_mut(s![1.., 1..]);
    slice += &seats.slice(s![..width - 1, ..height - 1]);
    slice = neighbours.slice_mut(s![.., 1..]);
    slice += &seats.slice(s![.., ..height - 1]);
    slice = neighbours.slice_mut(s![..width - 1, 1..]);
    slice += &seats.slice(s![1.., ..height - 1]);
    slice = neighbours.slice_mut(s![1.., ..]);
    slice += &seats.slice(s![..width - 1, ..]);
    slice = neighbours.slice_mut(s![..width - 1, ..]);
    slice += &seats.slice(s![1.., ..]);
    slice = neighbours.slice_mut(s![1.., ..height - 1]);
    slice += &seats.slice(s![..width - 1, 1..]);
    slice = neighbours.slice_mut(s![.., ..height - 1]);
    slice += &seats.slice(s![.., 1..]);
    slice = neighbours.slice_mut(s![..width - 1, ..height - 1]);
    slice += &seats.slice(s![1.., 1..]);
    neighbours
}

fn read_board(file: fs::File) -> Array2<i8> {
    let lines: Vec<String> = read_lines(file).collect();
    let height = lines.len();
    let width = lines[0].len();
    let mut cells = Array2::zeros((width, height));
    for (y, line) in lines.iter().enumerate() {
        for (x, tile) in line.bytes().enumerate() {
            cells[[x, y]] = match tile {
                b'L' => Tile::SEAT as i8,
                b'.' => Tile::FLOOR as i8,
                _ => panic!("Bad tile '{}'", tile),
            };
        }
    }
    cells
}

Day 11, Part 2

Part 2 of the puzzle is a further refinement to the rules: now not only the occupied seats in the cells directly adjacent count, but each cell looks at the nearest seat (occupied or not) in each direction, skipping any floor tiles, so if there is an occupied seat 8 tiles to the right, it will count as a neighbour if there are only floor tiles in between.

Additionally, people now only leave their seat if they have 5 neighbours, instead of 4.

Roughly here’s what I’ll do: first change the departures calculation to check for 5 neighbours instead of 4 if is_part2() is true. Then I’ll write a calc_los_neighbours(seats, tiles) function (“LOS” for “line of sight”) and use that instead of calc_neighbours() if is_part2() is true. That’s all simply done; now the big question is what to write in calc_los_neighbours()!

If this were Python I’d be very concerned about finding a trick that would let me do this without iterating through the array in Python, by composing the available fast NumPy operations. So my first instinct is to do the same in Rust, but actually I think I can probably just do this the easy way because iterating in a compiled language is fast.

One thing I run into while writing this is that I’d like to have an array of the eight directions as a global constant, but putting let directions = &[(-1, -1), (-1, 0), ...]; outside of a function doesn’t work. I google “rust global constant” and find that you have to make it static and cannot infer the type.

static DIRECTIONS: &[(isize, isize)] = &[
    (-1, -1),
    (-1, 0),
    (-1, 1),
    (0, -1),
    (0, 1),
    (1, -1),
    (1, 0),
    (1, 1),
];

fn calc_los_neighbours(seats: &Array2<i8>, tiles: &Array2<i8>) -> Array2<i8> {
    let mut neighbours = Array2::<i8>::zeros(seats.raw_dim());
    for x in 0..seats.nrows() {
        for y in 0..seats.ncols() {
            for dir in DIRECTIONS {
                if let Some(seat) = nearest_seat(tiles, x, y, dir) {
                    neighbours[[x, y]] += seats[seat];
                }
            }
        }
    }
    neighbours
}

fn nearest_seat(
    tiles: &Array2<i8>,
    x: usize,
    y: usize,
    &(dx, dy): &(isize, isize),
) -> Option<(usize, usize)> {
    let mut nx = x;
    let mut ny = y;
    while nx > 0 && nx < tiles.nrows() - 1 && ny > 0 && ny < tiles.ncols() - 1 {
        nx = incdec(nx, dx);
        ny = incdec(ny, dy);
        if tiles[[nx, ny]] == Tile::SEAT as i8 {
            return Some((nx, ny));
        }
    }
    None // if no seat in line of sight in this direction
}

fn incdec(val: usize, delta: isize) -> usize {
    match delta {
        1 => val + 1,
        -1 => val - 1,
        _ => val,
    }
}

The incdec() function might seem like an unnecessary way of doing things, but as on Day 8, you cannot add a signed type to an unsigned type, so I did it this way instead.

I run this and get the wrong answer. That’s unfortunate, as this is going to be difficult to debug, with such large arrays and so many steps. It would be better if I could debug it visually somehow!

To start with, I create a test_input file with the example input from the puzzle, and run my code on that instead. It produces the answer 39, not the correct answer 26.

In order to debug this visually I write a quick function to print the map:

fn print_board(seats: &Array2<i8>, tiles: &Array2<i8>) {
    for (seat_row, tile_row) in seats.genrows().into_iter().zip(tiles.genrows().into_iter()) {
        let row: String = seat_row.iter().zip(tile_row.iter()).map(|(seat, tile)| {
            match *tile {
                0 => '.',
                _ => match *seat {
                    0 => 'L',
                    1 => '#',
                    _ => panic!("Bad data"),
                },
            }
        }).collect();
        println!("{}", row);
    }
    println!("");
}

While doing this I notice that it’s not possible to do the following (as is an unexpected token here):

match *tile {
    Tile::FLOOR as i8 => ...
}

I print out the map on every iteration and I notice that the third iteration is where my program starts to differ from the example. I get this:

######.###
.L.L...L..
#LLLLLLLL#
#L.LLL.LL#
.LL..LLLL#
#L.LLL.LL#
#L.LLL.LL#
..L....LL.
#L.LLL.L.#
##.###.###

Whereas the example has this:2

#.LL.LL.L#
#LLLLLL.LL
L.L.L..L..
LLLL.LL.LL
L.LL.LL.LL
L.LLLLL.LL
..L.L.....
LLLLLLLLL#
#.LLLLLL.L
#.LLLLL.L#

My code keeps all the seats around the edges occupied, but only the corner seats are supposed to be occupied, with a few stragglers on the edges.

At this point I really wish I had an interactive environment to test my functions, like a Jupyter notebook! Luckily, before I resort to too much debug-printing or running it in a debugger, I look carefully at nearest_seat() and notice that I stop the loop when I reach any edge — even if I’m not looking for the nearest seat in the direction of that edge! That’s why I’m finding too few neighbours for the seats on the edge.

I change the loop in nearest_seat() to look like this:

loop {
    if (dx == -1 && nx == 0)
        || (dx == 1 && nx >= xmax)
        || (dy == -1 && ny == 0)
        || (dy == 1 && ny >= ymax)
    {
        break None; // no seat in line of sight in this direction
    }
    nx = incdec(nx, dx);
    ny = incdec(ny, dy);
    if tiles[[nx, ny]] == Tile::SEAT as i8 {
        break Some((nx, ny));
    }
}

Running this gives me the correct answer for the example, and then also for the actual puzzle input.

Afterword

Today’s program seems much less idiomatic than previous days’ programs have been. This is partly because I couldn’t figure out how to have an ndarray of an enum, even if the enum ought to fit into an i8 data type. I think must be implementing the enum incorrectly, since I had to keep repeating Tile::SEAT as i8 and couldn’t even get it to work in a match expression.

But the main reason is probably because I was pretending to write Python code, only doing it in Rust.

I had mixed experiences with the ndarray package. On the one hand, given that I was already familiar with the same concepts from NumPy, it wasn’t too hard to use. On the other hand, the documentation and examples are not quite up to the standards of a lot of other Rust documentation that I’ve seen, and the error messages that it produces are much harder to understand, so it was difficult to make progress today.


[1] Which is also where I got the header image of this blog

[2] Yes, I know I got it rotated

Advent of Rust 10: When All You Have is Itertools, Every Problem Looks like an Iter

Welcome back to episode 10 of the previously-stream-of-consciousness-now-abbreviated log of me trying to teach myself the Rust programming language, stumbling my way through the puzzles from Advent of Code 2020.

I have noticed that by now doing a puzzle each day and writing about it is somewhat tiring. I’ve found myself eager to solve the puzzle in the quickest way possible rather than to use each day’s puzzle as an excuse to learn a new language feature in Rust. But on the other hand I think that’s OK! Despite that, I am still enjoying it and looking forward each day to seeing what the new puzzle is.

It’s just fine to want to solve puzzles in a hacky way; once the puzzle is solved, it’s done!

Day 10, Part 1

The first part of the puzzle is to figure out how to chain “joltage” (a made-up kind of voltage?) adapters together. Each adapter is rated for a different number of “jolts” and they all have to be connected in increasing order such that there is no more than a difference of 3 jolts between them, and all the adapters are used. I think this is a roundabout way of describing that the list has to be sorted in ascending numerical order?!

The answer to the puzzle is the number of adapters with 1 jolt difference between them, times the number of adapters with 3 jolts difference between them. This reminds me of Day 5 when I wanted to find which seat number was missing from a list and so looked for the item that did not have a number one higher than its predecessor.

This sounds like a job for … Itertools!

The initial approach of forging ahead and writing the code that I think will work, compiling it until it runs, and then trying the answer on the website, has worked many times so far, so I try it again now. I will sort the input array, add the device’s built-in adapter which is always 3 jolts higher than the highest adapter in the list, calculate the differences between consecutive elements using tuple_windows(), and then count the number of occurrences of each of those differences.

It’s for the latter step that I spend some time browsing the Itertools documentation to see if there is a method that already does this. The closest I come is to sort the vector of differences and then use group_by() on it, helpfully copying the code from the example usage of group_by() in the documentation, and then count the length of each of the groups.

Here’s the code:

let mut adapters: Vec<u8> = read_lines(file).map(|s| s.parse().unwrap()).collect();
adapters.sort_unstable();
adapters.push(adapters.last().unwrap() + 3); // add built-in adapter

let mut differences: Vec<u8> = adapters
    .iter()
    .tuple_windows()
    .map(|(j1, j2)| j2 - j1)
    .collect();
differences.sort_unstable();

let mut occurrences = vec![0, 0, 0];
for (key, group) in &differences.iter().group_by(|d| *d) {
    occurrences[*key as usize - 1] = group.count();
}

println!("{}", occurrences[0] * occurrences[2]);

Clippy helpfully reminds me to use sort_unstable() instead of sort() for u8 which doesn’t need to preserve the order of equal elements, and to use count() instead of the much less readable collect::<Vec<&u8>>().len(). Also, the * operators that you see in the code above were definitely the compiler’s idea, not mine.

I get an answer and put it into the Advent of Code website, and it’s too low. I print out adapters, differences, and occurrences to see if they make sense, and they do, but I notice the problem: I’ve added the built-in adapter on one end, which is 3 jolts higher than the highest one in the list, but I’ve forgotten to add the charging outlet on the other end, which is always rated 0 jolts. I do this (add adapters.push(0); before the sort) and this time get the right answer.

Before going on to Part 2, I look at this code again and think that maybe this is maybe just a tiny a bit too much Itertools, and I’m trying too hard to be clever. I refactor it into this, which still gives me the correct answer but only iterates through the sorted adapters once:

fn main() -> Result<(), io::Error> {
    let file = fs::File::open("input")?;
    let mut adapters: Vec<u8> = read_lines(file).map(|s| s.parse().unwrap()).collect();
    adapters.push(0); // add charging outlet
    adapters.sort_unstable();
    adapters.push(adapters.last().unwrap() + 3); // add built-in adapter

    let mut ones = 0;
    let mut threes = 0;
    for difference in adapters.iter().tuple_windows().map(|(j1, j2)| j2 - j1) {
        match difference {
            1 => ones += 1,
            3 => threes += 1,
            _ => (),
        }
    }

    println!("{}", ones * threes);
    Ok(())
}

Day 10, Part 2

Part 2 is to figure out the number of possible configurations of adapters with which you can connect the charging outlet to the device. Each adapter must have a higher number than the one before it, but no more than 3 higher.

The way they describe the puzzle, it sounds like brute force is not an option here! I first start thinking of a tree structure, but quickly discard that idea, because if there are trillions of possible configurations, then the tree would need to have trillions of branches.

For quite a long time I stare at the worked example in the puzzle description which has 8 possible configurations, scrolling back and forth between the list of adapters and the list of configurations. In the list of configurations I notice that many of the numbers remain the same because you have only one choice for the adapter that goes there. Looking at all 8 configurations, they all follow this pattern:

0, 1, 4, 5?, 6?, 7, 10, 11?, 12, 15, 16, 19, 22

Only 5, 6 and 11 are optional. Each one may occur or it may not, so that’s 23 = 8 combinations. And in fact, when you have reached adapter 4 you have 3 choices for the next adapter (5, 6, or 7), when you have reached adapter 10 you have 2 choices for the next adapter (11 or 12), and all the other adapters only have one possible choice for the next adapter. So the number of combinations is the product of 2n − 1 for each adapter where n is the number of possible choices for the next adapter.

For a little while I think this is how to get the answer, but then I realize this can’t be true, because according to this formula the answer can only be a power of 2 (since it’s calculated by multiplying powers of 2 together.) The answer to the second worked example, however, is 19280, not a power of 2.

I suppose if you had the sequence 0, 3, 4, 5, 6, 7, 10 then things would be a bit different! (Unlike the first worked example, there are five adapters next to each other in the list with a difference of 1 between them, not four.)

These would be the valid configurations for that sequence:

0, 3, 4, 5, 6, 7, 10
0, 3, 4, 5,    7, 10
0, 3, 4,    6, 7, 10
0, 3, 4,       7, 10
0, 3,    5, 6, 7, 10
0, 3,    5,    7, 10
0, 3,       6, 7, 10

There are 7 of them, clearly not a power of 2. My scheme was thrown off because the number of choices at one adapter can affect the number of choices at another adapter. At 5 you can choose to skip 6, but you can’t skip 6 if you’ve already skipped 4.

I did notice when I debug-printed occurrences in Part 11, that there were no differences of 2 in the list. They were all differences of 1 or 3. My hunch is that a difference of 3 “resets” things, since the two numbers on either side of it must always occur. So we can consider each “run” of ones in isolation.

We know from the original worked example (differences of 1, 3, 1, 1, 1, 3, 1, 1, 3, 1, 3, 3) that a run of one one yields only one choice, a run of two ones yields two choices (10, 11?, 12), a run of three ones yields four choices (4, 5?, 6?, 7), and now we know from my new example above that a run of four ones yields seven choices.

I check what the valid configurations are for a run of five ones, let’s say 0, 3, 4, 5, 6, 7, 8, 11:

0, 3, 4, 5, 6, 7, 8, 11
0, 3, 4, 5, 6,    8, 11
0, 3, 4, 5,    7, 8, 11
0, 3, 4, 5,       8, 11
0, 3, 4,    6, 7, 8, 11
0, 3, 4,    6,    8, 11
0, 3, 4,       7, 8, 11
0, 3,    5, 6, 7, 8, 11
0, 3,    5, 6,    8, 11
0, 3,    5,    7, 8, 11
0, 3,    5,       8, 11
0, 3,       6, 7, 8, 11
0, 3,       6,    8, 11

There are 13 of them. And a run of six ones, let’s say 0, 3, 4, 5, 6, 7, 8, 9, 12:

0, 3, 4, 5, 6, 7, 8, 9, 12
0, 3, 4, 5, 6, 7,    9, 12
0, 3, 4, 5, 6,    8, 9, 12
0, 3, 4, 5, 6,       9, 12
0, 3, 4, 5,    7, 8, 9, 12
0, 3, 4, 5,    7,    9, 12
0, 3, 4, 5,       8, 9, 12
0, 3, 4,    6, 7, 8, 9, 12
0, 3, 4,    6, 7,    9, 12
0, 3, 4,    6,    8, 9, 12
0, 3, 4,    6,       9, 12
0, 3, 4,       7, 8, 9, 12
0, 3, 4,       7,    9, 12
0, 3,    5, 6, 7, 8, 9, 12
0, 3,    5, 6, 7,    9, 12
0, 3,    5, 6,    8, 9, 12
0, 3,    5, 6,       9, 12
0, 3,    5,    7, 8, 9, 12
0, 3,    5,    7,    9, 12
0, 3,    5,       8, 9, 12
0, 3,       6, 7, 8, 9, 12
0, 3,       6, 7,    9, 12
0, 3,       6,    8, 9, 12
0, 3,       6,       9, 12

Here, there are 24 possible combinations. Each time we start with 2n − 1 combinations, but eliminate a few due to having gaps larger than 3.

I don’t really see a pattern in the number of choices that have to be eliminated because of gaps larger than 3:

run lengthchoices
120 = 1
221 = 2
322 = 4
423 − 1 = 7
524 − 3 = 13
625 − 8 = 24
726 − 20 = 44
827 − 47 = 81

I do notice that any combinations eliminated in one row are also eliminated in all subsequent rows, so maybe it could be defined recursively in terms of doubling the previous entry and removing some more rows:

run length nchoices f(n)
11 = 1
22 × f(1) = 2
32 × f(2) = 4
42 × f(3) − 1 = 7
52 × f(4) − 1 = 13
62 × f(5) − 2 = 24
72 × f(6) − 4 = 44
82 x f(7) − 7 = 81

This is starting to make sense. When I write out the combinations in order to count the rows, the number of rows I have to remove each time consists of a pattern from one of the earlier entries but with three missing adapters in front of it. (I’m not sure if this is a good way to explain it, but maybe more visually: to get from the combinations for five ones to the combinations for six ones that I wrote out above, I add one to all the numbers except zero, insert a column of threes, copy all the lines and paste them below the existing lines, delete the threes from the newly-pasted lines, and then delete the last two rows since they start with 0, 3, 7 which is not allowed. The number of rows that I delete at the end corresponds to the number of rows in an earlier iteration of the pattern.) I predict that a run of nine ones is going to produce 149 choices, or 2 × 81 − 13, and when I write them out to make sure, that turns out to be correct: so I’m guessing that for larger n, f(n) = 2 × f(n − 1) − f(n − 4).

This is by no means a mathematical-level rigorous proof, but I have a working hypothesis that successfully predicted the next result, which is good enough for me to start coding. If this were not a one-off puzzle I would start by verifying the worked examples in the puzzle description, but I will just write the code and see if the first answer I get is correct.

I then laugh out loud as I realize that the totally unnecessary use of group_by() in Part 1 is actually a good way to implement Part 2.

let differences = adapters.iter().tuple_windows().map(|(j1, j2)| j2 - j1);
let groups = differences.group_by(|d| *d);
let total: u64 = groups
    .into_iter()
    .filter(|(key, _)| *key == 1)
    .map(|(_, group)| possible_configurations(group.count()))
    .product();
println!("{}", total);

// ...

fn possible_configurations(run_length: usize) -> u64 {
    match run_length {
        n if n < 1 => panic!("Bad value"),
        1 => 1,
        2 => 2,
        3 => 4,
        4 => 7,
        n => 2 * possible_configurations(n - 1) - possible_configurations(n - 4),
    }
}

I stumble over the return value of group_by() not being an iterator, and not having an iter() method like Vec but instead an into_iter() method. And as in Part 1, the *s are all the compiler’s idea.

Running this gives me the correct answer.

Afterword

I am now curious whether all the trouble I went to, to figure out the number of configurations for long runs of adapters with differences of 1 between them, was actually necessary. With a debug print I find that it wasn’t: the longest run of ones in the input is four. (And in hindsight I can tell that the n => line was never reached, because I initially forgot to multiply it by 2, but still got the correct answer!) I guess the lesson here is, when doing programming puzzles, check the input first, and see if you can get away with not handling cases that aren’t present!

That makes two paths that I took, and spent a lot of time on, that weren’t wrong as such, but were unnecessary. (The second one being, all the time I spent in Part 1 looking for an Itertools method that would count the occurrences in differences even though I knew how to write it with a simple for loop.) Both of them were caused by trying to be too clever. I should learn that for these Advent of Code puzzles, a clever solution doesn’t matter, it only matters that it’s correct! I should have taken my own advice that I wrote in the introduction to this blog post.

I also notice that today’s episode has been much more about figuring out what code to write, than about learning Rust. Once I had figured that out, I wrote the code, added whatever & or * operators the compiler told me to, and for the most part it worked.

I still wish I would understand enough to get the & and * operators right the first time. I suspect that if I set up my editor to show Rust types when hovering over an identifier, or something like that, then I’d be more aware of where I was working with a borrowed type, and be able to write the code accordingly.


[1] Debug printing is good for something, after all

Advent of Rust 9: Find That Number, (F)or Else

Welcome again to the not-so-stream-of-consciousness log, where the puns in the titles get worse every day. Today’s topic is the same as every day’s topic: me teaching myself the Rust programming language by doing programming puzzles from Advent of Code 2020.

Day 9, Part 1

Today’s puzzle is to analyze a long list of numbers, pretending that we are breaking an encryption scheme! The answer to the puzzle is the first number in the list (starting at position 26) that is not the sum of two numbers out of the “preamble” consisting of the previous 25 numbers in the list. Wow, that’s a technically correct but very confusing way to say it. Imagine, if you will, a snake moving through the list whose head is one number and whose tail is 25 numbers. If the snake’s head does not equal the sum of any two of the numbers from the snake’s tail, then the head number is the answer.1

As usual I start with cargo new puzzle9, download the input file, and set up puzzle9.rs with the boilerplate, as I did with puzzle8.rs yesterday.

Someone else might know a more efficient way to solve this,2 but I’m going to try to solve it with brute force and Itertools! I will use tuple_windows() to iterate through windows of length 26, and check the tuple_combinations() of the first 25 numbers of the window. I add itertools to Cargo.toml and use itertools::Itertools; to the top of the file.

First I write a map(|s| s.parse().unwrap()) that parses the numbers, then I try to iterate through windows. I’m soon disappointed that tuple_windows() only supports up to a window length of 4! I put the items into a vector instead and implement the window iteration myself, by taking a slice of &numbers[from..to].

Since I need to stop the tuple_combinations() loop when a sum is found, but stop the tuple_windows() loop when the inner loop is not stopped, I am wondering if Rust has a for-else construct like Python does. I google “rust for else” but find that it does not, although I do read that the loop expression (which I am seeing now for the first time) can actually return a value by using break value;, which is something I’ve never encountered before in a programming language! I wonder if the for loop can do this too? I read a bit more and find that no, it cannot.

Ugh, I don’t much like the found = true idiom ever since I learned about Python’s for-else, but nothing to do I guess, unless I want to refactor this into a separate function. And I don’t! I just cram it all in one main() function:

fn main() -> Result<(), io::Error> {
    let file = fs::File::open("input")?;
    let numbers: Vec<u64> = read_lines(file).map(|s| s.parse().unwrap()).collect();

    let window_size = 25;
    let mut answer = None;
    for ix in window_size..numbers.len() {
        let preamble = &numbers[(ix - window_size)..ix];
        let mut valid = false;
        for (a, b) in preamble.iter().tuple_combinations() {
            if a + b == numbers[ix] {
                valid = true;
                break;
            }
        }
        if !valid {
            answer = Some(numbers[ix]);
            break;
        }
    }

    println!("{}", answer.unwrap());

    Ok(())
}

Some interesting mistakes that I made:

  • I originally tried to parse the file as a list of u32 because I didn’t scroll down far enough and see that there were huge numbers, so I got a panic on parse().
  • I made the window_size 5 initially instead of 25, because I was confused with the example given in the text.
  • I forgot all the muts on my variables.
  • I thought I was being clever by making answer an Option, but then I was not clever enough to remember to assert that the answer was actually found, with unwrap().

Despite the mistakes I was happy to see that the compiler could infer the type of parse() without having to specify parse::<u64>().

This program gives me the answer, and so I can unlock Part 2 of the puzzle.

Day 9, Part 2

This is the first Part 2 of a puzzle that actually uses the answer from Part 1! So I don’t need the is_part2() function today.

This time, I must find a contiguous set of at least two numbers in the list that add up to the answer of Part 1. The answer to Part 2 is the sum of the smallest and largest number in that set.

I’m going to have to do a lot more iteration over sliding windows of the list in this one! That tuple_windows() iterator sure would be nice. I do a bit more searching and find what I hadn’t realized before: you can do sliding windows of arbitrary size with windows(), on a slice, just not on an iterator. I’d really prefer to use windows(),3 so maybe I can refactor Part 1 to do that before I write Part 2.

for window in numbers.windows(window_size + 1) {
    let preamble = &window[..window_size];
    let number = *window.last().unwrap();
    let mut valid = false;
    for (a, b) in preamble.iter().tuple_combinations() {
        if a + b == number {
            valid = true;
            break;
        }
    }
    if !valid {
        answer = Some(number);
        break;
    }
}

This is a bit more readable!

Now to write Part 2. I will start with sliding windows of 2 contiguous elements and keep increasing the window size until I find the answer:

fn encryption_weakness(numbers: &[u64], invalid_number: u64) -> Option<u64> {
    for window_size in 2..numbers.len() {
        for window in numbers.windows(window_size) {
            if window.iter().sum::<u64>() == invalid_number {
                return Some(window.first().unwrap() + window.last().unwrap());
            }
        }
    }
    None
}

I get this to compile without too much trouble. I have to specify the type of sum::<u64> and I don’t understand why, similar to an error I got a few days ago. Helpfully, cargo clippy tells me to use &[u64] as the type of the first parameter instead of &Vec<u64>. Nonetheless, it doesn’t work. The answer is wrong, and this time the website doesn’t say if it’s too high or too low (probably because it’s not relevant.) I debug-print the window of numbers to try to get a clue about why the answer is wrong, and I find out that I added the first and last number in the window, not the largest and smallest number as I was supposed to.

This is a nice excuse to use the Itertools minmax() method, which I scrolled past a few days ago and thought was cool! I now read that it has an enum return type, which luckily I learned about yesterday, so I think I should know how to get an answer out of it. I try this:

let itertools::MinMaxResult::MinMax(largest, smallest) = window.iter().minmax();

I wasn’t sure if let with an enum-pattern would even work, but I decided to try it, as I thought I had seen it elsewhere in an example. I originally thought this would assert that the result was not one of the other variants of the enum (NoElements or OneElement.) But instead, the compiler tells me “let bindings require an ‘irrefutable pattern’, like a struct or an enum with only one variant”, and suggests using if let. That seems like a good suggestion, but instead I peeked into the documentation for itertools::MinMaxResult and decided to use into_option() instead:

let (largest, smallest) = window.iter().minmax().into_option().unwrap();

Other than that, it worked well! I got the right answer and solved the puzzle.

Now that I have a nice-looking encryption_weakness() function, I’d really like to refactor Part 1 to remove this horrible valid = true thing. I create a function invalid_number and that lets me return instead of the outer break statement. In addition, I realize that I can use Iterator::any() to get rid of the inner break statement.

Full code:

use itertools::Itertools;
use std::fs;
use std::io::{self, BufRead};

fn main() -> Result<(), io::Error> {
    let file = fs::File::open("input")?;
    let numbers: Vec<u64> = read_lines(file).map(|s| s.parse().unwrap()).collect();

    let answer = invalid_number(&numbers, 25).unwrap();

    println!("Part 1: {}", answer);
    println!("Part 2: {}", encryption_weakness(&numbers, answer).unwrap());

    Ok(())
}

fn invalid_number(numbers: &[u64], window_size: usize) -> Option<u64> {
    for window in numbers.windows(window_size + 1) {
        let preamble = &window[..window_size];
        let number = window[window_size];
        if !preamble
            .iter()
            .tuple_combinations()
            .any(|(a, b)| a + b == number)
        {
            return Some(number);
        }
    }
    None
}

fn encryption_weakness(numbers: &[u64], invalid_number: u64) -> Option<u64> {
    for window_size in 2..numbers.len() {
        for window in numbers.windows(window_size) {
            if window.iter().sum::<u64>() == invalid_number {
                let (largest, smallest) = window.iter().minmax().into_option().unwrap();
                return Some(largest + smallest);
            }
        }
    }
    None
}

fn read_lines(file: fs::File) -> impl Iterator<Item = String> {
    io::BufReader::new(file).lines().map(|res| res.unwrap())
}

Afterword

I solved this puzzle fairly quickly. I can think of two reasons why: I was relatively familiar with Itertools because I’ve been using it often in the past few days, and I also managed to think of a solution for both parts of the puzzle that was able to be implemented by composing parts of Itertools and the standard library that I was already familiar with, or at least knew what to look for.

What can I say? I just love Itertools. I think having practiced solving Advent of Code puzzles with it, will also make me reach for Python’s itertools more often when I’m programming in Python.

Having now written two functions that return Option<u64>, I do wonder how Rust stores this type internally! Is it two 8-byte words with 63 wasted bits, or is it 9 bytes with 7 wasted bits?

I’m liking the abbreviated style that I’ve been using for the past couple of days and I think I’ll continue it.


[1] I’m not sure that’s clear either, but hopefully it will become clear from the code. Code might be difficult to read, but at least it’s unambiguous

[2] Writing this later, I wonder if a more efficient solution would involve sorting the arrays to eliminate some of the combinations? I don’t plan to spend time on it though

[3] Never thought I’d be writing those words on this blog

Advent of Rust 8: Please Make Your Error More Error-y

It’s Day 8 of the no-longer-so-stream-of-consciousness-log of teaching myself the Rust programming language by solving the programming puzzles at Advent of Code 2020.

Today I start off by refactoring my boilerplate code some more. I got loads of friendly advice from Federico Mena Quintero including how to configure Cargo so that the main.rs doesn’t have to be in a subdirectory, some reading material on error handling which I am working my way through, and a talk which I watched last night while washing the dishes, on Rust programs as a dialogue between the programmer and the compiler. A dialogue between the programmer and the compiler is certainly what some of these puzzles have been!

Reorganizing the project structure to be flat is something I’ve wanted to do since Day 1! I create a new project with cargo new puzzle8, but then I delete the src/ directory and create puzzle8.rs in the main puzzle8 directory, and put the following in Cargo.toml:

[[bin]]
name = "puzzle8"
path = "puzzle8.rs"

(I haven’t read anything yet about TOML and am just parroting the examples in the Cargo documentation; in particular, don’t ask me what the double square brackets signify.)

I decide to start with this boilerplate in puzzle8.rs:

use std::env;
use std::fs;
use std::io::{self, BufRead};

fn main() -> Result<(), io::Error> {
    let file = fs::File::open("input")?;
    let lines: Vec<String> = read_lines(file).collect();
    println!("Hello, world! {}", lines.len());

    Ok(())
}

fn is_part2() -> bool {
    env::args().nth(1).map(|val| val == "2").unwrap_or(false)
}

fn read_lines(file: fs::File) -> impl Iterator<Item = String> {
    io::BufReader::new(file).lines().map(|res| res.unwrap())
}

Federico’s advice included moving the fs::File::open() call into the main body. I find this version of the code much shorter and easier to read.

What I’m also doing this week is enabling the Rust documentation in the DevDocs tab that I permanently have open in my browser so that I can search the API documentation more easily. This wouldn’t have been so useful to me in the first few days, since I wouldn’t have understood the documentation very well, but now it is.

Now I’m ready to get started on the puzzle!

Day 8, Part 1

Today’s puzzle involves executing some computer instructions in a made-up assembly language, and figuring out where it goes into an infinite loop. The answer to the puzzle is the value that’s in the accumulator just before the infinite loop starts.

This is exciting, we get to build a tiny virtual machine! That sounds intimidating but there are a few things that make it easy:

  • there are only 3 instruction codes (“opcodes”).
  • there is only one variable (“accumulator”).
  • there are no choices, branches, or side effects, so if you reach the same instruction for the second time, then you know you’re in an infinite loop.

I think I will start by designing a data structure and API for the virtual machine. Instructions can be a tuple of an opcode and a parameter (and looking at the input file, I see parameters greater than +128 and less than -127, but none more than three digits, so i16 seems like a good type for now). The opcodes are nop to do nothing, acc to increase or decrease the accumulator, or jmp to jump to a different instruction. I think this can be represented by an enum, if Rust has such a thing. I google “rust enum” and land on a chapter in the Rust book.

I start with this:

enum Opcode {
    NOP,
    ACC,
    JMP,
}

struct Instruction {
    opcode: Opcode,
    param: i16,
}

Reading a bit further on in the book, I find out something that is surprising to me: enums in Rust are not what is known as enums in other programming languages! They are actually variant data types. So, because the NOP instruction ignores its parameter, I can instead write the following, remembering #[derive(Debug)] from Day 2, and dispense with having a separate struct Instruction:

#[derive(Debug)]
enum Instruction {
    NOP,
    ACC(i16),
    JMP(i16),
}

Then for the virtual machine itself I will need a Vec<Instruction> for the program code, a usize for the program counter (an index pointing to which instruction in the program code is being executed), and a member for the accumulator. The puzzle description doesn’t say how many bits the accumulator is, but let’s give it a fairly large signed integer type: i32. We will also need one bit per instruction to keep track of whether the instruction has been executed before or not. We could store the program code as Vec<(Instruction, bool)>, which would waste a lot of space but be just fine for solving the puzzle. But out of interest, I also take a look at the bitvec package and it seems like it won’t be too difficult to use, so I tentatively decide to try that, and will revert to the tuple approach if I run into problems.

struct VM {
    acc: i32,
    pc: usize,
    code: Vec<Instruction>,
    visited: BitVec,
}

Now I need to decide what methods the virtual machine will have. It will need a method to convert a line of assembly language into an instruction and push the instruction into the code vector. This should probably look like assemble_line(line: &str) -> Result<(), ???>. It will also need a method to run the program until an infinite loop is detected, which I will call run() -> Result<(), ???>. I’m not sure what to put in the ??? types in both cases. In the case of assemble_line(), the possible errors could be that the string is not in the right format, or that the opcode is unknown, or the parameter is out of range. In the case of run(), the possible errors could be that an infinite loop was detected, or that the accumulator overflowed, or any number of other errors that I haven’t thought of.

I think I will need to learn how to define my own error type in Rust, so I google “rust define error type” and land on the “Defining an Error Type” page in Rust by Example and although that helpfully tells me that it’s possible to give parameters to error types, the example doesn’t actually show how to do what I want! My impression a few days ago was that Rust by Example wasn’t all that useful for me, and now that I know a bit more, I think it’s because the examples in Rust by Example tend to be too concise and basic for my purposes. Maybe they would be more useful to jog my memory if I had done these things once before.

The next search result is the Stack Overflow question “How do you define custom Error types in Rust?”. Unfortunately most of the answers to this question consist basically of “I am the author of a crate that lets you do this,” and I’ve gotten burned often enough by “Hey, you should use my npm package for this” that it seems to me I should stay far away from those! The bottom answer does usefully tell me that I don’t actually need to implement the Error trait, I can just use my own enum. It doesn’t show what that looks like, but having just read about enums I think I can figure it out from here.

enum VMError {
    InvalidString(String),
    InvalidOpcode(String),
    InvalidParameter(String),
    InfiniteLoop,
}

impl VM {
    fn assemble_line(&self, line: &str) -> Result<(), VMError> {
        Ok(())
    }

    fn run(&self) -> Result<(), VMError> {
        Ok(())
    }
}

I wonder if I have to write a constructor as well, since I don’t want to have to create a VM object by specifying values for acc, pc, code, and visited. I google “rust constructor” and don’t find a very good resource to answer my question, but I manage to piece together something from a few different resources:

fn new() -> Self {
    VM {
        acc: 0,
        pc: 0,
        code: vec![],
        visited: BitVec::new(),
    }
}

Now that I have the outline, I’d like to start by writing the code for assemble_line(). What this needs to do is take the first three characters of the string and determine the opcode from them, and parse position 4 until the end of the string into the integer parameter. Then it needs to store the resulting Instruction in the code vector, and append a zero to the visited bit vector. Here’s what I come up with:

fn assemble_line(&mut self, line: &str) -> Result<(), VMError> {
    let opcode_string = &line[..3];
    let parameter_string = &line[4..];
    let parameter = parameter_string
        .parse::<i16>()
        .map_err(|_| VMError::InvalidParameter(parameter_string.to_string()))?;
    let instruction = match opcode_string {
        "nop" => Instruction::NOP,
        "acc" => Instruction::ACC(parameter),
        "jmp" => Instruction::JMP(parameter),
        _ => return Err(VMError::InvalidOpcode(opcode_string.to_string())),
    };
    self.code.push(instruction);
    self.visited.push(false);
    Ok(())
}

A few observations:

  • self needs to be mutable, which I had forgotten.
  • It’s actually quite verbose to construct a VMError, so I wonder if I’m doing it right after all. (At first I tried simply InvalidParameter(parameter_string), but the error type needs to own the string.)
  • I don’t need VMError::InvalidString after all, it’s covered by InvalidParameter and InvalidOpcode.

I then try to write some code in main() to test the new function:

fn main() -> Result<(), io::Error> {
    let file = fs::File::open("input")?;
    let mut vm = VM::new();
    for line in read_lines(file) {
        vm.assemble_line(&line)?;
    }
    println!("{:?}", vm.code);

    Ok(())
}

I note happily that if I forget the ? on assemble_line(), the compiler will tell me that the error must be handled, even though the successful case doesn’t return anything. But other than that, I’m sad, because I get this error:

error[E0277]: `?` couldn't convert the error to `std::io::Error`
  --> puzzle8.rs:62:32
   |
58 | fn main() -> Result<(), io::Error> {
   |              --------------------- expected `std::io::Error` because of this
...
62 |         vm.assemble_line(&line)?;
   |                                ^ the trait `std::convert::From<VMError>` is not implemented for `std::io::Error`
   |
   = note: the question mark operation (`?`) implicitly performs a conversion on the error value using the `From` trait
   = help: the following implementations were found:
             <std::io::Error as std::convert::From<std::ffi::NulError>>
             <std::io::Error as std::convert::From<std::io::ErrorKind>>
             <std::io::Error as std::convert::From<std::io::IntoInnerError<W>>>
   = note: required by `std::convert::From::from`

I guess this is what that Stack Overflow answer meant when it said I didn’t have to implement the Error trait if my error types lined up … and they do not line up. I try a few things (like changing the return type of main() to Result<(), impl Error>) and go back to search results for “rust custom error”, but don’t make any progress. Then I realize that there is a section in the Error Handling in Rust blog post that Federico sent me, that is relevant to this. I haven’t reached that part yet, but I skip ahead to it and read it.

Copying some code from that page, I manage to cobble this together:

impl fmt::Display for VMError {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match &*self {
            VMError::InvalidOpcode(opcode) => write!(f, "Unknown opcode {}", opcode),
            VMError::InvalidParameter(param) => {
                write!(f, "Parameter {} not a 16-bit integer", param)
            }
            VMError::InfiniteLoop => write!(f, "Infinite loop detected"),
        }
    }
}

impl Error for VMError {}

impl convert::From<VMError> for io::Error {
    fn from(err: VMError) -> io::Error {
        io::Error::new(io::ErrorKind::Other, err)
    }
}

The & on match &*self confuses me, here’s another lifetime <'_> that I don’t get, and on the whole this is definitely code that I wouldn’t have been able to write without copying it from somewhere, but it works! What I do understand about it is that for the ? operator to be able to convert my custom VMError into io::Error, I need to implement the From<VMerror> trait for io::Error1, and for that trait, VMError also needs to implement Error, and for Error it also needs to implement Display.

On to the run() method! This needs to clear the program counter, accumulator, and visited vector to 0, and execute the instructions one by one, updating the accumulator and program counter as necessary, and marking each one as visited. If the program counter reaches the end of the instructions, then the program is done, but if it reaches an instruction that was already visited, we have hit an infinite loop.

fn run(&mut self) -> Result<(), VMError> {
    self.pc = 0;
    self.acc = 0;
    self.visited.set_all(false);
    let code_length = self.code.len();
    while self.pc < code_length {
        if self.visited[self.pc] {
            return Err(VMError::InfiniteLoop);
        }
        self.visited.set(self.pc, true);
        match self.code[self.pc] {
            Instruction::NOP => self.pc += 1,
            Instruction::ACC(value) => {
                self.acc += value;
                self.pc += 1;
            }
            Instruction::JMP(distance) => self.pc += distance,
        };
    }
    Ok(())
}

The big mistake that I made here is that I can’t add the i16 parameter to self.acc: i32 or self.pc: usize. So I google “rust convert i16 to i32” and find out about the as operator. Writing self.acc += param as i32 works for the accumulator, but self.pc += distance as isize does not (and self.pc += distance as usize would be incorrect); but neither can I make self.pc into an isize instead of usize, because I need it to index into the vectors. What I would really like for this situation is a method that does checked addition of a signed type to an unsigned type, but I browse through the documentation for usize and such a method doesn’t seem to exist. I do find this Stack Overflow answer that has a good implementation that I can copy, though:

fn checked_jump(pc: usize, jump: i16) -> Option<usize> {
    if jump.is_negative() {
        pc.checked_sub(jump.wrapping_abs() as u16 as usize)
    } else {
        pc.checked_add(jump as usize)
    }
}

Then I can change the JMP case to self.pc = checked_jump(self.pc, distance).ok_or(VMError::InvalidJump)? once again gladly using the diagram of Rust Result/Option Transformations.

Now I test this by putting vm.run()?; in my main() function and I do indeed see that an infinite loop error gets printed. I just need to handle this error and print the accumulator, and I’ll have my answer:

let err = vm.run().unwrap_err();
match err {
    VMError::InfiniteLoop => println!("{}", vm.acc),
    _ => return Err(err.into()),
}

I’m sure this is not the most idiomatic way to expect a particular error enum, but I get my answer, and it is correct according to the Advent of Code website. The full code is a bit long so I won’t put it here, but you can scroll down to see it at the end of Part 2.

Day 8, Part 2

Part 2 of the puzzle is to figure out which instruction causes the infinite loop and should be repaired. We know that exactly one instruction has been corrupted, and that it’s either a NOP which was changed to JMP, or vice versa. (So that’s why NOP instructions have parameters!) We also now know that the program is supposed to terminate when the program counter points exactly one past the end of the code. (In Part 1 I assumed that it could point anywhere past the end, even if it was way past.)

First I refactor the Part 1 code. I add the i16 parameter to Instruction::NOP, and this requires writing the match expression as Instruction::NOP(_) =>. Then I check that we don’t jump more than 1 past the end, and return a new VMError::PastTheEnd if we do, by adding this to the end of run():

if self.pc != code_length {
    Err(VMError::PastTheEnd)
} else {
    Ok(())
}

I will have to iterate through all the instructions one by one, flip JMP to NOP and vice versa, and check if the program terminates; if not, flip back. I will add a repair_instruction(pc: &usize) method that will do the flipping:

fn repair_instruction(&mut self, pc: usize) -> bool {
    match self.code[pc] {
        Instruction::NOP(param) => {
            self.code[pc] = Instruction::JMP(param);
            true
        },
        Instruction::ACC(_) => false,
        Instruction::JMP(param) => {
            self.code[pc] = Instruction::NOP(param);
            true
        }
    }
}

I give it a return value so that I know I can skip running the program if the instruction was ACC.

Then I add the following code to main(), to flip each instruction, run the program, and flip back if that didn’t fix the problem:

for pc in 0..vm.code.len() {
    if !vm.repair_instruction(pc) {
        continue;
    }
    if vm.run().is_ok() {
        break;
    }
    vm.repair_instruction(pc);
}
println!("{}", vm.acc);

To my surprise, this all basically runs and gives me the correct answer the first time! I did give repair_instruction() a &usize parameter originally, but it turned out that wasn’t necessary. Fastest Part 2 so far!

Here’s the full code (the day-to-day boilerplate is now so small compared to the rest of the program, I may as well include it):

use bitvec::prelude::*;
use std::convert;
use std::env;
use std::error::Error;
use std::fmt;
use std::fs;
use std::io::{self, BufRead};

#[derive(Debug)]
enum Instruction {
    NOP(i16),
    ACC(i16),
    JMP(i16),
}

#[derive(Debug)]
enum VMError {
    InvalidOpcode(String),
    InvalidParameter(String),
    InvalidJump,
    PastTheEnd,
    InfiniteLoop,
}

impl fmt::Display for VMError {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match &*self {
            VMError::InvalidOpcode(opcode) => write!(f, "Unknown opcode {}", opcode),
            VMError::InvalidParameter(param) => {
                write!(f, "Parameter {} not a 16-bit integer", param)
            }
            VMError::InvalidJump => write!(f, "Negative jump overflow"),
            VMError::PastTheEnd => write!(f, "Positive jump overflow"),
            VMError::InfiniteLoop => write!(f, "Infinite loop detected"),
        }
    }
}

impl Error for VMError {}

impl convert::From<VMError> for io::Error {
    fn from(err: VMError) -> io::Error {
        io::Error::new(io::ErrorKind::Other, err)
    }
}

struct VM {
    acc: i32,
    pc: usize,
    code: Vec<Instruction>,
    visited: BitVec,
}

impl VM {
    fn new() -> Self {
        VM {
            acc: 0,
            pc: 0,
            code: vec![],
            visited: BitVec::new(),
        }
    }

    fn assemble_line(&mut self, line: &str) -> Result<(), VMError> {
        let opcode_string = &line[..3];
        let parameter_string = &line[4..];
        let parameter = parameter_string
            .parse::<i16>()
            .map_err(|_| VMError::InvalidParameter(parameter_string.to_string()))?;
        let instruction = match opcode_string {
            "nop" => Instruction::NOP(parameter),
            "acc" => Instruction::ACC(parameter),
            "jmp" => Instruction::JMP(parameter),
            _ => return Err(VMError::InvalidOpcode(opcode_string.to_string())),
        };
        self.code.push(instruction);
        self.visited.push(false);
        Ok(())
    }

    fn run(&mut self) -> Result<(), VMError> {
        self.pc = 0;
        self.acc = 0;
        self.visited.set_all(false);
        let code_length = self.code.len();
        while self.pc < code_length {
            if self.visited[self.pc] {
                return Err(VMError::InfiniteLoop);
            }
            self.visited.set(self.pc, true);
            match self.code[self.pc] {
                Instruction::NOP(_) => self.pc += 1,
                Instruction::ACC(value) => {
                    self.acc += value as i32;
                    self.pc += 1;
                }
                Instruction::JMP(distance) => {
                    self.pc = checked_jump(self.pc, distance).ok_or(VMError::InvalidJump)?
                }
            };
        }
        if self.pc != code_length {
            Err(VMError::PastTheEnd)
        } else {
            Ok(())
        }
    }

    fn repair_instruction(&mut self, pc: usize) -> bool {
        match self.code[pc] {
            Instruction::NOP(param) => {
                self.code[pc] = Instruction::JMP(param);
                true
            }
            Instruction::ACC(_) => false,
            Instruction::JMP(param) => {
                self.code[pc] = Instruction::NOP(param);
                true
            }
        }
    }
}

// https://stackoverflow.com/a/54035801/172999
fn checked_jump(pc: usize, jump: i16) -> Option<usize> {
    if jump.is_negative() {
        pc.checked_sub(jump.wrapping_abs() as u16 as usize)
    } else {
        pc.checked_add(jump as usize)
    }
}

fn main() -> Result<(), io::Error> {
    let file = fs::File::open("input")?;
    let mut vm = VM::new();
    for line in read_lines(file) {
        vm.assemble_line(&line)?;
    }

    if is_part2() {
        for pc in 0..vm.code.len() {
            if !vm.repair_instruction(pc) {
                continue;
            }
            if vm.run().is_ok() {
                break;
            }
            vm.repair_instruction(pc);
        }
        println!("{}", vm.acc);
    } else {
        let err = vm.run().unwrap_err();
        match err {
            VMError::InfiniteLoop => println!("{}", vm.acc),
            _ => return Err(err.into()),
        }
    }

    Ok(())
}

fn is_part2() -> bool {
    env::args().nth(1).map(|val| val == "2").unwrap_or(false)
}

fn read_lines(file: fs::File) -> impl Iterator<Item = String> {
    io::BufReader::new(file).lines().map(|res| res.unwrap())
}

Afterword

Today’s puzzle went more smoothly than yesterday’s, especially Part 2. The most time-consuming part was figuring out all of the fuss required to make a custom error type that implements the Error trait. That was certainly not as easy as I had expected it would be, and I will probably avoid doing it for future puzzles.

In hindsight, it probably would have been a lot easier if I had used my custom error type only for runtime errors in the VM. Then I wouldn’t have had to implement the Error trait in order to be able to return those errors from main().

The bitvec package, on the other hand, was super easy to use.

Finally, to be clear, unlike in the first few days’ blog posts, I am no longer writing down every mistake that I make! I am still making plenty of mistakes, but I’m finding that it no longer helps me that much to log all of them, because I am starting to understand what the compiler errors mean. This doesn’t mean that I’ve learned quick enough to write all this code without mistakes!


[1] Is adding a trait to a standard library type as bad as monkeypatching a built-in object in JavaScript though? I’m not sure

Advent of Rust 7: What Type is a sum()?

Welcome back to the stream-of-consciousness log of me solving the puzzles at Advent of Code 2020 in order to teach myself the Rust programming language.

This is the end of the first week of learning. The posts are getting shorter, and while I found in the first days that writing about each compiler error helped me think about what might be causing it, now I have usually figured out what’s going on before I finish writing.

So I think today’s might be the last installment in which I go into so much detail about compiler errors; starting this week I’ll post shorter entries, maybe bunched into a few days at a time, that write about the approach I took and what errors were still surprising to me, instead of writing about every time I have to add or delete a & operator. (But if hearing about those details would still be useful to you, now is a good time to let me know!)

Day 7, Part 1

Today’s puzzle is complicated, I have to read the description several times. The input file contains a number of rules about which color bags can hold which other color bags, written in prose. The answer to the puzzle is how many colors of bags can contain a “shiny gold” bag, either directly or by containing other bags which contain the shiny gold bag.

I start with cargo new puzzle7 and copying over the boilerplate from yesterday. Also, I’m not sure I understand exactly what the rules look like, so I download the input file and check what it contains. A lot of lines like this:

light green bags contain 2 pale cyan bags.
dim tan bags contain 3 shiny teal bags, 5 bright white bags, 4 striped bronze bags.
dotted magenta bags contain 2 faded cyan bags, 4 bright yellow bags.
dull silver bags contain 3 striped green bags.

For this puzzle I can ignore how many of each color of bag can be contained (I suspect it will come back in Part 2, though) and focus on which colors can be contained by which other colors.

I will need to figure out how to obtain the rules out of the prose-like sentences in the input file, and I think I will use scan_fmt! for this, so I add it to Cargo.toml.

I don’t immediately get an idea for a data structure to hold this information, so maybe I will work on the string scanning first, and see if I get any ideas about a data structure while I do that. The one thing that I do notice (after thinking about it for a little bit) is that the input file provides information about which colors can contain which other colors, but to answer the puzzle, I need to look up for a given color which colors it can be contained by. So in any case, I will need to reverse the relationships given by the rules.

But first to the string scanning!

for line in read_lines("input")?.map(|s| s.unwrap()) {
    let (container, contents) =
        scan_fmt!(&line, "{[a-z ]} bags contain {[a-z ]}.", String, String)
            .expect(&format!("{} didn't match pattern", line));
    let contained_bags = if contents == "no other bags" {
        vec![]
    } else {
        contents
            .split(", ")
            .map(|bag| {
                scan_fmt!(bag, "{[a-z ]} bag", String)
                    .expect(&format!("{} didn't match pattern", bag))
            })
            .collect::<Vec<String>>()
    };
    println!("{} -> {:?}", container, contained_bags);
}

I googled “rust format string” (as I haven’t actually done that yet, I’ve only formatted strings with println!()) and discover in Rust by Example that there is a format!() macro which works just like println!(). I use this to provide better error messages, since I do expect that I probably haven’t got the scanning patterns correct the first time.

Running cargo clippy suggests using .unwrap_or_else(|_| panic!("{} didn't match pattern", line)) instead of .expect(&format!("{} didn't match pattern", line)) and it even prints a link that I can read which explains why that’s better!

I made a few other typos and left out some & operators, but that stuff is probably boring by now. The one interesting error that I did make is that I originally tried collect::<Vec<&str>>(). I think this was probably due to not thinking hard enough about the type of the vector, rather than misunderstanding something. The compiler error was clear enough: “a value of type Vec<&str> cannot be built from an iterator over elements of type String“.

When I run this code, it panics on the first line of the input file! The line light green bags contain 2 pale cyan bags. doesn’t match the pattern that I gave to scan_fmt!(). Here’s where I would really like to be able to try a few things in a Rust REPL until I get it right. But I have an idea of what might be going wrong. Maybe the matchers in scan_fmt!() are eager, so the first {[a-z ]} matches everything until the end of the string? I try it like this:

let (adjective, color, contents) = scan_fmt!(
    &line,
    "{} {} bags contain {[a-z ]}.",
    String,
    String,
    String
)
.unwrap_or_else(|_| panic!("{} didn't match pattern", line));
let container = format!("{} {}", adjective, color);

(and the same change to the second scan_fmt!() call as well)

Having changed that I get another panic when trying to scan the contained bags. This time it tells me that the empty string didn’t match the pattern. I wonder how I got an empty string? I look at the scan_fmt!() documentation again figure out that {[a-z ]} is probably only matching one character; what I really want is {/[a-z ]+/}. I make this change, but the error still occurs.

I add a println!("{} {} {}", adjective, color, contents); after the first scan_fmt!() call to see what I’m getting. It seems that contents is blank. But, I see that I have forgotten the comma in the regular expression, and what’s more, even though I figured I could ignore the digits for Part 1 of the puzzle, I cannot ignore them when scanning the string, because of course they are still there! 😳

So, I use "{} {} bags contain {/[0-9a-z, ]+/}." for the first pattern, and "{*d} {} {} bag" for the second pattern, and the program runs. I get output such as:

light green -> ["pale cyan"]
dim tan -> ["shiny teal", "bright white", "striped bronze"]
dull aqua -> []

Now, I still have to figure out what data structure to store this in! I’m thinking that if I use a tree, where each node points to the other nodes that can contain that color of bag, then I can start at the node for shiny gold bags and just count the total number of nodes below it. I google “rust tree” and land on the trees package, but that seems more advanced than what I want, and I don’t understand the documentation very well. I also read this article which says it is more aimed at beginners, and from reading it, it seems like trees are fairly difficult to implement in Rust the way that you would in C, but there is a more convenient way to do it using Vec.1

It also occurs to me that I would like to be able to look up bag rules by the color of the bag. If I had a tree, I’d have to search the whole tree to find my shiny gold bag starting point. So maybe a HashMap<String, Vec<String>> is the appropriate data structure, with the key being the color of the bag, and the value being a vector of other bag colors that can contain this bag.

I decide to use the Entry API that I used yesterday to build the tree. I add use std::collections::HashMap; and let mut rules = HashMap::new(); in the appropriate places, and then write this code:

if contents != "no other bags" {
    contents
        .split(", ")
        .map(|bag| {
            let (adjective, color) = scan_fmt!(bag, "{*d} {} {} bag", String, String)
                .unwrap_or_else(|_| {
                    panic!("'{}' ({}) didn't match pattern", bag, contents)
                });
            format!("{} {}", adjective, color)
        })
        .for_each(|color| {
            let mut entry = rules.entry(color).or_insert(vec![]);
            entry.push(container);
        });
};
println!("{:?}", rules["shiny gold"]);

(Yes, unlike a few days ago I now know that iterators have a for_each() method because I found out that there is documentation for the Iterator trait where I can look…) This gives me a few errors:

warning: variable does not need to be mutable
  --> src/main.rs:31:25
   |
31 |                     let mut entry = rules.entry(color).or_insert(vec![]);
   |                         ----^^^^^
   |                         |
   |                         help: remove this `mut`
   |
   = note: `#[warn(unused_mut)]` on by default

error[E0507]: cannot move out of `container`, a captured variable in an `FnMut` closure
  --> src/main.rs:32:32
   |
21 |         let container = format!("{} {}", adjective, color);
   |             --------- captured outer variable
...
32 |                     entry.push(container);
   |                                ^^^^^^^^^ move occurs because `container` has type `String`, which does not implement the `Copy` trait

I remove the mut from entry (I wrote it because it seemed like an entry should be mutable, but then I realize I didn’t have mut yesterday either). The second error actually makes sense. I need to have a different copy of the string for the containing bag in each vector. I can’t remember off the top of my head whether this would be achieved by String::from() so I quickly google “rust copy string” and land right away on the Clone trait, so I add container.clone() to my code.

Now the code runs, but I get a panic in my debug-print of rules["shiny gold"]. This key doesn’t exist in the map! I change the line to print out the entirety of rules to check that the general shape of the data is what I expected; it is. I wonder why there’s no shiny gold?

I try to print rules["clear gray"] which is the last entry in my debug output, so I know it must exist in the map. I still get the panic, so therefore I must be indexing the map wrong. I think I am actually supposed to use get() and not the [] operator (though then why does the code compile?) I change it to rules.get(&"clear gray").expect("Key not present") and get another interesting error:

error[E0277]: the trait bound `String: Borrow<&str>` is not satisfied
  --> src/main.rs:37:32
   |
37 |         println!("{:?}", rules.get(&"clear gray").expect("Key not present"));
   |                                ^^^ the trait `Borrow<&str>` is not implemented for `String`
   |
   = help: the following implementations were found:
             <String as Borrow<str>>

If I’m reading this error message correctly, then I think it says that I can use "clear gray" here and it will be automatically converted to a temporary String to pass to get(), but the same does not happen for &"clear gray". So I remove the &, but then I get back to the panic that I got earlier: “Key not present”.

Maybe it’s get(&String::from("clear gray"))? Same result, that doesn’t work either.

Then I realize it! I accidentally have my debug-print inside the loop, so it’s printing out the rule after every line in the input file, instead of once at the end! So the first time I try to access rules["clear gray"], it hasn’t been inserted yet. I change the print statement back to rules["shiny gold"], move it down one line and indeed, I get a list of bag colors that can contain a shiny gold bag. One step closer to the solution!

Now I need to count the number of bag colors that can contain a shiny gold bag, plus the number of bag colors that can contain those colors of bags, and so on. The downside is that I don’t know whether there are bag colors that can contain each other (or in math-speak, whether the graph is cyclic.) If I knew for sure the graph was acyclic (bag colors can only contain other bag colors that they are not contained by) then I could implement this by just counting the number of elements in each Vec in the node for "shiny gold" and below. There’s an easy way to find out, though; if I try that and the graph is cyclic, then my program will go into an infinite loop, and I’ll notice soon enough! So I decide to try this. I write this function:

fn total_containers_for(rules: &HashMap<String, Vec<String>>, bag_color: &str) -> usize {
    let containers = &rules[bag_color];
    containers.len()
        + containers
            .iter()
            .map(|color| total_containers_for(rules, color))
            .sum()
}

and I try to print out total_containers_for(&rules, "shiny gold") at the end of the program. I get an error that I don’t understand:

error[E0284]: type annotations needed: cannot satisfy `<usize as std::ops::Add<_>>::Output == usize`
  --> src/main.rs:46:9
   |
46 |         + containers
   |         ^ cannot satisfy `<usize as std::ops::Add<_>>::Output == usize`

I stare at this for a while, but I really just don’t get any closer to understanding it. I refactor it into this, to see if the error is in the first or second half of the expression:

let n_direct_containers = containers.len();
let n_indirect_containers = containers
    .iter()
    .map(|color| total_containers_for(rules, color))
    .sum();
n_direct_containers + n_indirect_containers

That changes the error message into something more understandable:

error[E0282]: type annotations needed
  --> src/main.rs:46:9
   |
46 |     let n_indirect_containers = containers
   |         ^^^^^^^^^^^^^^^^^^^^^ consider giving `n_indirect_containers` a type

OK, that I can do! I add : usize to the variable and it compiles. (I’d like to refactor it back into one expression, but I’m not sure how to add a type annotation to only part of an expression, so I leave it like this.)

Now the program runs, but it panics again, in total_containers_for(), at the &rules[bag_color] expression. I add the following debug-prints:2

let mut debug: Vec<&String> = rules.keys().collect();
debug.sort();
println!("{:?}", debug);
let containers = &rules
    .get(bag_color)
    .unwrap_or_else(|| panic!("{} not found in rules", bag_color));

I find that light fuchsia is the key that’s not found, and indeed it’s not there in the sorted list of keys. So now at least I know I am indexing the map correctly, but there’s a bug in my code that puts all the rules into the map. I open the input file and do a search for light fuchsia. It’s only present in one line:

light fuchsia bags contain 1 shiny gold bag, 5 faded beige bags, 2 dark chartreuse bags, 3 light brown bags.

Apparently, nothing is allowed to contain light fuchsia bags! Since it never appears in the second half of a rule, it’s never added to the map. So what I need to do is add all of the colors in the first half of the rule as well. I add this line to the appropriate place:3

rules.entry(container).or_insert(vec![]);

But this is a mistake: it changes the inferred key type of the HashMap from String to &String, making the subsequent inserts invalid! Luckily I learned above that I can clone() the string, so I change it again to:

rules.entry(container.clone()).or_insert(vec![]);

With this, the program runs, and gives me an answer. It’s not over yet, though: the Advent of Code website tells me my answer is too high.

What to do next? I don’t have any immediate ideas about what could be going wrong. I decide to try running the program on the example input given in the puzzle description, to see if I get the right answer on that. I mv input real_input to back up the input, and then change the input file to have the following contents:

light red bags contain 1 bright white bag, 2 muted yellow bags.
dark orange bags contain 3 bright white bags, 4 muted yellow bags.
bright white bags contain 1 shiny gold bag.
muted yellow bags contain 2 shiny gold bags, 9 faded blue bags.
shiny gold bags contain 1 dark olive bag, 2 vibrant plum bags.
dark olive bags contain 3 faded blue bags, 4 dotted black bags.
vibrant plum bags contain 5 faded blue bags, 6 dotted black bags.
faded blue bags contain no other bags.
dotted black bags contain no other bags.

I then run the program again, and get the answer 6, whereas the correct answer is 4. So I add println!("{:?}", rules); to examine the rules map that I’ve generated. It all seems correct with what is in the file, but I think I’ve found the bug: I’m not removing duplicates from the list of bags that can contain shiny gold bags, so I’m counting light red and dark orange twice.

This will take a bit of refactoring! I change total_containers_for() to a new function all_containers_for() which returns a HashSet of bag colors that can contain the requested bag:

fn all_containers_for(rules: &HashMap<String, Vec<String>>, bag_color: &str) -> HashSet<String> {
    let containers = &rules[bag_color];
    let mut colors: HashSet<String> = containers.iter().map(|s| s.clone()).collect();
    for color in containers.iter() {
        let mut indirect_colors = all_containers_for(rules, color);
        colors.extend(indirect_colors.drain());
    }
    colors
}

Then to get my answer I do println!("{}", all_containers_for(&rules, "shiny gold").len());

I also get a suggestion from cargo clippy:

warning: you are using an explicit closure for cloning elements
  --> src/main.rs:46:39
   |
46 |     let mut colors: HashSet<String> = containers.iter().map(|s| s.clone()).collect();
   |                                       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ help: consider calling the dedicated `cloned` method: `containers.iter().cloned()`

Well that’s useful!

This runs (except that I forgot the mut on both of the HashSet variables at first…) and I get the answer 4, as it should be. Hopefully if I run this again on the real input, I’ll get the real answer! I bring back the real input file with mv real_input input, run the program again, and get an answer. This time it’s correct. Phew!

Day 7, Part 2

Let’s hope Part 2 goes a bit faster than Part 1, this has been more difficult than the other days and I’m a bit tired of it!

Part 2 of the puzzle is to consider the rules the other way around. We have to once again start from a shiny gold bag, but this time say how many bags it must contain.

I think it’s best to assemble a different set of rules, since we are looking up the bags in the other direction. I’ll rename the existing rules to container_rules, and introduce a new contains_rules of type HashMap<String, Vec<(String, usize)>>. Then once I have a database of contains_rules, I can write a function total_contained_by() that will give me the total number of bags that must be contained by the given bag; recursively, similar to all_containers_for().

After a few typos and forgotten .clone()s, my main() function looks like this:

fn main() -> Result<(), io::Error> {
    let mut container_rules = HashMap::new();
    let mut contents_rules = HashMap::new();
    for line in read_lines("input")?.map(|s| s.unwrap()) {
        let (adjective, color, contents) = scan_fmt!(
            &line,
            "{} {} bags contain {/[0-9a-z, ]+/}.",
            String,
            String,
            String
        )
        .unwrap_or_else(|_| panic!("{} didn't match pattern", line));
        let container = format!("{} {}", adjective, color);
        container_rules.entry(container.clone()).or_insert(vec![]);
        if contents != "no other bags" {
            contents
                .split(", ")
                .map(|bag| {
                    let (num, adjective, color) =
                        scan_fmt!(bag, "{d} {} {} bag", usize, String, String).unwrap_or_else(
                            |_| panic!("'{}' ({}) didn't match pattern", bag, contents),
                        );
                    (num, format!("{} {}", adjective, color))
                })
                .for_each(|(num, color)| {
                    let container_entry = container_rules.entry(color.clone()).or_insert(vec![]);
                    container_entry.push(container.clone());
                    let contents_entry = contents_rules.entry(container.clone()).or_insert(vec![]);
                    contents_entry.push((num, color));
                });
        };
    }

    if is_part2() {
        println!("{:?}", contents_rules);
    } else {
        println!(
            "{}",
            all_containers_for(&container_rules, "shiny gold").len()
        );
    }

    Ok(())
}

I print out the new contents_rules map with cargo run 2 and it looks like what I might expect. Now I try to write total_contained_by():

fn total_contained_by(rules: &HashMap<String, Vec<(usize, String)>>, bag_color: &str) -> usize {
    rules[bag_color]
        .iter()
        .map(|(num, color)| num * total_contained_by(rules, color))
        .sum()
}

This compiles, but again crashes with a missing key when I run it. I do get a pretty quick idea of what the problem is, though: I’m forgetting to add the entry to contents_rules if the second part of the rule is contains no other bags. I move the let contents_entry = contents_rules.entry(container.clone()).or_insert(vec![]); line up above the if statement and try again. This time, I get an answer of zero! Clearly the wrong answer, because there is this line in the input file:

shiny gold bags contain 5 mirrored lavender bags, 4 shiny maroon bags, 4 striped yellow bags.

So even if those bags contain nothing else, the answer has to be at least 13.

I do a bit of debug-printing and find out that total_contained_by() is always returning zero, no matter what, so that’s why the total answer is zero. It should return zero for bags that don’t contain other bags. But if a bag contains no other bags, then I still have to count that bag itself! So I change the map() line in total_contained_by() to this:

.map(|(num, color)| num * total_contained_by(rules, color) + 1)

Now I get a more realistic answer from the program. I put it into the puzzle website, but it’s still too low. Then I realize that if my bag contains five other bags that each contain no other bags, I still have to count five bags, not one! In other words, I’ve forgotten the parentheses:

.map(|(num, color)| num * (total_contained_by(rules, color) + 1))

(I also check the puzzle description again to make sure I don’t need to count the original shiny gold bag, but I don’t!) Running the program again gives me a much higher answer which is, finally, correct according to the website.

Here’s the full code, but without the boilerplate:

use std::collections::{HashMap, HashSet};

#[macro_use]
extern crate scan_fmt;

fn main() -> Result<(), io::Error> {
    let mut container_rules = HashMap::new();
    let mut contents_rules = HashMap::new();
    for line in read_lines("input")?.map(|s| s.unwrap()) {
        let (adjective, color, contents) = scan_fmt!(
            &line,
            "{} {} bags contain {/[0-9a-z, ]+/}.",
            String,
            String,
            String
        )
        .unwrap_or_else(|_| panic!("{} didn't match pattern", line));
        let container = format!("{} {}", adjective, color);
        container_rules.entry(container.clone()).or_insert(vec![]);
        let contents_entry = contents_rules.entry(container.clone()).or_insert(vec![]);
        if contents != "no other bags" {
            contents
                .split(", ")
                .map(|bag| {
                    let (num, adjective, color) =
                        scan_fmt!(bag, "{d} {} {} bag", usize, String, String).unwrap_or_else(
                            |_| panic!("'{}' ({}) didn't match pattern", bag, contents),
                        );
                    (num, format!("{} {}", adjective, color))
                })
                .for_each(|(num, color)| {
                    let container_entry = container_rules.entry(color.clone()).or_insert(vec![]);
                    container_entry.push(container.clone());
                    contents_entry.push((num, color));
                });
        };
    }

    if is_part2() {
        println!("{}", total_contained_by(&contents_rules, "shiny gold"));
    } else {
        println!(
            "{}",
            all_containers_for(&container_rules, "shiny gold").len()
        );
    }

    Ok(())
}

fn total_contained_by(rules: &HashMap<String, Vec<(usize, String)>>, bag_color: &str) -> usize {
    rules[bag_color]
        .iter()
        .map(|(num, color)| num * (total_contained_by(rules, color) + 1))
        .sum()
}

fn all_containers_for(rules: &HashMap<String, Vec<String>>, bag_color: &str) -> HashSet<String> {
    let containers = &rules[bag_color];
    let mut colors: HashSet<String> = containers.iter().cloned().collect();
    for color in containers.iter() {
        let mut indirect_colors = all_containers_for(rules, color);
        colors.extend(indirect_colors.drain());
    }
    colors
}

Afterword

I had a more difficult time today than I did on the previous days! First I went down a wrong path while working with scan_fmt!() because I didn’t realize the matchers were greedy instead of lazy. Then I had that weird error “cannot satisfy <usize as std::ops::Add<_>>::Output == usize” which threw me for a loop. Finally, I made several mistakes in the logic of the program which I could have made just as easily in other programming languages. I don’t know if this was just a particularly difficult puzzle, or if the puzzles are getting more difficult as we go along, or if I was just having a bad day.

Yesterday and today I’ve not been writing down the instances where I misspelled something or forgot some & operators. Earlier in the week, writing everything out, as it happened, really helped me think about what to do next, but as I mentioned in the beginning it’s not so helpful at this point.

Lastly, I did find that when I got the wrong answer, it was really useful to run the program on the example input in the puzzle, and make sure that I compute the example answer. Thinking about it more, I’m surprised that today is the first time I’ve done this. I think I should do this more often.


[1] Maybe less efficient, but for a one-day programming puzzle, I don’t care

[2] I know, I know, one of these days I will google “rust debugger” instead of printing things. Today is not that day

[3] It seems like there ought to be a more idiomatic way to say “insert if not already existing”, but I don’t know what it is

Advent of Rust 6: Please Continue

It’s that time again, time for the daily stream-of-consciousness log of me trying to teach myself the Rust programming language by doing programming puzzles at Advent of Code 2020.

In yesterday’s installment I talked about how people had been providing helpful and encouraging comments, which I appreciated! This time, I also got one unfriendly comment, complaining how I was increasing GNOME’s dependency on Microsoft with Rust. That’s just nonsense, and I don’t even understand how they got from here to there, but for avoidance of all doubt: this series is unconnected to GNOME or my volunteer work for the GNOME Foundation, and also unconnected to my employer (Igalia, not Microsoft.) It is a learning exercise for me personally.

That unpleasant formality out of the way, let’s get started!

Day 6, Part 1

Once again I start out with cargo new puzzle6 and copy over the boilerplate from yesterday.

Today’s puzzle is about customs forms: there are 26 yes-or-no questions on these forms, marked a to z. In the input file you get lines consisting of the letters for which each passenger on the plane has answered yes. The passengers are divided into groups separated by blank lines, and you need to compute for each group, how many questions were answered yes by at least one person. The answer to the puzzle is the sum of all these counts.

The line-by-line data divided into groups separated by blank lines looks a lot like Day 4, so I can reuse some code from there. Another similarity with Day 4 is that this problem seems to lend itself well to using a HashSet. If I can take the string on each line, and insert all the characters into a HashSet for each group, then I can get the per-group count by counting the number of the elements in the HashSet when we move on to the next group.

Here’s the code that I write:

let mut total = 0;
let mut current = HashSet::new();
for line in read_lines("input")? {
    if line == "" {
        total += current.len();
        current = HashSet::new();
    }
    current.extend(line.bytes());
}
total += current.len();
println!("{}", total);

This doesn’t compile because I forgot that each line is a Result, so I need to handle errors. I add two question marks:

for line in read_lines("input")? {
    if line? == "" {
        total += current.len();
        current = HashSet::new();
    }
    current.extend(line?.bytes());
}

Here I get an error that I haven’t seen yet:

error[E0382]: use of moved value: `line`
  --> src/main.rs:15:24
   |
10 |     for line in read_lines("input")? {
   |         ---- move occurs because `line` has type `std::result::Result<std::string::String, std::io::Error>`, which does not implement the `Copy` trait
11 |         if line? == "" {
   |            ----- `line` moved due to this method call
...
15 |         current.extend(line?.bytes());
   |                        ^^^^ value used here after move
   |
note: this function consumes the receiver `self` by taking ownership of it, which moves `line`

I did read about moving the other day when I was reading about ownership. As far as I can understand here, you can only use the ? operator once on a Result because it moves the value out of the Result. I try instead for line in read_lines("input")?.map(|s| s.unwrap()), and that works…

But I get a panic “No such file or directory” because I’ve forgotten to even download the input file! Once I’ve done that, I run the program again, and I get an answer, which according to the Advent of Code website, is correct!

This is a happy milestone for me. Although I can’t count on being able to write a program that compiles without errors the first time, still, I got most things right and didn’t have to change very much to make it work. I’m also noticing that I have a much better idea of where to look for things in the documentation than I did 6 days ago when I started.

Here’s the full code, without boilerplate:

fn main() -> Result<(), io::Error> {
    let mut total = 0;
    let mut current = HashSet::new();
    for line in read_lines("input")?.map(|s| s.unwrap()) {
        if line == "" {
            total += current.len();
            current = HashSet::new();
        }
        current.extend(line.bytes());
    }
    total += current.len();
    println!("{}", total);
    Ok(())
}

Day 6, Part 2

The second part of the puzzle is the same as the first, but you have to count the number of questions for which everyone in the group answered yes, instead of the questions for which anyone in the group answered yes. And once again like Day 4, this seems like a good opportunity to convert the HashSet of questions for which anyone answered yes, to a HashMap counting the number of people in the group who answered yes to each question.

I start out by reading the HashMap documentation again and notice something that I didn’t notice before: the Entry API. I’m somewhat familiar with this idiom from working on GJS, because it’s used in SpiderMonkey‘s hash maps inside the Firefox browser code. So I’m not actually all that surprised to see it in Rust, which originated as a Mozilla project.

From reading the documentation, it looks like this is how I’d increment the count of an element using the Entry API, inserting it if it wasn’t present yet:

let count = hashmap.entry(element).or_insert(0)
*count += 1;

So I figure what I can do is also keep track of the number of people in each group as I read the lines in from the file, and then when the group ends, change the HashMap into an iterator and filter on the counts that are equal to the number of people in the group — this should mean filtering down to the questions for which every person in the group answered yes.

First I want to refactor the program so that it uses the HashMap to count, but still computes the Part 1 answer. This is my attempt:

fn main() -> Result<(), io::Error> {
    let mut total = 0;
    let mut current = HashMap::new();
    for line in read_lines("input")?.map(|s| s.unwrap()) {
        if line == "" {
            total += count_answers(&current);
            current = HashMap::new();
        }
        for byte in line.bytes() {
            let count = current.entry(byte).or_insert(0);
            *count += 1;
        }
    }
    total += count_answers(&current);
    println!("{}", total);

    Ok(())
}

fn count_answers(group: &HashMap<u8, usize>) -> usize {
    group.len()
}

I’m a bit concerned about whether the compiler will be able to infer the type of the HashMap‘s values, or whether I need to explicitly specify usize, but apparently this is not a problem. It runs the first time, and I get the same answer I had before!

I refactored group.len() into count_answers() because that’s where I’m going to put the logic for Part 2. Here’s the first version that I write:

fn main() -> Result<(), io::Error> {
    let mut total = 0;
    let mut current = HashMap::new();
    let mut group_size = 0;
    for line in read_lines("input")?.map(|s| s.unwrap()) {
        if line == "" {
            total += count_answers(&current, group_size);
            current = HashMap::new();
            group_size = 0;
        }
        for byte in line.bytes() {
            let count = current.entry(byte).or_insert(0);
            *count += 1;
        }
        group_size += 1;
    }
    total += count_answers(&current, group_size);
    println!("{}", total);

    Ok(())
}

fn count_answers(group: &HashMap<u8, usize>, group_size: usize) -> usize {
    if is_part2() {
        group
            .iter()
            .filter(|(_, count): &(u8, usize)| usize == group_size)
            .count()
    } else {
        group.len()
    }
}

The first compiler error is an easily corrected mistake: I meant to write count == group_size, not usize == group_size. The second error is that once again I’ve gotten the type of a tuple in a map() or filter() function wrong: it should be &(&u8, &usize), and I still don’t understand why these pass-by-value parameters have to be borrowed. But I have learned from yesterday that I will need to dereference *count == group_size in that case, because you cannot compare &usize with usize, so I add that as well. But even now I get it wrong: I actually need to dereference it twice, **count == group_size, I guess because the tuple is borrowed as well as the elements of the tuple? This is a bit of a mystery to me.

With that, I can run the program and get an answer. The answer seems like it’s very small, and indeed when I put it into the Advent of Code website I find out that it’s wrong.

I wonder if I should start stepping through it in a debugger, but after staring at it for a while, I find that I’ve forgotten to put continue; inside the if line == "" clause! This was also a bit sloppy in Part 1, but it didn’t matter, because if the line was empty, the for byte in line.bytes() loop would also not run. But now I have group_size += 1 down below that loop, and that’s not supposed to be executed if the line was empty.

I add the continue; and get a different answer, which I put into the website and it’s correct.

Here’s the full code, minus the boilerplate:

use std::collections::HashMap;

fn main() -> Result<(), io::Error> {
    let mut total = 0;
    let mut current = HashMap::new();
    let mut group_size = 0;
    for line in read_lines("input")?.map(|s| s.unwrap()) {
        if line == "" {
            total += count_answers(&current, group_size);
            current = HashMap::new();
            group_size = 0;
            continue;
        }
        for byte in line.bytes() {
            let count = current.entry(byte).or_insert(0);
            *count += 1;
        }
        group_size += 1;
    }
    total += count_answers(&current, group_size);
    println!("{}", total);

    Ok(())
}

fn count_answers(group: &HashMap<u8, usize>, group_size: usize) -> usize {
    if is_part2() {
        group
            .iter()
            .filter(|(_, count): &(&u8, &usize)| **count == group_size)
            .count()
    } else {
        group.len()
    }
}

Afterword

Part 1 went very quickly, and Part 2 took a bit longer. This time there was a more balanced mix of Rust-beginner mistakes (that danged & operator every time!) and “normal” mistakes that I might make in another programming language (forgetting the continue statement).

I do think that I’m leaning very heavily on existing knowledge of things from other programming languages. For example, I guessed that Rust might have a continue statement without looking it up, because of all the other languages that have a continue statement. The knowledge I’m leaning most heavily on comes from C++ (for the general idea of RAII, the types that the language provides, references, and templates), and after that Python (for iterators and the idea of an extensive standard library); not so much from JavaScript or any of the other languages I’ve worked in. I might have mentioned this before, but I think progress would have been much slower had I not already been familiar with C++ and Python.

Onward to Day 7!


[0] No footnotes this time

Advent of Rust 5: Help Arrives

Welcome to the latest installment of the stream-of-consciousness log of me trying to learn the Rust programming language by doing the programming puzzles on Advent of Code 2020.

I’ve noticed that these logs, while still long, are becoming shorter. On Day 1 I wrote 6000 words, on Day 2 5000, and on Day 3 and 4 just under 4000. (Today’s is a bit over 3000.) I think that’s because I’m solving the puzzles with fewer mistakes that I have to write about solving! Eventually I expect that I won’t keep writing one post per day because that level of detail won’t be interesting anymore, but let’s see how today goes.

I start off today having gotten several pieces of advice from commenters on the earlier blog posts and from the Rust ❤️ GNOME chat channel, and will use them to improve the boilerplate read_lines() and is_part2() functions that I copy every day. Jan Alexander Steffens noted that to return an iterator of Strings (the task that I failed at yesterday), I don’t have to specify the exact return type, which is what I struggled with, producing a long unreadable type signature that I couldn’t get correct in the end. Instead, I can specify impl Iterator<Item = String>, meaning that it returns a type that implements the iterator interface and the iterator yields String, but that you don’t care about the particulars. Nice!

Perry Lorier mentioned, among other things, that you can make the return type of main() a Result and so use the ? operator to pass errors back to the caller. This is the concise error handling that I was looking for originally on Day 1! Perry also pointed me at this diagram which looks very complicated, but after studying it a bit, I understand better what Ok() and Some() are for, and how to get from one type to the other. This diagram is particularly helpful for shortening the is_part2() function.

Day 5, Part 1

I start out as usual with cargo new puzzle5, copy over read_lines() and is_part2() from yesterday, and start to refactor them using the new knowledge that others have helped me acquire. After some experimentation which I forget to take notes on (but is mostly dealing with compiler errors telling me that I got the Result and Option types slightly wrong,) I have the following boilerplate to start with:

use std::env;
use std::fs;
use std::io::{self, BufRead};
use std::path;

fn main() -> Result<(), io::Error> {
    let lines = read_lines("input")?.collect::<Result<Vec<_>, _>>()?;

    if is_part2() {
        println!("Part 2");
    } else {
        println!("{:?}", &lines[..10]);
    }

    Ok(())
}

fn is_part2() -> bool {
    env::args().nth(1).map(|val| val == "2").unwrap_or(false)
}

fn read_lines<P>(filename: P) -> io::Result<io::Lines<io::BufReader<fs::File>>>
where
    P: AsRef<path::Path>,
{
    let file = fs::File::open(filename)?;
    Ok(io::BufReader::new(file).lines())
}

The final thing that Perry told me about is cargo clippy, which seems to be a command that checks your code and makes suggestions on how to write it more idiomatically. It tells me, for example, that the .and_then(|val| Some(val == "2") that I had at one point in is_part2(), is more cleanly expressed as .map(|val| val == "2").

Now, on to the puzzle! Today’s puzzle is to figure out seat numbers on a weirdly-numbered airplane, where there are 128 rows with 8 seats each, and your boarding pass has seat designations like FBFBBFFRLR where the first F tells you to go to the front half of the airplane, the second character B tells you to go to the back quarter of the front half, etc. The first 7 characters are F or B, telling you which row to go to, and the last three are similarly L or R telling you which seat in that row to sit in (right or left.) Each seat has a “seat ID” that is row × 8 + seat. The answer to the puzzle is the highest seat ID in the given input file containing boarding pass codes.

I spend a moment thinking about how to calculate the range of row numbers that is the back quarter of the front half. Since the airplane has 128 rows, the ranges will all be powers of 2. I briefly think about using nested match statements but that jogs something in my memory and I think: maybe these are actually binary digits in disguise. So I go to my JavaScript console1 and input the example code FBFBBFFRLR as 0b0101100101 — replacing each F and L with a zero, and B and R with a one, and indeed I get 357, which is the seat ID given in the example. I try the next example, BFFFBBFRRR, which is 0b1000110111 or 567, and it checks out too. If this were a real application I’d want to think about it some more, but as it is, I’m satisfied enough to start writing the program.

There are two approaches I could take here: manually turning each B and R into the appropriate power of 2 and adding them all together, or I could use a string replace, followed by parse() (which I know about from Day 1, and I assume it ought to be able to parse binary numbers as well as decimal.) I decide on the latter. Even though it is probably less efficient, it’s not so inefficient that it will make a difference, and I expect it will be faster to write.

For the first time, I’m feeling like I don’t need to google anything, but instead I can go straight to the API documentation. I need to look at the documentation for String to find out how the replace() method works, and how to specify a different arithmetic base to the parse() method. I also guess that there will probably be an iterator method that will exhaust the iterator and give me the largest item, but if there isn’t then I can write one with reduce(), which I’m familiar with from JavaScript.

First I read about replace() but then I realize that since I’m replacing every character in the string anyway, I don’t need it. I actually need something like map(), which I don’t see in the list of methods. But I do know that map() is an iterator method, and to get an iterator over the characters of a string I can use chars(). Then I see char_indices() which will give me each character along with its position in the string, and that makes me think that it might be easier after all to turn the letters into powers of 2 and add them together. And then I see bytes(), which would be even more appropriate because there are only four possible one-byte characters in the strings, but I don’t see a corresponding byte_indices() method. But anyway, it doesn’t matter, because we can use enumerate() on the iterator returned from bytes().

I will then need to get the sum of the elements in one iterator (the powers of 2), and the greatest element of the other iterator (the boarding pass codes in the file), and so I click through to the Iterator documentation and see that these methods are called sum() and max(), respectively.

There is one thing that I do have to google: how to do exponentiation and/or bit shifts in Rust. I find that there is a left-shift << operator which will work fine for me.

Here’s the program I write:

let lines = read_lines("input")?;
let largest_seat_id = lines.map(|s| code_to_seat_id(s?)).max();
println!("{}", largest_seat_id);

// [...]

fn code_to_seat_id(line: String) -> u16 {
    let maxbyte = line.len() - 1;
    line.bytes()
        .enumerate()
        .map(|(index, byte): (usize, &u8)| {
            let digit = match byte {
                b'B' | b'R' => 1,
                _ => 0,
            };
            digit << (maxbyte - index);
        })
        .sum()
}

I was so hoping that I might have understood things well enough to write a program that ran the first time, but no such luck:

error[E0277]: the `?` operator can only be used in a closure that returns `Result` or `Option` (or another type that implements `Try`)
  --> src/main.rs:12:61
   |
12 |         let largest_seat_id = lines.map(|s| code_to_seat_id(s?)).max();
   |                                         --------------------^^-
   |                                         |                   |
   |                                         |                   cannot use the `?` operator in a closure that returns `u16`
   |                                         this function should return `Result` or `Option` to accept `?`
   |
   = help: the trait `Try` is not implemented for `u16`
   = note: required by `from_error`

error[E0277]: `Option<u16>` doesn't implement `std::fmt::Display`
  --> src/main.rs:13:24
   |
13 |         println!("{}", largest_seat_id);
   |                        ^^^^^^^^^^^^^^^ `Option<u16>` cannot be formatted with the default formatter
   |
   = help: the trait `std::fmt::Display` is not implemented for `Option<u16>`
   = note: in format strings you may be able to use `{:?}` (or {:#?} for pretty-print) instead
   = note: required by `std::fmt::Display::fmt`
   = note: this error originates in a macro (in Nightly builds, run with -Z macro-backtrace for more info)

error[E0631]: type mismatch in closure arguments
  --> src/main.rs:23:10
   |
23 |         .map(|(index, byte): (usize, &u8)| {
   |          ^^^ ----------------------------- found signature of `for<'r> fn((usize, &'r u8)) -> _`
   |          |
   |          expected signature of `fn((usize, u8)) -> _`

error[E0599]: no method named `sum` found for struct `Map<Enumerate<std::str::Bytes<'_>>, [closure@src/main.rs:23:14: 29:10]>` in the current scope
   --> src/main.rs:30:10
    |
23  |           .map(|(index, byte): (usize, &u8)| {
    |                -----------------------------
    |                |
    |                doesn't satisfy `<_ as FnOnce<((usize, u8),)>>::Output = _`
    |                doesn't satisfy `_: FnMut<((usize, u8),)>`
...
30  |           .sum()
    |            ^^^ method not found in `Map<Enumerate<std::str::Bytes<'_>>, [closure@src/main.rs:23:14: 29:10]>`
    |
    = note: the method `sum` exists but the following trait bounds were not satisfied:
            `<[closure@src/main.rs:23:14: 29:10] as FnOnce<((usize, u8),)>>::Output = _`
            which is required by `Map<Enumerate<std::str::Bytes<'_>>, [closure@src/main.rs:23:14: 29:10]>: Iterator`
            `[closure@src/main.rs:23:14: 29:10]: FnMut<((usize, u8),)>`
            which is required by `Map<Enumerate<std::str::Bytes<'_>>, [closure@src/main.rs:23:14: 29:10]>: Iterator`
            `Map<Enumerate<std::str::Bytes<'_>>, [closure@src/main.rs:23:14: 29:10]>: Iterator`
            which is required by `&mut Map<Enumerate<std::str::Bytes<'_>>, [closure@src/main.rs:23:14: 29:10]>: Iterator`

The third and fourth errors I’ve dealt with before; in that case I was missing a & operator on the tuple type of the argument of the function that I passed to map(). Here, though, judging from the error message, it seems I have an & operator that isn’t supposed to be there, so I remove it and the last two error messages disappear. I’m not sure why this is; it seems like the byte should be owned by the string, but maybe bytes are passed by value?

For the first error, I understand why it’s complaining: I need to use unwrap() there, because |s| code_to_seat_id(...) doesn’t return a Result or Option, so I cannot use the ? operator to handle errors.

The second error I do understand what it’s asking me to do, but I don’t understand why, until I go and read the documentation for max() again, and see that it returns an Option which is None in the case where the iterator is empty. This is a really nice example of how Rust forces you to handle all possible errors, because that is definitely a case that I would have forgotten about! So I add an extra ? to the end of that line.

Now I have two new errors:

error[E0277]: `?` couldn't convert the error to `std::io::Error`
  --> src/main.rs:12:79
   |
6  | fn main() -> Result<(), io::Error> {
   |              --------------------- expected `std::io::Error` because of this
...
12 |         let largest_seat_id = lines.map(|s| code_to_seat_id(s.unwrap())).max()?;
   |                                                                               ^ the trait `From<NoneError>` is not implemented for `std::io::Error`
   |
   = note: the question mark operation (`?`) implicitly performs a conversion on the error value using the `From` trait
   = help: the following implementations were found:
             <std::io::Error as From<ErrorKind>>
             <std::io::Error as From<IntoInnerError<W>>>
             <std::io::Error as From<NulError>>
   = note: required by `from`
help: consider converting the `Option<T>` into a `Result<T, _>` using `Option::ok_or` or `Option::ok_or_else`
   |
12 |         let largest_seat_id = lines.map(|s| code_to_seat_id(s.unwrap())).max().ok_or_else(|| /* error value */)?;
   |                                                                               ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

error[E0277]: the trait bound `u16: Sum<()>` is not satisfied
  --> src/main.rs:30:10
   |
30 |         .sum()
   |          ^^^ the trait `Sum<()>` is not implemented for `u16`
   |
   = help: the following implementations were found:
             <u16 as Sum<&'a u16>>
             <u16 as Sum>

It seems that my last adjustment wasn’t correct, the ? unwraps the Option but the return type of main() is Result, not Option. So I guess I can’t directly use the ? operator there either. The compiler suggests providing the Error value using ok_or_else(), but I decide to unwrap() this as well.

I have to stare at the second error for a while, but the () in Sum<()>, which I learned a few days ago means “the empty type”, finally gives me the clue. I have put a semicolon at the end of digit << (maxbyte - index) and if I delete the semicolon, the program works. I’m guessing the semicolon turns that line into a statement which doesn’t do anything, instead of the expression to be returned from the function! This makes it seem like you have to be really careful when writing an inline function without an explicit return type! This seems like something that the compiler could generate a better error message about. For example, my function here is used as an argument to map(), and it seems probable that you would want the mapped function to return a value.

Anyway, the answer I get is the correct answer according to the Advent of Code website, so on to Part 2.

Here’s the correct code (without the boilerplate):

fn main() -> Result<(), io::Error> {
    let lines = read_lines("input")?;
    let largest_seat_id = lines.map(|s| code_to_seat_id(s.unwrap())).max().unwrap();
    println!("{}", largest_seat_id);
    Ok(())
}

fn code_to_seat_id(line: String) -> u16 {
    let maxbyte = line.len() - 1;
    line.bytes()
        .enumerate()
        .map(|(index, byte): (usize, u8)| {
            let digit = match byte {
                b'B' | b'R' => 1,
                _ => 0,
            };
            digit << (maxbyte - index)
        })
        .sum()
}

Day 5, Part 2

Part 2 seems really simple at first glance, but that probably means it’s more difficult than it looks. The puzzle is to find your seat ID. Some seats at the front and the back of the plane are missing, but all the others are full, and you know you are not sitting in the very first or very last seat. So your seat ID is the one that is missing in the input file, but with the IDs on either side of it present.

I think we should probably start by sorting the seat IDs. I look up in the Vec documentation how to sort a vector, and I read under sort() that sort_unstable() is preferred if it’s OK for equal elements to be reordered. We should not have any equal elements at all in this vector anyway, so I use that. I change the main() function into this:

fn main() -> Result<(), io::Error> {
    let lines = read_lines("input")?;
    let seat_ids = lines.map(|s| code_to_seat_id(s.unwrap()));

    if is_part2() {
        let sorted = seat_ids.collect().sort_unstable();
        println!("{:?}", sorted);
    } else {
        let largest_seat_id = seat_ids.max().unwrap();
        println!("{}", largest_seat_id);
    }

    Ok(())
}

There’s one error, suggesting that I should specify the type on collect(), which is actually an error I’ve run into before. Perry explained to me why this happens: collect() can actually do several things, so sometimes you need to specify the type so that it knows which thing you want it to do. I change it to collect::<Vec<u16>>() and the program runs.

I get no output though! Or, to be precise, I get the output () which is the empty type. I go back and read again about what sort_unstable() does: the signature is sort_unstable(&mut self) and I don’t see a return value! So it’s a method that changes the original vector. I change that line to the following, also taking the opportunity to specify the type as an annotation on the variable sorted instead of as a type parameter to collect():

let mut sorted: Vec<u16> = seat_ids.collect();
sorted.sort_unstable();

I run the program and get a bunch of numbers! Looks like it’s working. Theoretically, if I spotted the missing number in here, then I’d have the answer to the problem — but I don’t happen to see it, and I don’t want to search through 800 numbers.

I think a simple way to find out which number is missing would be to iterate through the list and stop at the first number that isn’t equal to the previous number plus one. If this were Python and I was using NumPy, I might have the data in an ndarray, where I could rotate the array by 1 and subtract the rotated array from the original array; but I assume Rust arrays don’t work like that.

Instead I remember seeing a method for examining successive elements in an iterator, when I was browsing the itertools package on Day 1. I go to the documentation and find the method, which is called tuple_windows(). I can use that to iterate over all windows of two adjacent seat numbers, and then use find_position() to give me the first one where the two numbers are not sequential!

Here’s what I write:

let seat_number = sorted
    .iter()
    .tuple_windows()
    .find_position(|seats: &(u16, u16)| seats.1 != seats.0 + 1)
    .unwrap()
    .1
     .0
    + 1;
println!("{}", seat_number);

The .1.0 + 1 at the end is a bit cryptic: find_position().unwrap() will give me a tuple of (position, item) from the iterator, which is iterating over pairs of u16, so the type is something like (usize, (u16, u16)). I add one at the end, because .1.0 gives me the seat before the missing seat, so I add one to get the missing seat ID.

Of course it doesn’t work the first time; I’ve forgotten to add use itertools::Itertools; But after doing that I get the following errors:

error[E0271]: type mismatch resolving `<(u16, u16) as itertools::tuple_impl::TupleCollect>::Item == &u16`
  --> src/main.rs:16:14
   |
16 |             .tuple_windows()
   |              ^^^^^^^^^^^^^ expected `u16`, found `&u16`

error[E0271]: type mismatch resolving `<(u16, u16) as itertools::tuple_impl::TupleCollect>::Item == &u16`
  --> src/main.rs:17:14
   |
17 |             .find_position(|seats: &(u16, u16)| seats.1 != seats.0 + 1)
   |              ^^^^^^^^^^^^^ expected `u16`, found `&u16`
   |
   = note: required because of the requirements on the impl of `Iterator` for `TupleWindows<std::slice::Iter<'_, u16>, (u16, u16)>`

error[E0271]: type mismatch resolving `<(u16, u16) as itertools::tuple_impl::TupleCollect>::Item == &u16`
  --> src/main.rs:14:27
   |
14 |           let seat_number = sorted
   |  ___________________________^
15 | |             .iter()
16 | |             .tuple_windows()
17 | |             .find_position(|seats: &(u16, u16)| seats.1 != seats.0 + 1)
   | |_______________________________________________________________________^ expected `u16`, found `&u16`

I’m still not getting the & operators right! I think this might mean that the type of seats has to be &(&u16, &u16), which I don’t understand, because I just had to remove the & operator from something similar in Part 1! Maybe an explanation that makes sense could be that the tuple_windows() values are borrowed from the original iterator? When I make that change, the errors disappear, and I get a different error:

error[E0277]: can't compare `&u16` with `u16`
  --> src/main.rs:17:59
   |
17 |             .find_position(|seats: &(&u16, &u16)| seats.1 != seats.0 + 1)
   |                                                           ^^ no implementation for `&u16 == u16`
   |
   = help: the trait `PartialEq<u16>` is not implemented for `&u16`

Now this error I find really puzzling. Why shouldn’t I be able to compare a reference to u16 with a u16? I google “rust compare u16 with &u16” and I find a Stack Overflow post with the relevant title “Why isn’t it possible to compare a borrowed integer to a literal integer?” The answer isn’t all that satisfying because I’m skeptical of the rationale that the answer gives, but it does tell me what to do: seats.1.clone() or *seats.1.

I also take the opportunity to refactor the code to use destructuring to get rid of that ugly .1.0:

let (_, (seat_before, _)) = sorted
    .iter()
    .tuple_windows()
    .find_position(|seats: &(&u16, &u16)| *seats.1 != seats.0 + 1)
    .unwrap();
println!("{}", seat_before + 1);

This gives me an answer, which I put in to the Advent of Code website, and it’s correct! Hooray!

Here’s the full code, again minus boilerplate:

use itertools::Itertools;

fn main() -> Result<(), io::Error> {
    let lines = read_lines("input")?;
    let seat_ids = lines.map(|s| code_to_seat_id(s.unwrap()));

    if is_part2() {
        let mut sorted: Vec<u16> = seat_ids.collect();
        sorted.sort_unstable();
        let (_, (seat_before, _)) = sorted
            .iter()
            .tuple_windows()
            .find_position(|seats: &(&u16, &u16)| *seats.1 != seats.0 + 1)
            .unwrap();
        println!("{}", seat_before + 1);
    } else {
        let largest_seat_id = seat_ids.max().unwrap();
        println!("{}", largest_seat_id);
    }

    Ok(())
}

fn code_to_seat_id(line: String) -> u16 {
    let maxbyte = line.len() - 1;
    line.bytes()
        .enumerate()
        .map(|(index, byte): (usize, u8)| {
            let digit = match byte {
                b'B' | b'R' => 1,
                _ => 0,
            };
            digit << (maxbyte - index)
        })
        .sum()
}

Afterword

I am starting to feel more and more confident writing Rust. I do still feel like the code I write is clunky and not idiomatic, and probably will for quite some time yet! So by “confident” I don’t mean I’m a good Rust programmer, but what I mean is I’m just starting to lose the feeling of having no idea what I’m doing.

Work From Home Reaction GIF - Find & Share on GIPHY
This is what Day 1 looked like

It has been very helpful to get comments on these posts, as I was able to put some of the tips to good use today. It’s good to not be learning in a vacuum! Another thing that really made today’s exercises go faster was the experience of getting errors that I had already encountered a few days ago, and knowing roughly how to solve them.


[1] Is there a Rust REPL?

Advent of Rust 4: It’s Hard to Return an Iterator

Welcome again to this stream-of-consciousness log about learning the Rust programming language by doing the programming puzzles in Advent of Code 2020, or as I like to call it, On the Code by Jack Kerouac.1 Let’s get on with it!

Day 4, Part 1

I start with cargo new puzzle4 and copying over the code from yesterday, but this time I’d like to refactor it a bit. I would like to write a function is_part2() that tells you whether the solution for Part 2 of the puzzle was requested or not, and I would like to change read_lines() so that it already does the expect() calls that I am copy-pasting every day, rather than returning a Result of an iterator of Results of strings.

Changing read_lines() really does not work for me. I can’t figure out how to return an iterator from the function! Well, clearly the function is already returning an iterator, but I can’t figure out how to express the iterator that I want to return, as a return type.

What I want is this:

fn read_lines<P>(filename: P) -> ???
where
    P: AsRef<path::Path>,
{
    let file = fs::File::open(filename).expect("Bad file");
    io::BufReader::new(file)
        .lines()
        .map(|s| s.expect("Bad line in file"))
}

where ??? ought to be something like Iterator<String>. But I cannot figure out how to write an iterator type. The iterator types that are returned from standard library functions all seem to be type aliases of some sort. For example, io::Lines is the iterator that lines() returns, and I know it is an iterator of Results of strings, because the documentation says so, but I don’t know how to build my own iterator type.

I google “rust return iterator” and the first result is encouragingly titled “Returning Rust Iterators”. This article suggests asking the compiler by returning the empty type () and letting it suggest what to return instead, so I do that.

Unfortunately, I get a type that I don’t think I can put into my program! The compiler says “expected unit type (), found struct Map<std::io::Lines<BufReader<File>>, [closure@src/main.rs:31:14: 31:46]>” I am guessing that referring to a type by the file in which it’s found and the lines and columns that it spans, is not legal Rust syntax!

So I try poking around with no success. By trying things and following the compiler’s suggestions, I end up with the awkward return type of iter::Map<io::Lines<io::BufReader<fs::File>>, dyn FnMut(io::Result<&String>) -> &String>, but this is still producing errors about lifetimes that I don’t understand. So I give up on this idea.

However, maybe I can write read_lines() so that it at least calls expect() on the io::Lines iterator that it returns:

fn read_lines<P>(filename: P) -> io::Lines<io::BufReader<fs::File>>
where
    P: AsRef<path::Path>,
{
    let file = fs::File::open(filename).expect("Bad file");
    io::BufReader::new(file).lines()
}

To be clear, I don’t really understand the P: AsRef<path::Path> part either. I guess I will try to refactor this again in a few days when I have learned a bit more.

Writing is_part2(), on the other hand, is quite straightforward:

fn is_part2() -> bool {
    let args: Vec<String> = env::args().collect();
    let default = String::from("1");
    let arg = args.get(1).unwrap_or(&default);
    arg == "2"
}

This works, but I actually think that I might be able to make this even nicer by using a match statement. I haven’t encountered the match statement directly yet, but I’ve seen it in several google results over the past few days. I google “rust match syntax”, land here, and come up with this:

fn is_part2() -> bool {
    match env::args().nth(1) {
        Some("2") => true,
        _ => false,
    }
}

This almost works, but I have to replace "2" with String::from("2"), and then the compiler tells me that I have to take it out of the match statement, because function calls are not allowed in pattern matching. So in the end it looks like this:

fn is_part2() -> bool {
    let string2 = String::from("2");
    match env::args().nth(1) {
        Some(string2) => true,
        _ => false,
    }
}

The funny thing is, though, that the compiler warns that string2 is an unused variable in both of the places that it is used! It seems like I haven’t understood this well enough. I google “rust match string” and land on a Stack Overflow question titled “How to match a String against string literals in Rust?”, but that is actually only good for when you know that you already have a String! But I have an Option<String>, so I google “rust match option string”, and find another Stack Overflow post with the topic “How can I pattern match against an Option<String>?”. The helpful answer says this is a known limitation of pattern-matching, but suggests two things to do instead. The second solution looks good to me, so I implement it:

fn is_part2() -> bool {
    match env::args().nth(1) {
        Some(s) if s == "2" => true,
        _ => false,
    }
}

This works, and looks like what I had in mind. Time to start on the puzzle!

Today’s puzzle is processing records that represent “passports”. These records consist of whitespace-separated key:value pairs, and records are separated by blank lines. There are eight possible keys, each consisting of three letters. The cid key is optional, and all the others are required. A record is valid if it contains all the required keys. The answer to the puzzle is the number of valid passports in the input file.

I start out by downloading the input file and put it in the project directory, as usual.

So first I think a bit about how I will process the data into records. My usual approach so far has been to split the file into lines and process each line using a chain of iterators, but maybe it’s better to let go of that approach for today. I could read the whole file into a string and split it on the blank lines in order to get an array where each element is a record, and then process each record. Or I could still process the file line-by-line, and use a for loop while keeping the notion of a “current” record, which I push into a vector when it is completed. I think I like that idea best so far.

The records can be hash sets, where I store the keys. That’s a bit wasteful since really all I need is one bit for each of the 8 possible keys, to tell whether the record has it or not! (I can ignore the values for now, since I only need to look at the keys.) But I decide to be wasteful nonetheless, for two reasons: first, I suspect Part 2 of the puzzle will require me to do something with the values, but if Rust is like other languages, a hash set will be easy enough to refactor into a hash map. Second, stuffing the string keys into a hash set or hash map is simple, and I won’t have to write code that translates key strings into record fields.

To make a first attempt, I google “rust hash set” and read the Rust by Example page. It’s interesting that you don’t have to specify the type of a HashSet, the compiler can figure it out by what you insert into it!

I also have to look in the API documentation for how to split a string on whitespace, but it seems there is conveniently a split_whitespace() method.

Here’s my attempt:

use std::collections::HashSet;
use std::env;
use std::fs;
use std::io::{self, BufRead};
use std::path;

fn main() {
    let mut passports = vec![];
    let mut current = HashSet::new();
    for line in read_lines("input").map(|s| s.expect("Bad line in file")) {
        if line == "" {
            passports.push(current);
            current = HashSet::new();
        }
        current = current.union(get_keys_from_line(&line));
    }

    if is_part2() {
        println!("part 2");
    } else {
        println!("the first passport is {:?}", passports[0]);
    }
}

fn get_keys_from_line(line: &str) -> HashSet<String> {
    let mut new_keys = HashSet::new();
    for pair in line.split_whitespace() {
        new_keys.insert(String::from(&pair[..3]));
    }
    new_keys
}

It looks like I got several & operators right this time, even though I still got one wrong:

error[E0308]: mismatched types
  --> src/main.rs:15:33
   |
15 |         current = current.union(get_keys_from_line(&line));
   |                                 ^^^^^^^^^^^^^^^^^^^^^^^^^
   |                                 |
   |                                 expected `&HashSet<_>`, found struct `HashSet`
   |                                 help: consider borrowing here: `&get_keys_from_line(&line)`
   |
   = note: expected reference `&HashSet<_>`
                 found struct `HashSet<String>`

error[E0308]: mismatched types
  --> src/main.rs:15:19
   |
15 |         current = current.union(get_keys_from_line(&line));
   |                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `HashSet`, found struct `std::collections::hash_set::Union`
   |
   = note: expected struct `HashSet<_>`
              found struct `std::collections::hash_set::Union<'_, _, RandomState>`

I need a & on the return value of get_keys_from_line(), and it appears I didn’t read the documentation of union() well enough because it returns an iterator, not another hash set, so I need to add collect() after it. I’m momentarily confused since I thought collect() created a vector from an iterator, not a hash set! But I see that the examples in the documentation for union() are doing it like that, so I assume it must be OK. I’m also wondering if there isn’t a more idiomatic way to do what I’m trying to do (I’m thinking of Python’s dict.update()) but I decide to leave it for now.

Now I get this error:

error[E0277]: a value of type `HashSet<String>` cannot be built from an iterator over elements of type `&String`
  --> src/main.rs:15:61
   |
15 |         current = current.union(&get_keys_from_line(&line)).collect();
   |                                                             ^^^^^^^ value of type `HashSet<String>` cannot be built from `std::iter::Iterator<Item=&String>`
   |
   = help: the trait `FromIterator<&String>` is not implemented for `HashSet<String>`

At least I think I know enough to understand this error message now; the union() iterator is giving me the &String values that are owned by the original two hash sets (current and the temporary object returned from get_keys_from_line()). I don’t own them, so I can’t insert them into a hash set of values that I’m supposed to own.

Hmm, this is not what I wanted at all. What I actually wanted was an update() method that would move the elements from the second set into the first set. I start to think this might have been easier after all if I’d used 8 bits to store whether the keys were present… 😝

I google “rust hashset update” and land on this encouragingly titled Stack Overflow post: “How can I insert all values of one HashSet into another HashSet?” It comes as a surprise to me that there is an extend() method for this! I guess as the commenter says under that post,

Plus it teaches me that I should not only look at the ‘methods’ section of the doc to find methods, but also into the traits a struct implements.

I guess I’ve learned that too now! Wow, that really is confusing, that a note down at the bottom of the API documentation page saying only impl<T, S> Extend<T> for HashSet<T, S> is actually telling you that there is an extend() method.

Regardless, I change the line to read current.extend(&get_keys_from_line(&line)); and I don’t quite get what I want either:

error[E0716]: temporary value dropped while borrowed
  --> src/main.rs:15:25
   |
12 |             passports.push(current);
   |                            ------- borrow later used here
...
15 |         current.extend(&get_keys_from_line(&line));
   |                         ^^^^^^^^^^^^^^^^^^^^^^^^^ - temporary value is freed at the end of this statement
   |                         |
   |                         creates a temporary which is freed while still in use
   |
   = note: consider using a `let` binding to create a longer lived value

This is another head-scratcher. I don’t see why it should matter that the temporary value is freed, when I thought I was moving all the elements out of it and into current! From reading about ownership yesterday, I thought I understood that ownership of values is always moved into function calls, unless they are borrowed with the & operator.

But while I was browsing the HashSet documentation I do remember coming across the drain() method and wondering if that would be useful. Maybe the problem is that the ownership of the values isn’t getting transferred, and I need to drain() them out of the temporary object so that current owns them. I change the line to current.extend(get_keys_from_line(&line).drain()); and it works!

So, I file away the knowledge that the operation I think of as a.update(b) is written as a.extend(b.drain()) in Rust. I wonder if that is actually the idiomatic way to do it?

Now that I have the data in the form that I wanted, I can write the code to get the answer:

let count = passports.iter().filter(passport_is_valid).count();
println!("{}", count);

// [...]

fn passport_is_valid(passport: &HashSet<String>) -> bool {
    let n_keys = passport.len();
    n_keys == 8 || (n_keys == 7 && !passport.contains("cid"))
}

But this doesn’t work:

error[E0631]: type mismatch in function arguments
  --> src/main.rs:21:45
   |
21 |         let count = passports.iter().filter(passport_is_valid).count();
   |                                             ^^^^^^^^^^^^^^^^^ expected signature of `for<'r> fn(&'r &HashSet<String>) -> _`
...
26 | fn passport_is_valid(passport: &HashSet<String>) -> bool {
   | -------------------------------------------------------- found signature of `for<'r> fn(&'r HashSet<String>) -> _`

error[E0599]: no method named `count` found for struct `Filter<std::slice::Iter<'_, HashSet<String>>, for<'r> fn(&'r HashSet<String>) -> bool {passport_is_valid}>` in the current scope
    --> src/main.rs:21:64
     |
21   |           let count = passports.iter().filter(passport_is_valid).count();
     |                                                                  ^^^^^ method not found in `Filter<std::slice::Iter<'_, HashSet<String>>, for<'r> fn(&'r HashSet<String>) -> bool {passport_is_valid}>`
     |
     = note: the method `count` exists but the following trait bounds were not satisfied:
             `<for<'r> fn(&'r HashSet<String>) -> bool {passport_is_valid} as FnOnce<(&&HashSet<String>,)>>::Output = bool`
             which is required by `Filter<std::slice::Iter<'_, HashSet<String>>, for<'r> fn(&'r HashSet<String>) -> bool {passport_is_valid}>: Iterator`
             `for<'r> fn(&'r HashSet<String>) -> bool {passport_is_valid}: FnMut<(&&HashSet<String>,)>`
             which is required by `Filter<std::slice::Iter<'_, HashSet<String>>, for<'r> fn(&'r HashSet<String>) -> bool {passport_is_valid}>: Iterator`
             `Filter<std::slice::Iter<'_, HashSet<String>>, for<'r> fn(&'r HashSet<String>) -> bool {passport_is_valid}>: Iterator`
             which is required by `&mut Filter<std::slice::Iter<'_, HashSet<String>>, for<'r> fn(&'r HashSet<String>) -> bool {passport_is_valid}>: Iterator`

Well, I saw an error just like this yesterday, and it was a missing & operator on the type of the function parameter. But I already have a & there! I try putting a second one (since the error message also has two of them) and sure enough, it works. I get an answer, but it’s the wrong answer.

According to the Advent of Code website, my answer is too low. I look over my code again and I see that I forgot to add the last passport to my vector of passports! Maybe that’s the problem? I add passports.push(current); below the loop, run the program again, and yes, I get an answer that’s one more than the previous answer. This time, it’s correct according to the website.

Here’s the full code (I’ll start leaving out the definitions of is_part2() and read_lines() each time unless they change, though):

use std::collections::HashSet;

fn main() {
    let mut passports = vec![];
    let mut current = HashSet::new();
    for line in read_lines("input").map(|s| s.expect("Bad line in file")) {
        if line == "" {
            passports.push(current);
            current = HashSet::new();
        }
        current.extend(get_keys_from_line(&line).drain());
    }
    passports.push(current);

    if is_part2() {
        println!("part 2");
    } else {
        let count = passports.iter().filter(passport_is_valid).count();
        println!("{}", count);
    }
}

fn passport_is_valid(passport: &&HashSet<String>) -> bool {
    let n_keys = passport.len();
    n_keys == 8 || (n_keys == 7 && !passport.contains("cid"))
}

fn get_keys_from_line(line: &str) -> HashSet<String> {
    let mut new_keys = HashSet::new();
    for pair in line.split_whitespace() {
        new_keys.insert(String::from(&pair[..3]));
    }
    new_keys
}

Day 4, Part 2

Well, as I suspected, the second part of the puzzle does require looking at the values. So I will start by refactoring the hash set into a hash map, that saves the values as well as the keys.

This refactor is pretty straightforward, I look up the documentation for HashMap to check if the methods are different (contains() has to change to contains_key()) but other than that, I just have to change HashSet to HashMap throughout. (I also originally overlooked that the correct type is HashMap<String, String>, not HashMap<String>, but the compiler helpfully reminded me.)

use std::collections::HashMap;

fn main() {
    let mut passports = vec![];
    let mut current = HashMap::new();
    for line in read_lines("input").map(|s| s.expect("Bad line in file")) {
        if line == "" {
            passports.push(current);
            current = HashMap::new();
        }
        current.extend(get_pairs_from_line(&line).drain());
    }
    passports.push(current);

    if is_part2() {
        println!("part 2");
    } else {
        let count = passports.iter().filter(passport_is_valid).count();
        println!("{}", count);
    }
}

fn passport_is_valid(passport: &&HashMap<String, String>) -> bool {
    let n_keys = passport.len();
    n_keys == 8 || (n_keys == 7 && !passport.contains_key("cid"))
}

fn get_pairs_from_line(line: &str) -> HashMap<String, String> {
    let mut new_pairs = HashMap::new();
    for pair in line.split_whitespace() {
        new_pairs.insert(String::from(&pair[..3]), String::from(&pair[4..]));
    }
    new_pairs
}

Now I can start changing passport_is_valid() to implement the rules for each field. I’ll make it look something like this:

    (n_keys == 8 || (n_keys == 7 && !passport.contains_key("cid")))
        && valid_birth_year(&passport["byr"])
        && valid_issue_year(&passport["iyr"])
        && valid_expiry_year(&passport["eyr"])
        && valid_height(&passport["hgt"])
        && valid_hair_color(&passport["hcl"])
        && valid_eye_color(&passport["ecl"])
        && valid_passport_id(&passport["pid"])

Then I can write a function for each validation criterion. To start with I write all these functions but make them only contain true, so I can write them one by one but still run the program. (This went pretty smoothly although the compiler did have to remind me to add the & operators before passing each passport data field into each function.)

I wonder for a bit whether I should use scan_fmt! like I did on Day 2, or regular expressions, or parse(). I decide that maybe it’s time for me to use some regular expressions in Rust. It’s new for me, would be useful to learn, and these regular expressions will be simple. But for the fields where I need to check that the numbers are between certain ranges, I’ll also need to use parse().

Let’s start at the top. Birth year must be a 4-digit number between 1920 and 2002 inclusive. (What happens to the 17-year-old or 101-year-old travelers?) I google “rust regex” and find out that you need to install a package for regular expressions, so I add regex = "1" to Cargo.toml and use regex::Regex; to my program. I start reading the documentation for the regex package.

I already know regular expression syntax, which will be very helpful for completing this task. The one thing that I should take note of is that patterns match anywhere in the string, so I need to use ^ and $ to anchor them if I only want them to match the whole string. (That is, matching is like re.search() and not re.match() in Python.)

I come up with this as a first attempt:

fn valid_birth_year(byr: &str) -> bool {
    let re = Regex::new(r"^[12]\d{3}$").unwrap();
    if !re.is_match(byr) {
        return false;
    }
    let year = byr.parse::<u16>();
    year >= 1920 && year <= 2002
}

It seems the only thing I’ve forgotten is to unwrap() the result of parse(), which I had learned on Day 1 but forgot about. So I add that. Then, since issue year and expiry year are validated in a very similar way, just with different maximum and minimum years, I extract that into a valid_year() function:

fn valid_birth_year(byr: &str) -> bool {
    valid_year(byr, 1920, 2002)
}

fn valid_issue_year(iyr: &str) -> bool {
    valid_year(iyr, 2010, 2020)
}

fn valid_expiry_year(eyr: &str) -> bool {
    valid_year(eyr, 2020, 2030)
}

fn valid_year(y: &str, min: u16, max: u16) -> bool {
    let re = Regex::new(r"^[12]\d{3}$").unwrap();
    if !re.is_match(y) {
        return false;
    }
    let year = y.parse::<u16>().unwrap();
    year >= min && year <= max
}

(I initially forgot the -> bool on the new function. I’m so used to either not having a return type on functions (Python, JavaScript) or having the return type come before the name (C, C++) that I forget this a lot!)

Next I write a first attempt at valid_height(), using the match statement that I learned earlier today, and browsing the regex documentation to find that I have to use captures() to get the values of the regular expression’s capture groups:

fn valid_height(hgt: &str) -> bool {
    let re = Regex::new(r"^(\d{2,3})(cm|in)$").unwrap();
    let groups = re.captures(hgt);
    let height = groups[1].parse::<u8>().unwrap();
    match &groups[2] {
        "cm" => height >= 150 && height <= 193,
        "in" => height >= 59 && height <= 76,
    }
}

The compiler tells me that I forgot to unwrap() the result from captures(), and after I do that, it tells me that my match pattern is “non-exhaustive” — I guess this means that I don’t provide any instructions for what to do if the unit is neither cm nor in. I remember from earlier that a default case is written as _ =>, so I add _ => false to the match statement.

Now it runs! But it panics at unwrapping the return value of captures(). I look at the captures() documentation again, and it says that it will return None if the regex doesn’t match. So I decide to do some quick’n’dirty println!("{}", hgt) debugging to see what the string is that doesn’t match. It’s 97, without a unit after it, so indeed it doesn’t match. A string that doesn’t match should make the function return false, not panic.

I’m sure there’s a nice idiom for “return if None, unwrap otherwise” that I’m not yet aware of. I google “rust option return if none” and I learn a bit more about the ? operator, but since I’m not returning a Result from this function that doesn’t help me. However, another thing I learn is that the body of a match statement doesn’t actually have to be the same type as the expression! You can put return false in there and it will return from the function. How nice! So, the captures() call becomes:

let groups = match re.captures(hgt) {
    Some(groups) => groups,
    None => return false,
};

Next comes hair color. This is very similar to the year validation that I’ve done already, only without having to parse the string:

fn valid_hair_color(hcl: &str) -> bool {
    let re = Regex::new(r"^#[0-9a-f]{6}$").unwrap();
    re.is_match(hcl)
}

Eye color doesn’t actually need to use a regular expression:

fn valid_eye_color(ecl: &str) -> bool {
    ecl == "amb"
        || ecl == "blu"
        || ecl == "brn"
        || ecl == "gry"
        || ecl == "grn"
        || ecl == "hzl"
        || ecl == "oth"
}

This works, but I wonder if I could take this opportunity to apply something that I think I remember, from reading about match earlier:

fn valid_eye_color(ecl: &str) -> bool {
    match ecl {
        "amb" | "blu" | "brn" | "gry" | "grn" | "hzl" | "oth" => true,
        _ => false,
    }
}

This also works, and looks much nicer!

Finally, there is the passport ID, which is a nine-digit number:

fn valid_passport_id(pid: &str) -> bool {
    let re = Regex::new(r"^\d{9}$").unwrap();
    re.is_match(pid)
}

I should now be able to get my answer! Before I check whether it’s correct on the Advent of Code website, I would like to make one improvement that was mentioned in the regex documentation. Running the program takes an almost noticeably long time, and it’s probably because I’m rebuilding the same Regex objects once for each passport in the file, several hundred times. The documentation mentions you can use the lazy_static package to build them only once, and so I add that to Cargo.toml and follow the example in the regex documentation.

According to the example, I need to add this to the top of the file:

#[macro_use]
extern crate lazy_static;

And change this:

let re = Regex::new(r"^[12]\d{3}$").unwrap();

to this:

lazy_static! {
    static ref YEAR_REGEX: Regex = Regex::new(r"^[12]\d{3}$").unwrap();
}

I initially forget to add the type : Regex and the compiler’s error message isn’t so helpful:

error: no rules expected the token `=`
  --> src/main.rs:57:23
   |
57 |         static ref re = Regex::new(r"^[12]\d{3}$").unwrap();
   |                       ^ no rules expected this token in macro call

I still don’t quite know how macros work in Rust, or why lazy_static! is a macro and not a function, but my guess is that it’s harder to generate good error messages for macros.

I also try to keep the name re for the regular expressions, but the compiler helpfully tells me that it’s bad style for static variables to have lower case names! So I rename them.

My program seems to run faster now, and still gives me the same answer. So I put that answer into the Advent of Code website, and it’s correct! Hooray!

Here’s the program, quite long this time because of all the validation rules:

use regex::Regex;
use std::collections::HashMap;

#[macro_use]
extern crate lazy_static;

fn main() {
    let mut passports = vec![];
    let mut current = HashMap::new();
    for line in read_lines("input").map(|s| s.expect("Bad line in file")) {
        if line == "" {
            passports.push(current);
            current = HashMap::new();
        }
        current.extend(get_pairs_from_line(&line).drain());
    }
    passports.push(current);

    let count = passports.iter().filter(passport_is_valid).count();
    println!("{}", count);
}

fn passport_is_valid(passport: &&HashMap<String, String>) -> bool {
    let n_keys = passport.len();
    (n_keys == 8 || (n_keys == 7 && !passport.contains_key("cid")))
        && (!is_part2()
            || valid_birth_year(&passport["byr"])
                && valid_issue_year(&passport["iyr"])
                && valid_expiry_year(&passport["eyr"])
                && valid_height(&passport["hgt"])
                && valid_hair_color(&passport["hcl"])
                && valid_eye_color(&passport["ecl"])
                && valid_passport_id(&passport["pid"]))
}

fn valid_birth_year(byr: &str) -> bool {
    valid_year(byr, 1920, 2002)
}

fn valid_issue_year(iyr: &str) -> bool {
    valid_year(iyr, 2010, 2020)
}

fn valid_expiry_year(eyr: &str) -> bool {
    valid_year(eyr, 2020, 2030)
}

fn valid_year(y: &str, min: u16, max: u16) -> bool {
    lazy_static! {
        static ref YEAR_REGEX: Regex = Regex::new(r"^[12]\d{3}$").unwrap();
    }
    if !YEAR_REGEX.is_match(y) {
        return false;
    }
    let year = y.parse::<u16>().unwrap();
    year >= min && year <= max
}

fn valid_height(hgt: &str) -> bool {
    lazy_static! {
        static ref HEIGHT_REGEX: Regex = Regex::new(r"^(\d{2,3})(cm|in)$").unwrap();
    }
    let groups = match HEIGHT_REGEX.captures(hgt) {
        Some(groups) => groups,
        None => return false,
    };
    let height = groups[1].parse::<u8>().unwrap();
    match &groups[2] {
        "cm" => height >= 150 && height <= 193,
        "in" => height >= 59 && height <= 76,
        _ => false,
    }
}

fn valid_hair_color(hcl: &str) -> bool {
    lazy_static! {
        static ref HAIR_REGEX: Regex = Regex::new(r"^#[0-9a-f]{6}$").unwrap();
    }
    HAIR_REGEX.is_match(hcl)
}

fn valid_eye_color(ecl: &str) -> bool {
    match ecl {
        "amb" | "blu" | "brn" | "gry" | "grn" | "hzl" | "oth" => true,
        _ => false,
    }
}

fn valid_passport_id(pid: &str) -> bool {
    lazy_static! {
        static ref ID_REGEX: Regex = Regex::new(r"^\d{9}$").unwrap();
    }
    ID_REGEX.is_match(pid)
}

fn get_pairs_from_line(line: &str) -> HashMap<String, String> {
    let mut new_pairs = HashMap::new();
    for pair in line.split_whitespace() {
        new_pairs.insert(String::from(&pair[..3]), String::from(&pair[4..]));
    }
    new_pairs
}

Afterword

I don’t have that much to reflect on, this time. I did still forget the & operators all over the place, but less often than I did on the previous days, and I had a better understanding of the errors when they occurred.

I’m still a bit mystified about why it’s so difficult to express the type of an iterator in Rust. It seems like it shouldn’t be that hard, so maybe I’m missing something or approaching it the wrong way?

Finally, it seems like I’m reading the API documentation more often, and googling less. I think this is a sign that I have a better idea of where to look and what I’m looking for in the API documentation, but googling is still useful when I need to figure out how to do something that’s not covered by the examples in the API documentation, like a.extend(b.drain()).


[1] I don’t, in fact, like to call it that

Advent of Rust 3: Once in ‘a Lifetime

Well, this is another long stream-of-consciousness chronicle of my attempt to learn how to program in Rust by doing the daily programming puzzles on Advent of Code 2020. It’s long, but on the plus side, this is the first time ever that I’ve published two blog posts in two days, let alone three in three days. And you know what they say, if I’d had more time, I would’ve written you a shorter letter.

I thought a bit about why it should even be interesting or valuable to write about my mistakes and thought process. Or put more bluntly, isn’t this just a waste of time? Who is this useful for?

Well, for one thing, at my job I’ve been working on Temporal, a standards-track proposal to add a modern API for dates and times to the JavaScript language. Earlier this year I conducted a survey of people who had tried out the proposed Temporal API, and one of the purposes was to try to figure out what was easy to understand and what was hard, for someone coming to Temporal with no prior knowledge. Even though I had been in exactly that position myself only a few months before, I had become so accustomed to using Temporal that I could literally remember nothing of my own experience.

It’s sometimes called the curse of knowledge. I’m sure I will look back in a year, or two years, when I have written lots of Rust code, and not remember any of this either, and I’ll be glad that I wrote it down. But maybe it’ll be valuable in the meantime to someone else!

Day 3, Part 1

Today we get a roguelike puzzle! We are sliding on a toboggan down a horizontally repeating grid of open spaces (.) and trees (#) that is defined in our input file. We slide at a certain angle (3 cells across for every 1 cell down), and the answer to Part 1 is how many trees we crash into by the time we get to the bottom.

By this time I’m familiar with how to start — cargo new puzzle3, download the input file and put it in the project directory, and copy the relevant code from yesterday. This time I’m not only copying the read_lines() function, but also the code that determines from the command line argument whether I want to run the code for Part 1 or Part 2.

Here’s what I start out with:

use std::env;
use std::fs;
use std::io::{self, BufRead};
use std::path;

fn main() {
    let args: Vec<String> = env::args().collect();
    let mut part2 = false;
    let default = String::from("1");
    let arg = args.get(1).unwrap_or(&default);
    if arg == "2" {
        part2 = true;
    }
    let lines: Vec<String> = read_lines("input")
        .expect("Bad file")
        .map(|s| s.expect("Bad line in file"))
        .collect();
    println!("grid is {} × {}", lines[0].len(), lines.len());
}

fn read_lines<P>(filename: P) -> io::Result<io::Lines<io::BufReader<fs::File>>>
where
    P: AsRef<path::Path>,
{
    let file = fs::File::open(filename)?;
    Ok(io::BufReader::new(file).lines())
}

I still made a few minor mistakes when adapting this code from yesterday’s code: I forgot to add the Vec<String> type to lines, I forgot to handle errors with .map(|s| s.expect("Bad line in file")), and I guessed wrong that the length of a vector was length() and not len(). Happily, I am getting accustomed enough to this, that I’m able to correct those mistakes fairly quickly.

I will once again use my approach from the last two days, where I first try to get the data into the right data structure. Now that I’m no longer struggling with knowing what data structures even exist in Rust, and how do I even write Rust code, I can afford to think about this before I start writing any code.

It seems like the appropriate data structure is a two-dimensional array of booleans – true if there is a tree in the cell, false if the cell is an open space. I don’t know if Rust has two-dimensional arrays or vectors, so I first start by googling “rust two dimensional array”. I find several results (1, 2, 3, and the array2d package) but none of them really stand out as saying “this is the way to do it.”

What I do understand so far is that I’d use an array if the size was known at compile time, and a Vec of Vecs if I wanted to have variable-length rows or columns. The array2d package from my search results does look interesting because it seems like it gives you a rectangular array, where the length of each row and column is the same for the whole array, but doesn’t necessarily have to be known at compile time. In theory I do know the width and length at compile time, because I can look in the file and count the number of lines and the length of each line! I have a feeling that that would make my code too tied-up with this particular data file, though, and might mean that I would have to refactor the whole thing for Part 2, so I’d prefer not to take that approach.

(I think briefly about using a one-dimensional array and checking through it with a stride of width + 3, but because the grid repeats in the horizontal direction, I think that wouldn’t work.)

Taking the two-dimensional array approach would mean that unlike yesterday, I would not use iterators very much. Hmm, I feel like I’ve just gotten comfortable with iterators in Rust, I wonder what a solution would look like if it were based on iterators?

Maybe that would actually be easier! Thinking about it some more, I don’t actually need to store the entire grid in a 2-D array. I just need to read in each row, figure out my horizontal position on that row, and store a boolean indicating whether I have hit a tree on that row. I believe it can be done just by operating on the string representing each row, with a map(), filter(), and count().

Let’s see if my guess about how to do it is correct. Here’s the first version that I come up with:

fn main() {
    // [...args...]
    let trees_hit = read_lines("input")
        .expect("Bad file")
        .enumerate()
        .filter(hits_tree)
        .count();
    println!("{}", trees_hit);
}

fn hits_tree(row_index: usize, row: String) -> bool {
    let col_index = row_index * 3 % row.len();
    row.as_bytes()[col_index] == '#'
}

Here, I’m assuming that it’s OK to index the string as bytes, because the only characters allowed are # and .. (I learned from yesterday’s exercise what the difference was between indexing a string by byte and iterating through it by character.) I’m taking a guess that '#' (with single quotes instead of double quotes) will give me a single byte rather than a string, like it does in C.

The compiler gives me quite a lot of errors, but I think I know what most of them mean:

error[E0593]: function is expected to take 1 argument, but it takes 2 arguments
  --> src/main.rs:17:17
   |
17 |         .filter(hits_tree)
   |                 ^^^^^^^^^ expected function that takes 1 argument
...
22 | fn hits_tree(row_index: usize, row: String) -> bool {
   | --------------------------------------------------- takes 2 arguments

error[E0599]: no method named `count` found for struct `Filter<Enumerate<std::io::Lines<BufReader<File>>>, fn(usize, String) -> bool {hits_tree}>` in the current scope
    --> src/main.rs:18:10
     |
18   |           .count();
     |            ^^^^^ method not found in `Filter<Enumerate<std::io::Lines<BufReader<File>>>, fn(usize, String) -> bool {hits_tree}>`
     |
     = note: the method `count` exists but the following trait bounds were not satisfied:
             `<fn(usize, String) -> bool {hits_tree} as FnOnce<(&(usize, std::result::Result<String, std::io::Error>),)>>::Output = bool`
             which is required by `Filter<Enumerate<std::io::Lines<BufReader<File>>>, fn(usize, String) -> bool {hits_tree}>: Iterator`
             `fn(usize, String) -> bool {hits_tree}: FnMut<(&(usize, std::result::Result<String, std::io::Error>),)>`
             which is required by `Filter<Enumerate<std::io::Lines<BufReader<File>>>, fn(usize, String) -> bool {hits_tree}>: Iterator`
             `Filter<Enumerate<std::io::Lines<BufReader<File>>>, fn(usize, String) -> bool {hits_tree}>: Iterator`
             which is required by `&mut Filter<Enumerate<std::io::Lines<BufReader<File>>>, fn(usize, String) -> bool {hits_tree}>: Iterator`

error[E0308]: mismatched types
  --> src/main.rs:24:34
   |
24 |     row.as_bytes()[col_index] == '#'
   |                                  ^^^ expected `u8`, found `char`

The first error is probably because I need to make hits_tree() take a tuple of (row_index, row) as its one argument, instead of two arguments. The second error (reminiscent of those long template errors that you get from C++ compilers) I don’t understand, but it seems like it might be a consequence of the first error, and might go away if I solve that one? The third error shows that my guess that '#' is a byte, is wrong. I was close, it is a char, but a byte is type u8.

The third error seems like the easiest to solve, so first I google “rust byte literal” and land here, which makes me think that b'#' might be correct — and it is!

Next I need to make hits_tree() take a tuple as an argument. I wonder if I can destructure this tuple as I would be able to in JavaScript: function hits_tree([row_index, row]) { ... } I google “rust tuple function argument”, and I get this Stack Overflow answer which makes me think that I should be able to do (row_index, row): (usize, String).

But before I run that, I would like to try to get the & operator right this time. After yesterday, when every time I compiled my code, the compiler told me to add a &, I did spend some time reading the “Understanding Ownership” page. Now I feel like I should be better equipped to avoid these mistakes, or at least understand them when I do make them.

So for the first time in this series, I actually go to the API documentation for a function intentionally, instead of googling it and landing there! First I check enumerate() to check that usize is really the correct type for the index (it is,) then I check lines() to check that String is really the correct type for the row (it isn’t.) The type is actually io::Result<String> which reminds me that I need to expect() the value, so I add .map(|s| s.expect("Bad line in file")) before the call to enumerate().

Then there’s the question of whether the row parameter should be a reference or not. I remember reading this:

A more experienced Rustacean would write [s: &str] instead [of s: &String] because it allows us to use the same function on both &String values and &str values.

But on the other hand, I’m not sure that this parameter is actually a reference! It seems to me that since we get a io::Result<String> from read_lines(), the ownership of the string is passed from function to function in the iterator chain, so I would guess (but with only a little more than 50% confidence)1 that String is correct and &str is not. So I make the change of (row_index, row): (usize, String) and run it.

Unfortunately, sitting down and thinking about it is rewarded with an error that I really don’t understand:

error[E0631]: type mismatch in function arguments
  --> src/main.rs:18:17
   |
18 |         .filter(hits_tree)
   |                 ^^^^^^^^^ expected signature of `for<'r> fn(&'r (usize, String)) -> _`
...
23 | fn hits_tree((row_index, row): (usize, String)) -> bool {
   | ------------------------------------------------------- found signature of `fn((usize, String)) -> _`

I know from the reading I’ve done that 'r is a “lifetime”, but the page that I read told me that lifetimes were an advanced feature that would be explained later in the Rust book. Oops, I guess I should have read that chapter too!

I wonder if I can just fake it ’til I make it, by adding for<'r> and &'r to the function signature as the compiler is suggesting. I try that, but it’s a syntax error, “expected item, found keyword for“. I try removing the for<'r>, and I get another error about “unexpected lifetime” which makes me think that I should put the &'r on (usize, String) instead of (row_index, row). (That makes sense, somewhat, because it’s part of the type, not part of the destructured function arguments.) So I try that, and I get another error, but this one tells me exactly what to do:

error[E0261]: use of undeclared lifetime name `'r`
  --> src/main.rs:23:33
   |
23 | fn hits_tree((row_index, row): &'r (usize, String)) -> bool {
   |             -                   ^^ undeclared lifetime
   |             |
   |             help: consider introducing lifetime `'r` here: `<'r>`

Sure enough, when I add <'r>, it works (with some warnings about not using the part2 variable, which I’ll use soon enough) and I get a number out! I put the number into the Advent of Code website and it’s correct!

The lifetime thing is fairly unsatisfying: I have no idea what it does, why it’s necessary, or why it’s even called r!

I’ll try one more thing. Maybe I was wrong about the row needing to be a String. For example, I look back at yesterday’s code and see fn parse_line(line: &str), so maybe in today’s code I also need &str. So I try changing the function signature to fn hits_tree((row_index, row): (usize, &str)) -> bool, without any lifetimes. But I get the old errors back. I do notice one interesting thing in the error message this time:

error[E0631]: type mismatch in function arguments
  --> src/main.rs:18:17
   |
18 |         .filter(hits_tree)
   |                 ^^^^^^^^^ expected signature of `for<'r> fn(&'r (usize, String)) -> _`
...
23 | fn hits_tree((row_index, row): (usize, &str)) -> bool {
   | ----------------------------------------------------- found signature of `for<'r> fn((usize, &'r str)) -> _`

Now, for some reason, it thinks that my function signature already has a lifetime in it, even though I didn’t put one in! I wonder if the lifetime is implicitly when you include a reference. But it definitely wants a String and not a str. So I try changing the type of the argument to (usize, &String) without the lifetime. That doesn’t work either, but interestingly it does continue to think that the type of my function includes a lifetime. It’s telling me that the reference needs to be on the tuple, not on the string, so I try &(usize, String), once more without a lifetime, and that works.

So the message about having to add a lifetime was strange and confusing, but it turns out that I didn’t need to have it after all. Unfortunately I had to discover this by putting & operators in random places until my code compiled, which I had intended to stop doing today ☹️

On the plus side, I got the correct answer, so that’s the end of Part 1! Here’s the full code:

use std::env;
use std::fs;
use std::io::{self, BufRead};
use std::path;

fn main() {
    let args: Vec<String> = env::args().collect();
    let mut part2 = false;
    let default = String::from("1");
    let arg = args.get(1).unwrap_or(&default);
    if arg == "2" {
        part2 = true;
    }
    let trees_hit = read_lines("input")
        .expect("Bad file")
        .map(|s| s.expect("Bad line in file"))
        .enumerate()
        .filter(hits_tree)
        .count();
    println!("{}", trees_hit);
}

fn hits_tree((row_index, row): &(usize, String)) -> bool {
    let col_index = row_index * 3 % row.len();
    row.as_bytes()[col_index] == b'#'
}

fn read_lines<P>(filename: P) -> io::Result<io::Lines<io::BufReader<fs::File>>>
where
    P: AsRef<path::Path>,
{
    let file = fs::File::open(filename)?;
    Ok(io::BufReader::new(file).lines())
}

Day 3, Part 2

My guess was that Part 2 of the puzzle might be to do the same thing but with the toboggan at a sharper angle such that you would have to skip rows entirely. (For example, 1 right for every 3 down.) I was both right and wrong. It’s actually that you have to check a list of five angles including a sharper one that makes you skip rows, and the answer to the puzzle is the results from those angles all multiplied together. So, my approach of using iterators for the whole thing should actually be refactored, because I don’t want to read the file five times!

I briefly think about using array2d to store the map of the trees after all, but I decide that Vec<String> would be more convenient since I can get it from my existing iterator pipeline by capping it after the expect() call with collect(), and I expect my existing code will continue to work on that with few modifications.

So before I start on Part 2 I decide to refactor it this way:

let landscape: Vec<String> = read_lines("input")
    .expect("Bad file")
    .map(|s| s.expect("Bad line in file"))
    .collect();

let trees_hit = landscape.iter().enumerate().filter(hits_tree).count();

But oh no…

error[E0631]: type mismatch in function arguments
  --> src/main.rs:19:57
   |
19 |     let trees_hit = landscape.iter().enumerate().filter(hits_tree).count();
   |                                                         ^^^^^^^^^ expected signature of `for<'r> fn(&'r (usize, &String)) -> _`
...
23 | fn hits_tree((row_index, row): &(usize, String)) -> bool {
   | -------------------------------------------------------- found signature of `for<'r> fn(&'r (usize, String)) -> _`

OK, I’m back to adding & operators in random places! At least as far as I can tell from the error message, I will need to keep the one on the tuple, and add a second one to &String. And indeed that works.

Next I want to refactor the second part of that into a function count_trees_hit(landscape, right, down) so I can call it several times on the list of angles expressed as (right, down) pairs. I’ll start by omitting the down parameter and just making sure that the existing code works:

fn main() {
    // ...
    let trees_hit = count_trees_hit(&landscape, 3);
    println!("{}", trees_hit);
}

fn count_trees_hit(landscape: &Vec<String>, right: usize) -> usize {
    landscape
        .iter()
        .enumerate()
        .filter(|(row_index, row): &(usize, &String)| hits_tree(row_index, row, right))
        .count()
}

fn hits_tree(row_index: usize, row: &String, right: usize) -> bool {
    let col_index = row_index * right % row.len();
    row.as_bytes()[col_index] == b'#'
}

It looks like this almost works, but I get one error:

error[E0308]: mismatched types
  --> src/main.rs:27:65
   |
27 |         .filter(|(row_index, row): &(usize, &String)| hits_tree(row_index, row, right))
   |                                                                 ^^^^^^^^^
   |                                                                 |
   |                                                                 expected `usize`, found `&usize`
   |                                                                 help: consider dereferencing the borrow: `*row_index`

Since usize is an integer type I’m not sure why it has a reference, but I try changing the type of the row_index parameter to &usize and it works. It also works if I do what the compiler says and add *, but that’s an operator that I haven’t learned about (the page I read mentioned that it existed, but I don’t have a good idea of how it works.)

Next I want to add a down parameter. I think if we move multiple rows downwards for every column that we move to the right, then we can simply skip those rows. So it seems to me that I should be able to add another filter() step that skips the row if its index modulo down is not zero.

This new step doesn’t even need access to the row data so I wonder if I can simplify my code by ignoring the string parameter. I google “rust ignore parameter” and land on “Pattern Syntax” which I skim, and it looks like I should be able to use either .. or _ to ignore that parameter. I’ll try both and see what the compiler says. After a couple of tries, what works is: .filter(|(row_index, ..): &(usize, _)| *row_index % down == 0).

Now I have this code:

    let trees_hit = count_trees_hit(&landscape, 1, 2);
    println!("{}", trees_hit);
}

fn count_trees_hit(landscape: &Vec<String>, right: usize, down: usize) -> usize {
    landscape
        .iter()
        .enumerate()
        .filter(|(row_index, ..): &(usize, _)| *row_index % down == 0)
        .filter(|(row_index, row): &(usize, &String)| hits_tree(*row_index, row, right))
        .count()
}

fn hits_tree(row_index: usize, row: &String, right: usize) -> bool {
    let col_index = row_index * right % row.len();
    println!("{}, {}", col_index, row_index);
    row.as_bytes()[col_index] == b'#'
}

I am a bit suspicious that I might be getting the wrong row_index in the second filter() step, because I am filtering out the already-enumerated rows. So for testing, I try it with right 1 and down 2, and add the println!() statement in hits_tree() to print out the row index and column index.

It turns out my suspicion was correct. The indices that are printed out, are 0, 0, 2, 2, 4, 4, 6, 6 etc., while they should be 0, 0, 1, 2, 2, 4, 3, 6. I think what I need to do to fix this, is un-enumerate the items after the first filter() step and then re-enumerate them. I could write the un-enumerate step with map, but I have a feeling that there might be a built-in iterator method to take only the second element of a tuple, so I look at the API documentation for iterators again. I don’t see anything likely there. I look at the API documentation for Itertools as well, but don’t see anything there either. I try googling a few things (such as “rust iterator drop tuple element”) but that doesn’t give me any likely-looking results, so I decide to just write it myself. I insert .map(unenumerate).enumerate() into the iterator pipeline, after the first filter(), and define my unenumerate() function as follows:

fn unenumerate((.., row): &(_, &String)) -> &String {
    row
}

I get two errors that I haven’t seen before:

error[E0106]: missing lifetime specifier
  --> src/main.rs:34:45
   |
34 | fn unenumerate((.., row): &(_, &String)) -> &String {
   |                           -------------     ^ expected named lifetime parameter
   |
   = help: this function's return type contains a borrowed value, but the signature does not say which one of argument 1's 2 lifetimes it is borrowed from
help: consider introducing a named lifetime parameter
   |
34 | fn unenumerate<'a>((.., row): &'a (_, &String)) -> &'a String {
   |               ^^^^            ^^^^^^^^^^^^^^^^     ^^^

error[E0121]: the type placeholder `_` is not allowed within types on item signatures
  --> src/main.rs:34:29
   |
34 | fn unenumerate((.., row): &(_, &String)) -> &String {
   |                             ^ not allowed in type signatures
   |
help: use type parameters instead
   |
34 | fn unenumerate<T>((.., row): &(T, &String)) -> &String {
   |               ^^^              ^

From what I can understand from these errors, first it’s asking me to add a lifetime parameter, and second it seems like the .. trick is not allowed in named functions, only in inline functions?

The suggestion to use type parameters makes me think of how this might work in C++, so I try the following instead:

fn unenumerate<First, Second>((.., second): &(First, Second)) -> Second {
    second
}

Here, confusingly, the compiler does not want the & on the tuple type, so after a few tries of adding and removing & operators I do get this to compile and produce the debug output that I was expecting.

A bit too late, I realize that I could have done this much quicker with only one filter() step, skipping the rows by returning false in hits_tree(). Although what I have already works, this seems like it’s potentially a big enough improvement that I should try it:

fn count_trees_hit(landscape: &Vec<String>, right: usize, down: usize) -> usize {
    landscape
        .iter()
        .enumerate()
        .filter(|(row_index, row): &(usize, &String)| hits_tree(*row_index, row, right, down))
        .count()
}

fn hits_tree(row_index: usize, row: &String, right: usize, down: usize) -> bool {
    if row_index % down != 0 {
        return false;
    }
    let col_index = row_index / down * right % row.len();
    println!("{}, {}", col_index, row_index);
    row.as_bytes()[col_index] == b'#'
}

Apart from forgetting the braces on the if statement (apparently, you cannot omit them in Rust for a single-statement block as you can in C-like languages) I get the same result as my previous code that used unenumerate(), so I feel good about this.

It’s time to remove the debug println!() and actually write the Part 2 code, that tries several different angles and multiplies the answers together:

if part2 {
    let total = count_trees_hit(&landscape, 1, 1)
        * count_trees_hit(&landscape, 3, 1)
        * count_trees_hit(&landscape, 5, 1)
        * count_trees_hit(&landscape, 7, 1)
        * count_trees_hit(&landscape, 1, 2);
    println!("{}", total);
} else {
    let trees_hit = count_trees_hit(&landscape, 3, 1);
    println!("{}", trees_hit);
}

With this, cargo run 2 gives me an answer, which I put into the Advent of Code website, and it’s correct. And as a nice note to end on, this last change marks the first time in this series that I actually write some Rust code that compiles right away!

The full code, also pushed to GitHub:

use std::env;
use std::fs;
use std::io::{self, BufRead};
use std::path;

fn main() {
    let args: Vec<String> = env::args().collect();
    let mut part2 = false;
    let default = String::from("1");
    let arg = args.get(1).unwrap_or(&default);
    if arg == "2" {
        part2 = true;
    }
    let landscape: Vec<String> = read_lines("input")
        .expect("Bad file")
        .map(|s| s.expect("Bad line in file"))
        .collect();

    if part2 {
        let total = count_trees_hit(&landscape, 1, 1)
            * count_trees_hit(&landscape, 3, 1)
            * count_trees_hit(&landscape, 5, 1)
            * count_trees_hit(&landscape, 7, 1)
            * count_trees_hit(&landscape, 1, 2);
        println!("{}", total);
    } else {
        let trees_hit = count_trees_hit(&landscape, 3, 1);
        println!("{}", trees_hit);
    }
}

fn count_trees_hit(landscape: &Vec<String>, right: usize, down: usize) -> usize {
    landscape
        .iter()
        .enumerate()
        .filter(|(row_index, row): &(usize, &String)| hits_tree(*row_index, row, right, down))
        .count()
}

fn hits_tree(row_index: usize, row: &String, right: usize, down: usize) -> bool {
    if row_index % down != 0 {
        return false;
    }
    let col_index = row_index / down * right % row.len();
    row.as_bytes()[col_index] == b'#'
}

fn read_lines<P>(filename: P) -> io::Result<io::Lines<io::BufReader<fs::File>>>
where
    P: AsRef<path::Path>,
{
    let file = fs::File::open(filename)?;
    Ok(io::BufReader::new(file).lines())
}

Afterword

I can tell that I’m starting to get more comfortable in Rust, which feels good. But I’m a bit disappointed that even though I did some extra studying about ownership and the & operator, I was still confused, still couldn’t understand some errors, and basically had to either do exactly what the compiler said without understanding why, or else add or delete & operators arbitrarily until the code compiled.

Maybe what I should do next is read the page in the Rust book on lifetimes, and read about the * operator. Even though the page on ownership said those were advanced topics, both of those came up today in error messages that I didn’t understand.


[1] It occurs to me that — at least for this series — I’m glad I haven’t set up my editor to show Rust compiler errors inline, because otherwise I wouldn’t consciously think about these things