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.¹ 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:²

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

Advertisement