About Philip Chimento

Expect less than the unexpected.

Advent of Rust 25: Baby Steps

It’s the final post in the series chronicling my attempt to teach myself the Rust programming language by solving programming puzzles from Advent of Code 2020.

Day 25, Part 1

Today’s puzzle is about cracking an encryption key, in order to get at a piece of secret information (called loop size in the puzzle) by taking a piece of known public information (public key) and reversing the algorithm used to generate it. Of course, the algorithm (called transform subject number) is not easy to reverse, and that’s what the puzzle is about.

The puzzle description suggests guessing the loop size by trial and error which I am skeptical about, but this is the code that would do that by brute force:

fn transform_subject_number(subject_number: u64, loop_size: usize) -> u64 {
    let mut value = 1;
    for _ in 0..loop_size {
        value *= subject_number;
        value %= 20201227;
    }
    value
}

fn guess_loop_size(public_key: u64) -> usize {
    for loop_size in 1.. {
        if transform_subject_number(7, loop_size) == public_key {
            return loop_size;
        }
    }
    panic!("Not reachable");
}

#[derive(Debug)]
struct Party {
    loop_size: usize,
}

impl Party {
    fn public_key(&self) -> u64 {
        transform_subject_number(7, self.loop_size)
    }

    fn encryption_key(&self, other_public_key: u64) -> u64 {
        transform_subject_number(other_public_key, self.loop_size)
    }
}

fn main() {
    let card_public_key = 2084668;
    let door_public_key = 3704642;
    let card = Party {
        loop_size: guess_loop_size(card_public_key),
    };
    let door = Party {
        loop_size: guess_loop_size(door_public_key),
    };
    println!("{}", card.encryption_key(door.public_key()));
}

This is taking a long time. I’m guessing that this is not the way to do it.

I notice that, were it not for integer overflow, we’d be able to write the transform subject number result as SL (mod 20201227) (where S is the subject number and L is the loop size.) So, the total of what we know is this:

  • Pc ≡ 7Lc (mod 20201227)
  • Pd ≡ 7Ld (mod 20201227)
  • PcLdPdLc (mod 20201227)

where P is the public key, and the subscript c or d indicates card or door. The symbol “≡” means “congruent with” although I had to look it up on Wikipedia. Since I’m not even using all of this information in the trial and error implementation, I’m not surprised that it isn’t working.

I’m sure this is a solved problem, just like the hexagons yesterday, so I start searching (although I’m not sure what to search for, I try things like “modulo inverse”) and eventually land on the Wikipedia article for Modular exponentiation, which explains “the task of finding the exponent […] when given [the base, modular exponentiation, and modulus] is believed to be difficult.” Thanks, I guess…

These pages contain a little too much math all at once for my holiday-addled brain, especially because they confusingly use the notation a−1 to mean… something that’s not 1/a… so I decide to read a bit more on the topic hoping that something will sink in.

Eventually I read the “Modular arithmetic” section on the Wikipedia article for Discrete logarithm and a light begins to dawn. They give an example of how to calculate the possible solutions using Fermat’s Little Theorem.1 However, this approach turns out not to be useful for me because it already requires knowing one possible solution, and that’s exactly what I don’t have.

I do some more searching and find the Baby-step giant-step algorithm. I would probably have skipped over this if I had just stumbled upon the Wikipedia article without any context (because I don’t know what a finite abelian group is) but I reached it via another site with a bit more explanation of the missing link connecting the problem at hand to the Wikipedia article.2

The problem is of the form akb (mod n), where we have to find k. For the example in the puzzle description, we can fill in: a = 7, b = 17807724, n = 20201227.

The first thing I do is replace transform_subject_number() with a more general pow_m() function using the algorithm that I already have, called the “memory-efficient algorithm” in the Wikipedia article, and check that the tests still pass:

fn pow_m(base: u64, exponent: usize, modulus: u64) -> u64 {
    if modulus == 1 {
        return 0;
    }
    let mut value = 1;
    for _ in 0..exponent {
        value *= base;
        value %= modulus;
    }
    value
}

fn transform_subject_number(subject_number: u64, loop_size: usize) -> u64 {
    pow_m(subject_number, loop_size, 20201227)
}

Then I rewrite pow_m() to use the faster “right-to-left binary” algorithm from the Wikipedia article, and again check that the tests still pass:

fn pow_m(base: u64, exponent: usize, modulus: u64) -> u64 {
    if modulus == 1 {
        return 0;
    }
    let mut value = 1;
    let mut mod_base = base % modulus;
    let mut mod_exponent = exponent;
    while mod_exponent > 0 {
        if mod_exponent % 2 == 1 {
            value *= mod_base;
            value %= modulus;
        }
        mod_exponent >>= 1;
        mod_base *= mod_base;
        mod_base %= modulus;
    }
    value
}

Next I rewrite guess_loop_size() to use the baby-steps giant-steps algorithm, as described by Wikipedia:

fn bsgs(base: u64, modulus: u64, result: u64) -> Option<usize> {
    let m = (modulus as f64).sqrt().ceil() as u64;
    let mut table = HashMap::new();
    let mut e = 1;
    for j in 0..m {
        table.insert(e, j);
        e *= base;
        e %= modulus;
    }
    let factor = pow_m(base, (modulus - m - 1) as usize, modulus);
    let mut gamma = result;
    for i in 0..m {
        if let Some(j) = table.get(&gamma) {
            return Some((i * m + j) as usize);
        }
        gamma *= factor;
        gamma %= modulus;
    }
    None
}

fn guess_loop_size(public_key: u64) -> usize {
    bsgs(7, 20201227, public_key).unwrap()
}

The tests still pass, so that means it correctly handles the example code. I run this, it finishes almost immediately, and I get the right answer.

Day 25, Part 2

I’m not going to spoil the very last puzzle! I solve it without writing any code though.

Afterword

I found this puzzle one of the most difficult ones, as I’m not really into cryptography, and it required quickly getting acquainted with an area of mathematics that I had never encountered before. I don’t even think it would have been possible for me to do it, if I hadn’t had enough experience in other areas of mathematics that I at least knew some search terms that brought me in the right direction.

It was difficult in a different way than the image-assembly puzzle on Day 20, though; that one was more like, you could easily see what needed to be done, but it was so tedious to get right. The hard part today was to find out what needed to be done, and once I had landed on the right Wikipedia page with an explanation of the algorithm, it was simple enough to implement. In a way it was similar to yesterday’s hexagons, but the topic of modular discrete logarithms was so much more difficult to absorb quickly than the topic of hexagons was.

Reflections on the Whole Thing

How do I feel about doing 50 puzzles in the past 28 days?
First of all, if I do this again, I’m not going to keep up this pace and I’m not going to blog about it. It was fun while it lasted, but it’s really quite time-consuming, and it’s not even over yet — Rust is open source, so I have practically obligated myself in January to do the right thing and follow through with submitting all the suggestions for improvement of the Rust tools that I can glean from the earlier posts in the series.

I enjoyed the VM-like puzzles the most, after that the parser ones,3 and after that the ones that could be solved with interesting uses of iterators and Itertools. The cryptography puzzles like today’s, I didn’t enjoy that much. I appreciated that there were so many Game of Life variations as an homage to Conway who passed away this year, but as puzzles they were not so interesting; after I wrote the code to solve one, I basically just copied it for the subsequent puzzles. Conway’s Game of Life is so mesmerizing when you can watch it evolving, but since it wasn’t necessary for solving the puzzle I didn’t really feel like spending time building visualizations.

I didn’t find the Reddit board very helpful unless I was actively looking for a hint from the hint threads, or looking for other people’s visualizations of the Game of Life puzzles. Reading all the posts from people who knew exactly the right algorithm to use, or solved the puzzle in mere minutes, or made fantastic visualizations, made me feel inadequate. Even though there were a few of these puzzles that I thought I did very well at, there were always people on the Reddit board who did better.4

Can I program in Rust now?
I’m not sure. Probably not. I know just enough that I should now go and read the Rust book, and I will get much more out of it than I would have if I had started out by reading the book.

Would I recommend learning Rust?
Certainly I found it very rewarding. It’s refreshing to see how they designed it to avoid or mitigate common classes of mistakes. Its tools and its standard library were a pleasure to use. That said, I would mainly recommend learning it if you are already experienced in another programming language. Put another way, I found learning Rust while knowing C++ as a reference point to be comparable to (what I imagine is the experience of) learning C++ while knowing JavaScript as a reference point. The things that you already know from the other language do serve you well, and give you a better footing in the new language, but there are also many new concepts that have no equivalent in the other language and you just don’t think about them explicitly. For C++, an example would be pointers, and for Rust an example would be borrows. Speaking for myself at least, I wouldn’t want to be learning borrowing at the same time as I was learning for-loops. Not to mention I’ve finished this whole series while still only having a vague idea of what a lifetime is!

Is the hype justified?
Although based on limited experience, at this point I believe the advice of using Rust for new projects where you would otherwise be using C or C++ is sound! I’m excited to use Rust for a project in the future. On the other hand, I don’t think Rust quite lives up to the hype of being absolutely safe because I was able to easily write code in almost all of these puzzles that would abort when given any sort of unexpected input, but it is at least true that those cases might instead be buffer overflows in C.

Would I recommend learning programming by doing these puzzles?
I’ve seen people recommend this while reading about Advent of Code this month, but honestly? I wouldn’t. If you are learning programming, start with something that’s straightforward and not tricky at all. Programming is tricky enough already by itself.

To conclude this series, I will leave you with a fast-loading version of the Rust error types diagram that Federico sent me after reading my early posts, rendered from DOT and accessible without Google Drive. This diagram was really helpful for me along the way, big thanks to whoever first made it, so I’m glad I can re-share it in a hopefully improved format.

Happy New Year, let’s hope for some better times in 2021!


[1] Yes, that really is the name; is there also Fermat’s Big Theorem?

[2] I hesitate to link there because they have big banners saying “Get FAANG Ready With [our site]” which promotes a software engineering industry culture that I don’t support

[3] Hopefully that means I’m in the right job

[4] Or claimed to, in order to make others feel inadequate5

[5] No, I don’t have a very high opinion of the quality of discourse on Reddit, why do you ask?

Advent of Rust 24: A Hexagonal Tribute to Conway

Today in the penultimate post from the chronicle of teaching myself the Rust programming language by doing programming puzzles from Advent of Code 2020: a hexagonal grid, and another homage to Conway, this time unexpected.

But before that, I will finally solve that sea monster puzzle from Day 20.

Day 20, Part 2 (Yet Again)

First, as promised in the previous post, I will show the refactored code that assembles the full image.

struct Solver {
    tiles: Vec<Tile>,
    connections: MultiMap<u64, u64>,
    corners: [u64; 4],
    used_tile_ids: HashSet<u64>,
}

impl Solver {
    fn new(tiles: &[Tile]) -> Self {
        let mut connections = MultiMap::new();
        for (tile1, tile2) in tiles.iter().tuple_combinations() {
            if tile1.connection_side(tile2).is_some() {
                connections.insert(tile1.id, tile2.id);
                connections.insert(tile2.id, tile1.id);
            }
        }
        let corners: Vec<_> = tiles
            .iter()
            .map(|tile| tile.id)
            .filter(|id| match connections.get_vec(id).unwrap().len() {
                2 => true,
                3 | 4 => false,
                _ => panic!("Impossible"),
            })
            .collect();
        Self {
            tiles: tiles.to_vec(),
            connections,
            corners: corners.try_into().unwrap(),
            used_tile_ids: HashSet::new(),
        }
    }

    fn find_and_orient_tile(&mut self, tile: &Tile, direction: Direction) -> Option<Tile> {
        let tile_connections = self.connections.get_vec(&tile.id).unwrap();
        let maybe_next_tile = self
            .tiles
            .iter()
            .filter(|t| tile_connections.contains(&t.id) && !self.used_tile_ids.contains(&t.id))
            .find_map(|candidate| tile.match_other(candidate, direction));
        if let Some(t) = &maybe_next_tile {
            self.used_tile_ids.insert(t.id);
        }
        maybe_next_tile
    }

    fn arrange(&mut self) -> Array2<u8> {
        // Find top left corner - pick an arbitrary corner tile and rotate it until
        // it has connections on the right and bottom
        let mut tl_corner = self
            .tiles
            .iter()
            .find(|tile| self.corners.contains(&tile.id))
            .unwrap()
            .clone();
        self.used_tile_ids.insert(tl_corner.id);
        let mut tl_corner_connections = vec![];
        for possible_edge in &self.tiles {
            match tl_corner.connection_side(&possible_edge) {
                None => continue,
                Some(dir) => tl_corner_connections.push(dir),
            }
        }
        tl_corner = tl_corner.rot90(match (tl_corner_connections[0], tl_corner_connections[1]) {
            (Direction::RIGHT, Direction::BOTTOM) | (Direction::BOTTOM, Direction::RIGHT) => 0,
            (Direction::LEFT, Direction::BOTTOM) | (Direction::BOTTOM, Direction::LEFT) => 1,
            (Direction::LEFT, Direction::TOP) | (Direction::TOP, Direction::LEFT) => 2,
            (Direction::RIGHT, Direction::TOP) | (Direction::TOP, Direction::RIGHT) => 3,
            _ => panic!("Impossible"),
        });

        // Build the top edge
        let mut t_row = vec![tl_corner];
        loop {
            match self.find_and_orient_tile(&&t_row[t_row.len() - 1], Direction::RIGHT) {
                None => break,
                Some(tile) => {
                    t_row.push(tile);
                }
            }
        }

        let ncols = t_row.len();
        let nrows = self.tiles.len() / ncols;

        println!("whole image is {}×{}", ncols, nrows);

        // For each subsequent row...
        let mut rows = vec![t_row];
        for row in 1..nrows {
            // Arrange the tiles that connect to the ones in the row above
            rows.push(
                (0..ncols)
                    .map(|col| {
                        self.find_and_orient_tile(&rows[row - 1][col], Direction::BOTTOM)
                            .unwrap()
                    })
                    .collect(),
            );
        }

        // Concatenate all the image data together
        let all_rows: Vec<_> = rows
            .iter()
            .map(|row| {
                let row_images: Vec<_> = row.iter().map(|t| t.image.view()).collect();
                concatenate(Axis(1), &row_images).unwrap()
            })
            .collect();
        concatenate(
            Axis(0),
            &all_rows.iter().map(|row| row.view()).collect::<Vec<_>>(),
        )
        .unwrap()
    }
}

There are two main things that I changed here. First is that I noticed I was passing a lot of the same arguments (corners, edges, connections) to the methods that I had, so that was a code smell that indicated that these should be gathered together into a class, which I’ve called Solver.

The second insight was that I don’t actually need to keep track of which tiles are corners, edges, and middles; each tile can only connect in one way, so I only need to find the corners (both for the answer of Part 1, and to pick the top left corner to start assembling the image from.)

Now that I have the full image, I have to actually solve the Part 2 puzzle: cross-correlate the image with the sea monster matrix.

Unlike NumPy, Rust’s ndarray does not have any built-in facilities for cross-correlation, nor is it provided by any packages that I can find. So I will have to write code to do this, but because what I need is actually a very simple form of cross-correlation, I don’t think it will be so hard.

What I need to do is take a slice of the image at every position, of the size of the sea monster, except where the sea monster would extend outside the boundaries of the image. Then I multiply the slice by the sea monster, and sum all the elements in it, and if that sum is equal to the sum of the elements in the sea monster, then there is a sea monster located there.

I will need to do this operation on each of the eight orientations of the image (rotated four ways, and flipped) until I find one where sea monsters are present. Then to get the answer to the puzzle, I’ll have to subtract the number of sea monsters times the number of pixels in a sea monster, from the sum of the pixels in the image.

I write this code:

fn all_orientations(image: &Array2<u8>) -> [ArrayView2<u8>; 8] {
    [
        image.view(),
        image.view().reversed_axes(),
        image.slice(s![.., ..;-1]),
        image.slice(s![.., ..;-1]).reversed_axes(),
        image.slice(s![..;-1, ..]),
        image.slice(s![..;-1, ..]).reversed_axes(),
        image.slice(s![..;-1, ..;-1]),
        image.slice(s![..;-1, ..;-1]).reversed_axes(),
    ]
}

static SEA_MONSTER: [&str; 3] = [
    "                  # ",
    "#    ##    ##    ###",
    " #  #  #  #  #  #   ",
];

fn count_sea_monsters(image: &ArrayView2<u8>) -> (usize, usize) {
    let mon_rows = SEA_MONSTER.len();
    let mon_cols = SEA_MONSTER[0].len();
    let mut sea_monster = Array2::zeros((mon_rows, mon_cols));
    for (y, line) in SEA_MONSTER.iter().enumerate() {
        for (x, cell) in line.bytes().enumerate() {
            sea_monster[[y, x]] = (cell != b' ') as u8;
        }
    }
    let mon_pixels: u8 = sea_monster.iter().sum();

    let mut monsters = 0;
    let rows = image.nrows();
    let cols = image.ncols();
    for y in 0..(rows - mon_rows) {
        for x in 0..(cols - mon_cols) {
            let slice = image.slice(s![y..(y + mon_rows), x..(x + mon_cols)]);
            let correlation = &slice * &sea_monster.view();
            if correlation.iter().sum::<u8>() == mon_pixels {
                monsters += 1;
            }
        }
    }
    (monsters, monsters * mon_pixels as usize)
}

First I make sure it produces the right answer for the example data, then I add this to main():

let full_image = solver.arrange();
let (_, pixels) = all_orientations(&full_image)
    .iter()
    .find_map(|image| {
        let (count, pixels) = count_sea_monsters(image);
        if count != 0 { Some((count, pixels)) } else { None }
    })
    .unwrap();
println!("{}", full_image.iter().filter(|&&c| c > 0).count() - pixels);

Sadly, it doesn’t work. When trying to connect up the top left corner I get a panic because it is possible to connect it on three sides, not two! This is obviously a bug in my program (the tile wouldn’t have been in the list of corners if it had been able to connect on three sides!) I should investigate and fix this bug, but I am so done with this puzzle. In one last burst, I decide to paper over the bug by only trying the tiles that I already know should connect, replacing the tl_corner_connections code with the following:

let tl_corner_connections: Vec<_> = self
    .tiles
    .iter()
    .filter(|t| {
        self.connections.get_vec(&tl_corner.id).unwrap().contains(&t.id)
    })
    .map(|candidate| tl_corner.connection_side(&candidate))
    .filter(Option::is_some)
    .map(Option::unwrap)
    .collect();

Finally, finally, this gives me the correct answer, and I see the sea monster light up on the Advent of Code map. There is still a bug, but let us close this book and never speak of this code again.

Day 24, Part 1

Without that sea monster puzzle weighing on me, I’m happy to start the second-to-last puzzle. It involves a floor tiled with hexagonal tiles. The tiles have a white side and a black side, and can flip from one to the other. The puzzle involves starting from a center tile, and following directions (east, northeast, west, etc.) to get to another tile, which must be flipped. The answer to the puzzle is how many tiles are flipped after following all the directions.

So! I’ve never had to work with a hexagonal grid before, but so many games have one, it must be a solved problem. I google “represent hex grid in array” and land on a Stack Overflow question, which leads me to this brilliant page, “Hexagonal Grids” by Amit Patel. This is nothing short of a miracle, telling me everything I need to know in order to do things with hexagonal grids.

After reading that page and thinking about it for a while, I decide that I will use cube coordinates (x, y, z) and that I don’t even need to store a grid. I just need to store the destination coordinates that each instruction from the input takes me to. A tile is white at the end, if its coordinates are reached an even number of times (including 0), and a tile is black if its coordinates are reached an odd number of times.

I could store the destination coordinates in a hashmap from coordinate to count, but I wonder if there is a multiset similar to the multimap I used a few days ago. There is. With that, I can write the code for Part 1:

use multiset::HashMultiSet;

type Hex = (i32, i32, i32);

#[derive(Debug, PartialEq)]
enum Direction {
    EAST,
    SOUTHEAST,
    SOUTHWEST,
    WEST,
    NORTHWEST,
    NORTHEAST,
}

impl Direction {
    fn move_rel(&self, (x, y, z): Hex) -> Hex {
        use Direction::*;
        match self {
            EAST => (x + 1, y - 1, z),
            SOUTHEAST => (x, y - 1, z + 1),
            SOUTHWEST => (x - 1, y, z + 1),
            WEST => (x - 1, y + 1, z),
            NORTHWEST => (x, y + 1, z - 1),
            NORTHEAST => (x + 1, y, z - 1),
        }
    }
}

fn parse_line(text: &str) -> Vec<Direction> {
    use Direction::*;
    let mut iter = text.bytes();
    let mut retval = Vec::with_capacity(text.len() / 2);
    while let Some(b) = iter.next() {
        retval.push(match b {
            b'e' => EAST,
            b's' => match iter.next() {
                Some(b2) if b2 == b'e' => SOUTHEAST,
                Some(b2) if b2 == b'w' => SOUTHWEST,
                Some(b2) => panic!("bad direction s{}", b2),
                None => panic!("bad direction s"),
            },
            b'w' => WEST,
            b'n' => match iter.next() {
                Some(b2) if b2 == b'w' => NORTHWEST,
                Some(b2) if b2 == b'e' => NORTHEAST,
                Some(b2) => panic!("bad direction n{}", b2),
                None => panic!("bad direction n"),
            },
            _ => panic!("bad direction {}", b),
        });
    }
    retval
}

fn main() {
    let input = include_str!("input");
    let destination_counts: HashMultiSet<_> = input
        .lines()
        .map(|line| {
            parse_line(line)
                .iter()
                .fold((0, 0, 0), |hex, dir| dir.move_rel(hex))
        })
        .collect();
    let count = destination_counts
        .distinct_elements()
        .filter(|destination| destination_counts.count_of(destination) % 2 == 1)
        .count();
    println!("{}", count);
}

Day 24, Part 2

In a surprise twist, the second part of the puzzle is yet another Conway’s Game of Life, this time on the hex grid! So no more storing the coordinates of the flipped tiles in a multiset. I will need to have some sort of array to store the grid, and calculate the number of occupied neighbour cells, as we have done on several previous puzzles.

The Hexagonal Grids page comes through once again. Isn’t this great, that I knew nothing about hexagonal grids before encountering this puzzle, and there’s just a page on the internet that explains all of it well enough that I can use it to solve this puzzle! I will use axial coordinates (meaning, just discard one of the cube coordinates) and store the grid in a rectangular ndarray. The only question is how big the array has to be.

I decide, as in Day 17, that a good upper bound is probably the size of the starting pattern, plus the number of iterations of the game, extended in each direction. So, for the example pattern in the puzzle description, the highest number in any of the three coordinates is 3 (and −3), and the number of iterations is 100, so we’d want a grid of 103×103.

The hex page recommends encapsulating access to the hex grid in a class, so that’s exactly what I do:

struct Map {
    map: Array2<i8>,
    ref_q: i32,
    ref_r: i32,
}

impl Map {
    fn from_counts(counts: &HashMultiSet<Hex>) -> Self {
        let initial_extent = counts.distinct_elements().fold(0, |acc, (x, y, z)| {
            acc.max(x.abs()).max(y.abs()).max(z.abs())
        });
        let extent = initial_extent + 100; // n_iterations = 100
        let size = extent as usize;
        let map = Array2::zeros((2 * size + 1, 2 * size + 1));
        let mut this = Self {
            map,
            ref_q: extent,
            ref_r: extent,
        };
        for &(x, y, _) in counts
            .distinct_elements()
            .filter(|dest| counts.count_of(dest) % 2 == 1)
        {
            this.set(x, y);
        }
        this
    }

    fn set(&mut self, x: i32, y: i32) {
        let q = (x + self.ref_q) as usize;
        let r = (y + self.ref_r) as usize;
        self.map[[q, r]] = 1;
    }

    fn calc_neighbours(map: &Array2<i8>) -> Array2<i8> {
        let shape = map.shape();
        let width = shape[0] as isize;
        let height = shape[1] as isize;
        let mut neighbours = Array2::zeros(map.raw_dim());
        // Add slices of the occupied cells shifted one space in each hex
        // direction
        for &(xstart, ystart) in &[(1, 0), (0, 1), (-1, 1), (-1, 0), (0, -1), (1, -1)] {
            let xdest = xstart.max(0)..(width + xstart).min(width);
            let ydest = ystart.max(0)..(height + ystart).min(height);
            let xsource = (-xstart).max(0)..(width - xstart).min(width);
            let ysource = (-ystart).max(0)..(height - ystart).min(height);
            let mut slice = neighbours.slice_mut(s![xdest, ydest]);
            slice += &map.slice(s![xsource, ysource]);
        }
        neighbours
    }

    fn iterate(&mut self) {
        let neighbours = Map::calc_neighbours(&self.map);
        let removals = &neighbours.mapv(|count| (count == 0 || count > 2) as i8) * &self.map;
        let additions =
            &neighbours.mapv(|count| (count == 2) as i8) * &self.map.mapv(|cell| (cell == 0) as i8);
        self.map = &self.map + &additions - &removals;
    }

    fn count(&self) -> usize {
        self.map
            .fold(0, |acc, &cell| if cell > 0 { acc + 1 } else { acc })
    }
}

I store the map as a 2-dimensional ndarray, with coordinates (q, r) equal to (x, y) in the cube coordinate scheme (I just drop the z coordinate.) I store the offset of the center tile in (qref, rref).

I make a constructor that takes the multiset from Part 1 as input, and an iterate() method that calculates one iteration of the map and updates the class. The calc_neighbours() and iterate() code is practically copied from Day 11 except that we only shift the map in six directions instead of eight. (Which six directions those are, I get from the hex grids page.)

I’m not a big fan of acc.max(x.abs()).max(y.abs()).max(z.abs()) and wish I knew of a better way to do that.

I can then write the following code in main() which gives me the answer:

let mut map = Map::from_counts(&destination_counts);
for _ in 0..100 {
    map.iterate();
}
println!("{}", map.count());

Afterword

The Day 20 puzzle was a bit disappointing, since I spent so much more time on it than any of the other puzzles, and the solution wasn’t even particularly good. I’m not sure what made it so much more difficult, but I suspect that I just didn’t find the right data structure to read the data into.

Day 24, on the other hand, I completed easily with the help of a very informative web site. I suppose this puzzle was a bit of a gimmick, though; if you know how to deal with hexagonal grids then it’s very quick, and if you don’t, then it’s much more difficult. In my case, doing a search for the right thing made all the difference. If I had started out writing code without the knowledge that I had learned, I probably would have used offset coordinates, and, as you can read on the Hexagonal Grids page, that would mean that the directions are different depending on whether you’re in an odd or even-numbered column. The code would have been much more complicated!

This series will return for one final installment within the next few days.

Advent of Rust, Day 22 and 23: Profiling, Algorithms, and Data Structures

It’s that time again, time for a new post in the chronicle of me teaching myself the Rust programming language by solving programming puzzles from Advent of Code 2020.

Day 22, Part 1

Today’s puzzle is about the card game of Combat1, a two-player game with a numbered deck of cards. Each player takes a card off the top of the deck, and whoever has the highest card takes both. When one player has no cards left, the other player wins. The input to the puzzle is the cards in each deck, and the answer is the winning player’s score: the bottom card of their deck times 1, plus the next bottom-most card times 2, plus the next bottom-most card times 3, etc.

I read about VecDeque at the same time I read about Vec, on the very first day I started learning Rust with these puzzles, but I haven’t had an opportunity to use it yet. However, this seems like one. The program is quite straightforward:

use std::collections::VecDeque;

fn main() {
    let input = include_str!("input");
    let mut deck_blocks = input.split("\n\n");
    let mut deck1 = read_deck(deck_blocks.next().unwrap());
    let mut deck2 = read_deck(deck_blocks.next().unwrap());
    play_combat(&mut deck1, &mut deck2);
    println!(
        "{}",
        score_deck(if deck1.is_empty() { &deck2 } else { &deck1 })
    );
}

fn read_deck(block: &str) -> VecDeque<u16> {
    block.lines().skip(1).map(|s| s.parse().unwrap()).collect()
}

fn play_combat(deck1: &mut VecDeque<u16>, deck2: &mut VecDeque<u16>) {
    while !deck1.is_empty() && !deck2.is_empty() {
        let card1 = deck1.pop_front().unwrap();
        let card2 = deck2.pop_front().unwrap();
        if card1 > card2 {
            deck1.push_back(card1);
            deck1.push_back(card2);
        } else {
            deck2.push_back(card2);
            deck2.push_back(card1);
        }
    }
}

fn score_deck(deck: &VecDeque<u16>) -> u16 {
    deck.iter()
        .rev()
        .enumerate()
        .map(|(ix, val)| ((ix + 1) as u16) * val)
        .sum()
}

I’m also happy that I get all the & operators right this time. Sure, it’s a small program, but the achievement feels good.

Day 22, Part 2

Part 2 is a bit more complicated: we have to play Recursive Combat. Each player draws a card. If both players have enough cards in their deck, then they start a new sub-game of Recursive Combat with the top cards in their deck, as many as the number on the card they drew, and the winner of the sub-game takes both cards. If either player doesn’t have enough cards, then whoever had the higher card takes both cards. In the case of an infinite loop, Player 1 wins outright. The scoring rules are the same.

I’m again able to write this fairly straightforwardly. What I write at first has a few bugs, but once again writing inline tests based on the examples in the puzzle description helped me debug them. Here’s the code:

fn play_recursive_combat(deck1: &mut Deck, deck2: &mut Deck) -> bool {
    let mut played_rounds = HashSet::new();
    while !deck1.is_empty() && !deck2.is_empty() {
        let this_round = (deck1.clone(), deck2.clone());
        if played_rounds.contains(&this_round) {
            return true;
        }
        played_rounds.insert(this_round);
        let card1 = deck1.pop_front().unwrap();
        let card2 = deck2.pop_front().unwrap();
        let player1_wins = if deck1.len() >= card1 && deck2.len() >= card2 {
            let mut deck1_copy = deck1.clone();
            let mut deck2_copy = deck2.clone();
            deck1_copy.truncate(card1);
            deck2_copy.truncate(card2);
            play_recursive_combat(&mut deck1_copy, &mut deck2_copy)
        } else {
            card1 > card2
        };

        if player1_wins {
            deck1.push_back(card1);
            deck1.push_back(card2);
        } else {
            deck2.push_back(card2);
            deck2.push_back(card1);
        }
    }
    deck2.is_empty()
}

Day 23, Part 1

Today’s puzzle is simulating the outcome of yet another game. There are 10 cups, arranged in a circle, each labelled with a number, and one is the “current cup”. The three cups after the current cup are picked up, and inserted after the “destination cup”, which is the cup labelled with the current cup’s number minus 1. (If that cup is one of the ones picked up, then the destination cup is the current cup minus 2, and so on.) Then the current cup shifts to the next in the circle. The answer to the puzzle is the order of the cups after 100 of these moves, starting from the cup labelled 1.

I decide that since the cups are in a circle, the starting point doesn’t really matter, and I can make it so that the current cup is always the starting point. That way I don’t have to keep track of the index of the current cup, and I can use a VecDeque again to pop it off the front and push it onto the back, and the process of making a move becomes simpler.

The code that I write is fairly straightforward and goes without much incident:

use std::collections::VecDeque;

fn dec_nonnegative_mod(num: i8, n_cups: i8) -> i8 {
    (num + n_cups - 2) % n_cups + 1
}

fn do_move(cups: &mut VecDeque<i8>) {
    let n_cups = cups.len() as i8;
    let current_cup = cups.pop_front().unwrap();
    let mut move_cups: VecDeque<_> = (0..3).map(|_| cups.pop_front().unwrap()).collect();
    let mut destination_cup = dec_nonnegative_mod(current_cup, n_cups);
    while move_cups.contains(&destination_cup) {
        destination_cup = dec_nonnegative_mod(destination_cup, n_cups);
    }
    let insert_index = cups.iter().position(|&cup| cup == destination_cup).unwrap() + 1;
    (0..3).for_each(|n| cups.insert(insert_index + n, move_cups.pop_front().unwrap()));
    cups.push_back(current_cup);
}

fn main() {
    let input = "253149867";
    let mut cups: VecDeque<i8> = input
        .chars()
        .map(|c| c.to_digit(10).unwrap() as i8)
        .collect();
    let n_moves = 100;
    for _ in 0..n_moves {
        do_move(&mut cups);
    }
    while cups[0] != 1 {
        cups.rotate_left(1);
    }
    cups.pop_front();
    println!(
        "{}",
        cups.iter()
            .map(|n| n.to_string())
            .collect::<Vec<_>>()
            .join("")
    );
}

Day 23, Part 2

For part 2, we have 1 million cups (after the initial ordering, the rest is padded out with the numbers 10 through 999999 in order) and 10 million moves. The answer is the product of the two cups that end up after cup 1.

First I change the data type of the cups from i8 to i64. Then I make the changes in main() to reflect the updated rules of the game:

fn main() {
    let input = "253149867";
    let n_cups = if is_part2() { 1_000_000 } else { 9 };
    let mut cups: VecDeque<i64> = input
        .chars()
        .map(|c| c.to_digit(10).unwrap() as i64)
        .chain(10..(n_cups + 1))
        .collect();
    let n_moves = if is_part2() { 10_000_000 } else { 100 };
    for _ in 0..n_moves {
        do_move(&mut cups);
    }
    while cups[0] != 1 {
        cups.rotate_left(1);
    }
    cups.pop_front();
    if is_part2() {
        println!("{}", cups[0] * cups[1]);
    } else {
        println!(
            "{}",
            cups.iter()
                .map(|n| n.to_string())
                .collect::<Vec<_>>()
                .join("")
        );
    }
}

I run it and it seems to be taking a long time. Now I’d like to know just how long it will take so that I can decide whether it’s worth it to try to speed it up or just let it brute-force itself to the end. I add a progress bar with this cool library that I’ve heard about, and I’m pleased that it only takes a few lines:

let progress = indicatif::ProgressBar::new(n_moves);
progress.set_style(
    indicatif::ProgressStyle::default_bar().template("[{eta_precise}] {wide_bar} {pos}/{len}"),
);
// ...
for /* ... */ {
    // ...
    progress.inc(1);
}
// ...
progress.finish_and_clear();

By looking at the ETA, I suspect it will take well over 3 days to finish all 10 million moves!

My guess is that it’s taking so long because of inserting three elements into the vector, which has to make a copy of all the elements that come after the insertion. I am fairly bad at data structures, but I suspect that this might be one of the rare cases where it’s advantageous to use a linked list, since that has quick insertion in the middle. However, before I rewrite the whole thing I change the wasteful 3× insert, to split the vector at the insertion point, and append the three moved cups before sticking the second half of the vector back on:

let insert_index = cups.iter().position(|&cup| cup == destination_cup).unwrap() + 1;
let mut back = cups.split_off(insert_index);
cups.append(&mut move_cups);
cups.append(&mut back);
cups.push_back(current_cup);

This shaves five hours off the ETA, but it’s not enough.

I also move the determination of n_cups out of the loop, and instead provide it as a parameter of the do_move() function, but it doesn’t really affect the running time either.

Rust’s standard library does include a linked list, but it’s a doubly linked list and doesn’t have APIs for detaching and inserting whole ranges, as far as I can tell.

I wonder if, before resorting to rewriting the program with a different linked list data structure from a package, I should profile the existing program to find out what is taking so long. I suspect the insert, but it could be something else, like searching the vector for the destination cup.

I google “rust profiling tools” and land first on cargo-profiler. It looks really easy to install and use, but unfortunately it crashes if you have a digit in the path of your program:

$ cargo profiler callgrind -- 2

Compiling puzzle23 in debug mode...

Profiling puzzle23 with callgrind...
error: Regex error -- please file a bug. In bug report, please include the original output file from profiler, e.g. from valgrind --tool=cachegrind --cachegrind-out-file=cachegrind.txt

This bug is in a giant-ass regular expression that doesn’t give me a lot of confidence in the robustness this tool. On to the next one.

The cpuprofiler package has pretty decent getting-started documentation. It requires gperftools, so I first install my Linux distribution’s gperftools package, then add this preamble to my program:

extern crate cpuprofiler;
use cpuprofiler::PROFILER;

I then sandwich the main loop between the following two lines:

PROFILER.lock().unwrap().start("./23.profile").unwrap();
PROFILER.lock().unwrap().stop().unwrap();

I change the number of moves to 1000 and run the program. A 23.profile file appears in my project directory! According to the documentation, I can then use the pprof tool to check which lines in do_move() are hot (output slightly truncated):

$ pprof --list=do_move ./target/debug/puzzle23 23.profile
     0   3261 Total samples (flat / cumulative)
     .      .   12: fn do_move(cups: &mut VecDeque<i64>, n_cups: i64) {
     .      .   13:     let current_cup = cups.pop_front().unwrap();
     .      .   14:     let mut move_cups: VecDeque<_> = (0..3).map(|_| cups.pop_front().unwrap()).collect();
     .      .   15:     let mut destination_cup = dec_nonnegative_mod(current_cup, n_cups);
     .      1   16:     while move_cups.contains(&destination_cup) {
     .      .   17:         destination_cup = dec_nonnegative_mod(destination_cup, n_cups);
     .      .   18:     }
     .   3257   19:     let insert_index = cups.iter().position(|&cup| cup == destination_cup).unwrap() + 1;
     .      1   20:     let mut back = cups.split_off(insert_index);
     .      .   21:     cups.append(&mut move_cups);
     .      1   22:     cups.append(&mut back);
     .      .   23:     cups.push_back(current_cup);
     .      1   24: }

So I was wrong. It’s not the insert that is causing the problem at all, and I probably don’t need to use a linked list! The problem is searching the vector for the destination cup.

Interestingly, rewriting that loop not to use position(), cuts the expected running time almost in half, to a little over two days:

let mut ix = 0;
for &cup in cups.iter() {
    if cup == destination_cup {
        break;
    }
    ix += 1;
}
let insert_index = ix + 1;
let mut back = cups.split_off(insert_index);
cups.append(&mut move_cups);
cups.append(&mut back);
cups.push_back(current_cup);

However, either of (a) using enumerate() or (b) writing the loop without an iterator at all (for ix in 0.. and indexing cups[ix]) increases the expected running time back up to the same neighbourhood as using position(). I’m a bit surprised at that, but I file it away and move on.

Although I’m pleasantly surprised that profiling a program is so easy with Rust and Cargo, I’m starting to think that profiling and optimizing this code is a red herring, because if I keep this algorithm, then no matter what I’ll still have to search through the vector to find the destination cup, and I’m not sure it’s possible to do that any faster. I can see two possibilities from here: either there a different algorithm that will run faster; or there is a mathematical trick that can be used to figure out the answer in an easier way, like on Day 13.

I try changing the number of cups to 20 and the number of moves to 200, and printing out the order of cups every move, to see if I can see any patterns, but after staring at it for a while, I still don’t see anything.

I am getting a bit sick of this puzzle since it has taken a much larger chunk of my day than I actually wanted to spend on it, and I’m frustrated that I haven’t solved Day 20 yet. I decide to check the Reddit thread for this puzzle, where I hope to get a hint without spoiling myself entirely.

The first hint that I find is to use an array where the value at a given index is the next cup after the cup labelled with that index. This is actually so helpful that in the end I think I may have spoiled myself more than I wanted to. When I write the code, I realize two things:

  • This is actually a sort of linked list in disguise, so actually my idea earlier was on the right track.
  • By storing the linked list elements contiguously in an array, you can eliminate the search for the destination cup altogether.

Since with this scheme, we do need to store the current cup as part of the state, I decide to make a struct. I also change the data type of the cups once more, to usize, since the cup numbers are going to be used as array indices.

I run the program and this time the progress bar suggests it will be done in 21 minutes. That’s still a long time, but I decide I will just wait. If I get the wrong answer at the end, then I’ll spend time to profile it and make it faster. But when it finishes, the website tells me the answer is correct, so I move on.

Here’s the code, with the rewritten main() function for both of Parts 1 and 2:

fn dec_nonnegative_mod(num: usize, n_cups: usize) -> usize {
    (num + n_cups - 2) % n_cups + 1
}

struct Links {
    n_cups: usize,
    current_cup: usize,
    links: Vec<usize>,
}

impl Links {
    fn from_list(cups: &[usize]) -> Self {
        let n_cups = cups.len();
        let mut links = vec![0; n_cups + 1];
        for (&this, &next) in cups.iter().tuple_windows() {
            links[this] = next;
        }
        links[cups[n_cups - 1]] = cups[0];
        Self {
            n_cups,
            current_cup: cups[0],
            links,
        }
    }

    fn next(&self, cup: usize) -> usize {
        self.links[cup]
    }

    fn do_move(&mut self) {
        let move1 = self.links[self.current_cup];
        let move2 = self.links[move1];
        let move3 = self.links[move2];
        let mut insert_after = dec_nonnegative_mod(self.current_cup, self.n_cups);
        while insert_after == move1 || insert_after == move2 || insert_after == move3 {
            insert_after = dec_nonnegative_mod(insert_after, self.n_cups);
        }
        let next_current_cup = self.links[move3];
        self.links[self.current_cup] = next_current_cup;
        let insert_before = self.links[insert_after];
        self.links[insert_after] = move1;
        self.links[move3] = insert_before;
        self.current_cup = next_current_cup;
    }
}

fn main() {
    let input = "253149867";
    let n_cups = if is_part2() { 1_000_000 } else { 9 };
    let cups: Vec<usize> = input
        .chars()
        .map(|c| c.to_digit(10).unwrap() as usize)
        .chain(10..(n_cups + 1))
        .collect();
    let mut links = Links::from_list(&cups);
    let n_moves = if is_part2() { 10_000_000 } else { 100 };
    let progress = indicatif::ProgressBar::new(n_moves);
    progress.set_style(
        indicatif::ProgressStyle::default_bar()
            .template("[{eta_precise} left] {wide_bar} {pos}/{len}"),
    );
    for _ in 0..n_moves {
        links.do_move();
        progress.inc(1);
    }
    progress.finish_and_clear();
    if is_part2() {
        let next = links.next(1);
        let next2 = links.next(next);
        println!("{}", next * next2);
    } else {
        let mut cup = links.next(1);
        let mut order = vec![];
        while cup != 1 {
            order.push(cup.to_string());
            cup = links.next(cup);
        }
        println!("{}", order.join(""));
    }
}

Day 20, Part 2 (Again)

Back to the difficult puzzle from Day 20! In the meantime, a plan is forming; the plan seems clunky enough that it makes me think I am probably missing a more elegant solution, but I have gotten tired of this puzzle by now and I want to be done with it! What I will try to do, is to separate the tiles into a group of four corner tiles with two connections each, a group of edge tiles with three connections each, and a group of center tiles with four connections each. By the number of tiles in each group I should be able to figure out how big the total picture is.

I can then pick one of the corner tiles, determine which two sides don’t connect to any other tiles, place it in the correct orientation in the top left corner, and then start connecting edge tiles to it. Once I have the edge all connected, then I should be able to place all the center tiles correctly.

Here’s what I have written at this point, which I think is overly long and clunky and could use some refactoring:

#[derive(Clone, Copy, Debug, PartialEq)]
enum Direction {
    TOP = 0,
    RIGHT = 1,
    BOTTOM = 2,
    LEFT = 3,
}

impl Direction {
    fn opposite(&self) -> Self {
        use Direction::*;
        match *self {
            TOP => BOTTOM,
            RIGHT => LEFT,
            BOTTOM => TOP,
            LEFT => RIGHT,
        }
    }

    // returns the number of times to call rot90() on @other, to make it point
    // the same way as @self
    fn difference(self, other: Self) -> usize {
        ((4 + (other as i8) - (self as i8)) % 4) as usize
    }

    fn all() -> [Direction; 4] {
        use Direction::*;
        [TOP, RIGHT, BOTTOM, LEFT]
    }
}

bitflags! {
    struct Directions: u8 {
        const NONE = 0;
        const TOP = 0b0001;
        const RIGHT = 0b0010;
        const BOTTOM = 0b0100;
        const LEFT = 0b1000;
    }
}

#[derive(Clone, Debug, PartialEq)]
struct Tile {
    id: u64,
    // top, right, bottom, left borders with bits counted from LSB to MSB in
    // clockwise direction
    borders: [u16; 4],
    border_bits: u8, // number of bits in border
    image: Array2<u8>,
}

impl Tile {
    fn new(id: u64, grid: &Array2<u8>) -> Self {
        let borders = [
            s![0, ..],
            s![.., grid.ncols() - 1],
            s![grid.nrows() - 1, ..;-1],
            s![..;-1, 0],
        ]
        .iter()
        .map(|&slice| to_bits(grid.slice(slice)))
        .collect::<Vec<u16>>()
        .try_into()
        .unwrap();
        let image = grid
            .slice(s![1..grid.nrows() - 1, 1..grid.ncols() - 1])
            .into_owned();
        Tile {
            id,
            borders,
            image,
            border_bits: grid.ncols() as u8,
        }
    }

    // rotate counterclockwise n times
    fn rot90(&self, n: usize) -> Self {
        let rotated_view = match n % 4 {
            0 => self.image.view(),
            1 => self.image.slice(s![.., ..;-1]).reversed_axes(),
            2 => self.image.slice(s![..;-1, ..;-1]),
            3 => self.image.slice(s![..;-1, ..]).reversed_axes(),
            _ => panic!("Impossible"),
        };
        let rotated_image = rotated_view.into_owned();
        let mut borders = self.borders.clone();
        borders.rotate_left(n);
        Tile {
            id: self.id,
            borders,
            image: rotated_image,
            border_bits: self.border_bits,
        }
    }

    fn fliplr(&self) -> Self {
        let flipped_image = self.image.slice(s![.., ..;-1]).into_owned();
        let mut borders: Vec<_> = self
            .borders
            .iter()
            .map(|&b| flip_bits(b, self.border_bits))
            .collect();
        borders.reverse();
        borders.rotate_right(1);
        Tile {
            id: self.id,
            borders: borders.try_into().unwrap(),
            image: flipped_image,
            border_bits: self.border_bits,
        }
    }

    fn flipud(&self) -> Self {
        let flipped_image = self.image.slice(s![..;-1, ..]).into_owned();
        let mut borders: Vec<_> = self
            .borders
            .iter()
            .map(|&b| flip_bits(b, self.border_bits))
            .collect();
        borders.reverse();
        borders.rotate_left(1);
        Tile {
            id: self.id,
            borders: borders.try_into().unwrap(),
            image: flipped_image,
            border_bits: self.border_bits,
        }
    }

    fn connection_side(&self, other: &Self) -> Option<Direction> {
        let mut borders2: HashSet<_> = other.borders.iter().cloned().collect();
        borders2.extend(
            other
                .borders
                .iter()
                .map(|&b| flip_bits(b, self.border_bits)),
        );
        for (&border, &direction) in self.borders.iter().zip(Direction::all().iter()) {
            if borders2.contains(&border) {
                return Some(direction);
            }
        }
        None
    }

    fn connects_in_direction(&self, direction: Direction, other: &Self) -> Option<Direction> {
        let border_to_connect = self.borders[direction as usize];
        if let Some((_, &other_side)) = other
            .borders
            .iter()
            .zip(Direction::all().iter())
            .find(|(&border, _)| border == flip_bits(border_to_connect, self.border_bits))
        {
            println!(
                "{}'s {:?} side connects to {}'s {:?} side",
                self.id, direction, other.id, other_side
            );
            Some(other_side)
        } else {
            None
        }
    }
}

fn flip_bits(border: u16, n_bits: u8) -> u16 {
    assert!(n_bits <= 16);
    border.swap_bits() >> (16 - n_bits)
}

fn to_bits(slice: ArrayView<u8, Ix1>) -> u16 {
    let mut retval = 0;
    for (ix, &cell) in slice.iter().enumerate() {
        if cell > 0 {
            retval |= 2_u16.pow(ix.try_into().unwrap());
        }
    }
    retval
}

fn network(tiles: &Vec<Tile>) -> HashMap<u64, HashSet<u64>> {
    let mut connections = HashMap::new();
    for (tile1, tile2) in tiles.iter().tuple_combinations() {
        if tile1.connection_side(tile2).is_some() {
            let links1 = connections.entry(tile1.id).or_insert(HashSet::new());
            links1.insert(tile2.id);
            let links2 = connections.entry(tile2.id).or_insert(HashSet::new());
            links2.insert(tile1.id);
        }
    }
    connections
}

fn categorize(
    tiles: Vec<Tile>,
    connections: &HashMap<u64, HashSet<u64>>,
) -> (Vec<Tile>, Vec<Tile>, Vec<Tile>) {
    let mut corners = vec![];
    let mut edges = vec![];
    let mut centers = vec![];
    for tile in tiles {
        match connections.get(&tile.id).unwrap().len() {
            2 => corners.push(tile),
            3 => edges.push(tile),
            4 => centers.push(tile),
            _ => panic!("Impossible"),
        }
    }
    (corners, edges, centers)
}

fn orient_tile_correctly(tile: &Tile, tile_to_fit: &Tile, direction: Direction) -> Option<Tile> {
    match tile.connects_in_direction(direction, tile_to_fit) {
        None => (),
        Some(dir) => {
            let rotations = direction.opposite().difference(dir);
            println!("rotating {} by {} ccw", tile_to_fit.id, rotations);
            return Some(tile_to_fit.clone().rot90(rotations));
        }
    }
    let flipped = tile_to_fit.fliplr();
    match tile.connects_in_direction(direction, &flipped) {
        None => (),
        Some(dir) => {
            let rotations = direction.opposite().difference(dir);
            println!("flipping {} and rotating by {} ccw", flipped.id, rotations);
            return Some(flipped.rot90(rotations));
        }
    }
    None
}

fn find_and_orient_tile(
    tile: &Tile,
    possible_tiles: &[Tile],
    direction: Direction,
    connections: &HashMap<u64, HashSet<u64>>,
    used_tile_ids: &mut HashSet<u64>,
) -> Option<Tile> {
    let tile_connections = connections.get(&tile.id).unwrap();
    let candidates = possible_tiles
        .iter()
        .filter(|t| tile_connections.contains(&t.id) && !used_tile_ids.contains(&t.id));
    for candidate in candidates {
        println!(
            "candidate for connecting to {} ({:?}) is {} ({:?})",
            tile.id, tile.borders, candidate.id, candidate.borders
        );
        let next_tile = orient_tile_correctly(tile, candidate, direction);
        if let Some(t) = &next_tile {
            used_tile_ids.insert(t.id);
            return next_tile;
        }
    }
    None
}

fn arrange(
    corners: &[Tile],
    edges: &[Tile],
    centers: &[Tile],
    connections: &HashMap<u64, HashSet<u64>>,
) -> Array2<u8> {
    assert_eq!(corners.len(), 4);

    let mut used_tile_ids = HashSet::new();

    // Find top left corner - pick an arbitrary corner tile and rotate it until
    // it has connections on the right and bottom
    let mut tl_corner = corners[0].clone();
    used_tile_ids.insert(tl_corner.id);
    let mut tl_corner_connections = Directions::NONE;
    for possible_edge in edges {
        match tl_corner.connection_side(&possible_edge) {
            None => continue,
            Some(dir) if dir == Direction::TOP => tl_corner_connections |= Directions::TOP,
            Some(dir) if dir == Direction::RIGHT => tl_corner_connections |= Directions::RIGHT,
            Some(dir) if dir == Direction::BOTTOM => tl_corner_connections |= Directions::BOTTOM,
            Some(dir) if dir == Direction::LEFT => tl_corner_connections |= Directions::LEFT,
            Some(_) => panic!("Impossible"),
        }
    }
    tl_corner = tl_corner.rot90(match tl_corner_connections {
        dir if dir == Directions::RIGHT | Directions::BOTTOM => 0,
        dir if dir == Directions::BOTTOM | Directions::LEFT => 1,
        dir if dir == Directions::LEFT | Directions::TOP => 2,
        dir if dir == Directions::TOP | Directions::RIGHT => 3,
        _ => panic!("Impossible"),
    });

    // Build the top edge
    let mut t_row = vec![tl_corner];
    let mut current_tile = &t_row[t_row.len() - 1];
    loop {
        match find_and_orient_tile(
            &current_tile,
            &edges,
            Direction::RIGHT,
            connections,
            &mut used_tile_ids,
        ) {
            None => break,
            Some(tile) => {
                t_row.push(tile);
                current_tile = &t_row[t_row.len() - 1];
            }
        }
    }
    let tr_corner = find_and_orient_tile(
        &current_tile,
        &corners,
        Direction::RIGHT,
        connections,
        &mut used_tile_ids,
    )
    .unwrap();

    t_row.push(tr_corner);

    let ncols = t_row.len();
    let nrows = (corners.len() + edges.len() + centers.len()) / ncols;

    println!("whole image is {}×{}", ncols, nrows);

    // For each subsequent row except the bottom one...
    let mut rows = vec![t_row];
    for row in 1..nrows - 1 {
        // Find the left edge of the row
        let left = find_and_orient_tile(
            &rows[row - 1][0],
            &edges,
            Direction::BOTTOM,
            connections,
            &mut used_tile_ids,
        )
        .unwrap();
        let mut current_row = vec![left];
        // Arrange the middle tiles
        for col in 1..ncols - 1 {
            let next_tile = find_and_orient_tile(
                &current_row[col - 1],
                &centers,
                Direction::RIGHT,
                connections,
                &mut used_tile_ids,
            )
            .unwrap();
            current_row.push(next_tile);
        }
        // Find the right edge of the row
        let right = find_and_orient_tile(
            &current_row[ncols - 2],
            &edges,
            Direction::RIGHT,
            connections,
            &mut used_tile_ids,
        )
        .unwrap();
        current_row.push(right);

        rows.push(current_row);
    }

    // Now the bottom left corner
    let bl_corner = find_and_orient_tile(
        &rows[nrows - 2][0],
        &corners,
        Direction::BOTTOM,
        connections,
        &mut used_tile_ids,
    )
    .unwrap();
    let mut b_row = vec![bl_corner];
    // Bottom edge
    for col in 1..ncols - 1 {
        b_row.push(
            find_and_orient_tile(
                &b_row[col - 1],
                &edges,
                Direction::RIGHT,
                connections,
                &mut used_tile_ids,
            )
            .unwrap(),
        );
    }
    // Last tile
    let br_corner = find_and_orient_tile(
        &b_row[ncols - 2],
        &corners,
        Direction::RIGHT,
        connections,
        &mut used_tile_ids,
    )
    .unwrap();
    b_row.push(br_corner);
    rows.push(b_row);

    // Stack all the image data together
    let all_rows: Vec<_> = rows
        .iter()
        .map(|row| {
            let row_images: Vec<_> = row.iter().map(|t| t.image.view()).collect();
            concatenate(Axis(1), &row_images).unwrap()
        })
        .collect();
    concatenate(
        Axis(0),
        &all_rows.iter().map(|row| row.view()).collect::<Vec<_>>(),
    )
    .unwrap()
}

This isn’t done yet, I haven’t gotten to the point of scanning for sea monsters either, so I’ll have to tack that on to one of the final posts. It took me quite a long time to get this far, because of two bugs that I got stuck on:

  • When deciding which borders connect to each other, the border on one tile actually has to equal the bit-reversed border on the other tile. I didn’t notice this in Part 1, but it didn’t affect the answer, so it was in sort of a blind spot.
  • I was looking at ndarray::stack() in an old version of the ndarray docs on docs.rs without realizing it. In more recent versions, the stack() function was renamed to concatenate(), and stack() now does something else, and I couldn’t figure out why my result was wrong until I saw the tiny “⚠ Go to latest version” label in the corner. It would be nice if docs.rs would redirect you to the latest version when coming from search engines!

Afterword

Three of the four puzzles in this post went very smoothly. The final one got me to the point where I had to look for a hint, and I think this is another of those places where better knowledge of computer science fundamentals such as algorithms and data structures would have helped me; but on the other hand maybe not, since it is a puzzle after all, not a textbook problem. At least, it is nice that I at least had an idea (linked list) that was in the right direction, I don’t think it would have been enough to get there without the hint of storing the elements contiguously. These puzzles are challenging, but I still have to say that I’ve rarely, possibly never, faced a situation in my professional career where I’ve been hampered by missing knowledge such as this!

At least I did learn something from trying to solve the problem and from the hint! I learned how to profile Rust programs, and I learned a new application of a data structure that I will hopefully remember in the future.

I will make two more posts in this series: one with Day 24 plus the finish of Day 20, and one with Day 25.


[1] Which, played with the usual deck of 52 cards in four suits, we knew as War when I was a kid

Advent of Rust, Day 20 and 21: Stumped by Sea Monsters

Welcome back to another two days’ worth of the ongoing chronicle of me trying to teach myself the Rust programming language by doing programming puzzles from Advent of Code 2020.

Day 20, Part 1

Unlike in the past puzzles, I have no idea how to tackle this problem, so I start just by reading in the data. I’ll create a struct Tile to hold the data. I don’t have to store the actual image data, just the borders, so I can compare them to the borders of the other tiles.

There are eight borders — one on each of the four sides, plus the tiles may also be flipped, so the same borders again but reversed. I’ll store each border as a u16 bit pattern for easy comparing, in an array of length 8.

I do start out with the vague idea that I should use tuple_combinations() for this. But anyway, I’ll read in the data first.

#[macro_use]
extern crate scan_fmt;

use ndarray::{s, Array2, ArrayView, Ix1};
use std::convert::TryInto;

struct Tile {
    id: u16,
    borders: [u16; 8],
}

impl Tile {
    fn new(id: u16, grid: &Array2<u8>) -> Self {
        let borders = [
            s![0, ..],
            s![0, ..;-1],
            s![grid.nrows() - 1, ..],
            s![grid.nrows() - 1, ..;-1],
            s![.., 0],
            s![..;-1, 0],
            s![.., grid.ncols() - 1],
            s![..;-1, grid.ncols() - 1],
        ]
        .iter()
        .map(|&slice| to_bits(grid.slice(slice)))
        .collect::<Vec<u16>>()
        .try_into()
        .unwrap();
        Tile { id, borders }
    }
}

fn to_bits(slice: ArrayView<u8, Ix1>) -> u16 {
    let mut retval = 0;
    for (ix, &cell) in slice.iter().enumerate() {
        if cell > 0 {
            retval |= 2_u16.pow(ix.try_into().unwrap());
        }
    }
    retval
}

fn read_grid(lines: Vec<&str>) -> Array2<u8> {
    let rows = lines.len();
    let cols = lines[0].len();
    let mut cells = Array2::zeros((rows, cols));
    for (y, line) in lines.iter().enumerate() {
        for (x, tile) in line.bytes().enumerate() {
            cells[[y, x]] = match tile {
                b'#' => 1,
                b'.' => 0,
                _ => panic!("Bad tile '{}'", tile),
            };
        }
    }
    cells
}

fn read_tile(input: &str) -> Tile {
    let mut lines = input.lines();
    let header = lines.next().unwrap();
    let id = scan_fmt!(header, "Tile {}:", u16).unwrap();
    let grid = read_grid(lines.collect::<Vec<&str>>());
    Tile::new(id, &grid)
}

fn read_input(input: &'static str) -> impl Iterator<Item = Tile> {
    input.split("\n\n").map(read_tile)
}

I write the slice things (s![0, ..;-1]) after reading a bit more of the documentation about slicing ndarrays. I think this notation is an improvement on the Conway’s Game of Life code that I wrote a few days ago.

Maybe if there is only ever one possibility for each edge to match another tile’s edge, we can iterate over tuple_combinations() and check that there are four tiles that have only two possible connections to other tiles?

I add a HashSet<u16> of connections to the Tile type, and add these two methods:

fn connect(&mut self, other: &mut Self) {
    let borders1: HashSet<_> = self.borders.iter().collect();
    let borders2: HashSet<_> = other.borders.iter().collect();
    let intersection: HashSet<_> = borders1.intersection(&borders2).collect();
    match intersection.len() {
        0 => (),
        1 => {
            self.connections.insert(other.id);
            other.connections.insert(self.id);
        }
        _ => panic!(
            "Tile {} and {} can connect in more than one way",
            self.id, other.id
        ),
    }
}

fn n_connections(&self) -> usize {
    self.connections.len()
}

I try this to set up the network of tiles:

fn network(tiles: &mut Vec<Tile>) {
    for (&mut tile1, &mut tile2) in tiles.iter_mut().tuple_combinations() {
        tile1.connect(&mut tile2);
    }
}

tuple_combinations() doesn’t work, for one thing:

error[E0277]: the trait bound `std::slice::IterMut<'_, Tile>: std::clone::Clone` is not satisfied
  --> puzzle20.rs:81:54
   |
81 |     for (&mut tile1, &mut tile2) in tiles.iter_mut().tuple_combinations() {
   |                                                      ^^^^^^^^^^^^^^^^^^ the trait `std::clone::Clone` is not implemented for `std::slice::IterMut<'_, Tile>`

error[E0277]: the trait bound `&mut Tile: std::clone::Clone` is not satisfied
  --> puzzle20.rs:81:54
   |
81 |     for (&mut tile1, &mut tile2) in tiles.iter_mut().tuple_combinations() {
   |                                                      ^^^^^^^^^^^^^^^^^^ the trait `std::clone::Clone` is not implemented for `&mut Tile`
   |
   = note: `std::clone::Clone` is implemented for `&Tile`, but not for `&mut Tile`

If I understand the error message correctly, this is because tuple_combinations() makes copies of the elements, and I don’t think I can copy the tiles — for one thing, I want the number of connections to be updated in the same copy of the tile, I don’t want different copies of the same tile with different connections!

I try indexing the array and iterating over tuple combinations of indices:

fn network(tiles: &mut Vec<Tile>) {
    let indices = 0..tiles.len();
    for (ix1, ix2) in indices.tuple_combinations() {
        tiles[ix1].connect(&mut tiles[ix2]);
    }
}

This also doesn’t work:

error[E0499]: cannot borrow `*tiles` as mutable more than once at a time
  --> puzzle20.rs:80:33
   |
80 |         tiles[ix1].connect(&mut tiles[ix2]);
   |         -----      -------      ^^^^^ second mutable borrow occurs here
   |         |          |
   |         |          first borrow later used by call
   |         first mutable borrow occurs here

This I don’t understand. I don’t want to borrow the whole array twice, I just want to modify elements in it.

Eventually, after trying a lot more things, I give up, and store the connections in a separate collection:

impl Tile {
    fn connects_to(&self, other: &Self) -> bool {
        let borders1: HashSet<_> = self.borders.iter().collect();
        let borders2: HashSet<_> = other.borders.iter().collect();
        let intersection: HashSet<_> = borders1.intersection(&borders2).collect();
        match intersection.len() {
            0 => false,
            1 => true,
            _ => panic!(
                "Tile {} and {} can connect in more than one way",
                self.id, other.id
            ),
        }
    }
}

fn network(tiles: Vec<Tile>) -> HashMap<u16, HashSet<u16>> {
    let mut connections = HashMap::new();
    for (tile1, tile2) in tiles.iter().tuple_combinations() {
        if tile1.connects_to(tile2) {
            let links1 = connections.entry(tile1.id).or_insert(HashSet::new());
            links1.insert(tile2.id);
            let links2 = connections.entry(tile2.id).or_insert(HashSet::new());
            links2.insert(tile1.id);
        }
    }
    connections
}

This works, but running it on the example input I get ‘Tile 2311 and 1951 can connect in more than one way’! Then I realize that yes, they could both be connected, but if you flip both of them, then they can still be connected. So we should expect that tiles connect in either 0 or 2 possible ways in connects_to().

For the array of connections in the example input, I get 4 tiles with 2 connections, 4 tiles with 3 connections, and one tile with 4 connections, which is consistent with the tiles being arranged in a 3×3 square.

Running it on the real input I get a panic, because a zero-length string is being passed to read_tile(). Sure enough, there is an extra newline at the end of the file. I wonder if instead of splitting on "\n\n" I can split on "\n{2,}", but that requires adding a dependency on the regex package which I’m not using anywhere else, so I add a .filter(|s| s.len() > 0) to read_input().

Finally I write the main() function which looks like this:

fn main() {
    let input = include_str!("input");
    let tiles = read_input(input);
    let connections = network(&tiles);

    let answer: u32 = connections
        .iter()
        .filter(|(_, links)| links.len() == 2)
        .map(|(id, _)| id)
        .product();
    println!("{}", answer);
}

I get an overflow in the call to product() so I change the type of the IDs to u64. This gives me the right answer.

Day 20, Part 2

Next we have to remove the borders of the tiles, and arrange them in the correct configuration, and then search for “sea monsters” that look like this:

                  #
#    ##    ##    ###
 #  #  #  #  #  #

From experience at a job a long time ago, I know how to search for the sea monster, by using cross-correlation, which I would be willing to bet that ndarray is capable of doing. Before I get to that part, however, I’m a bit at a loss for how to stitch the pictures together. I feel that I could do it, but without a good plan it would probably be very messy and take me a lot of time to finish.

I decide once again to start by storing the data that I will need, and then see if I get any ideas while doing that.

First of all, I will need to store the tile, as an ndarray::Array2, without the borders. This can be done by taking a slice and copying it into an owned array, in the constructor:

let image = grid
    .slice(s![1..grid.nrows() - 1, 1..grid.ncols() - 1])
    .into_owned();
Tile { id, borders, image }

Now I’m not sure what to do. I take a break and work on Day 21 instead. When I come back to it, I don’t really have any more ideas.

I decide that since the orientation of each tile is now important, I should do some refactors to Tile. I will add rot90(), fliplr(), and flipud() methods (named after the NumPy functions), and I won’t store eight borders in an arbitrary order, but instead four borders in the order top, right, bottom, and left. The rotating and flipping operations will manipulate the array of borders so that they are correct for the new orientation.

#[derive(Debug, PartialEq)]
struct Tile {
    id: u64,
    // top, right, bottom, left borders with bits counted from LSB to MSB in
    // clockwise direction
    borders: [u16; 4],
    border_bits: u8, // number of bits in border
    image: Array2<u8>,
}

impl Tile {
    fn new(id: u64, grid: &Array2<u8>) -> Self {
        let borders = [
            s![0, ..],
            s![.., grid.ncols() - 1],
            s![grid.nrows() - 1, ..;-1],
            s![..;-1, 0],
        ]
        .iter()
        .map(|&slice| to_bits(grid.slice(slice)))
        .collect::<Vec<u16>>()
        .try_into()
        .unwrap();
        let image = grid
            .slice(s![1..grid.nrows() - 1, 1..grid.ncols() - 1])
            .into_owned();
        Tile {
            id,
            borders,
            image,
            border_bits: grid.ncols() as u8,
        }
    }

    // rotate counterclockwise n times
    fn rot90(&self, n: usize) -> Self {
        let rotated_view = match n % 4 {
            0 => self.image.view(),
            1 => self.image.slice(s![.., ..;-1]).reversed_axes(),
            2 => self.image.slice(s![..;-1, ..;-1]),
            3 => self.image.slice(s![..;-1, ..]).reversed_axes(),
            _ => panic!("Impossible"),
        };
        let rotated_image = rotated_view.into_owned();
        let mut borders = self.borders.clone();
        borders.rotate_left(n);
        Tile {
            id: self.id,
            borders,
            image: rotated_image,
            border_bits: self.border_bits,
        }
    }

    fn fliplr(&self) -> Self {
        let flipped_image = self.image.slice(s![.., ..;-1]).into_owned();
        let mut borders: Vec<_> = self
            .borders
            .iter()
            .map(|&b| flip_bits(b, self.border_bits))
            .collect();
        borders.reverse();
        borders.rotate_right(1);
        Tile {
            id: self.id,
            borders: borders.try_into().unwrap(),
            image: flipped_image,
            border_bits: self.border_bits,
        }
    }

    fn flipud(&self) -> Self {
        let flipped_image = self.image.slice(s![..;-1, ..]).into_owned();
        let mut borders: Vec<_> = self
            .borders
            .iter()
            .map(|&b| flip_bits(b, self.border_bits))
            .collect();
        borders.reverse();
        borders.rotate_left(1);
        Tile {
            id: self.id,
            borders: borders.try_into().unwrap(),
            image: flipped_image,
            border_bits: self.border_bits,
        }
    }

    fn connects_to(&self, other: &Self) -> bool {
        let borders1: HashSet<_> = self.borders.iter().cloned().collect();
        let mut borders2: HashSet<_> = other.borders.iter().cloned().collect();
        borders2.extend(
            other
                .borders
                .iter()
                .map(|&b| flip_bits(b, self.border_bits)),
        );
        let intersection: HashSet<_> = borders1.intersection(&borders2).collect();
        match intersection.len() {
            0 => false,
            1 => true,
            _ => panic!(
                "Tile {} and {} can connect in more than one way",
                self.id, other.id
            ),
        }
    }
}

fn flip_bits(border: u16, n_bits: u8) -> u16 {
    assert!(n_bits <= 16);
    border.swap_bits() >> (16 - n_bits)
}

fn to_bits(slice: ArrayView<u8, Ix1>) -> u16 {
    let mut retval = 0;
    for (ix, &cell) in slice.iter().enumerate() {
        if cell > 0 {
            retval |= 2_u16.pow(ix.try_into().unwrap());
        }
    }
    retval
}

I also write some tests for this code, and debug it until the tests pass. The full code is on the repository. This, at least, still gives me the correct answer for Part 1. However, I’m really tired of doing this puzzle, so I think I’ll stop for now and leave it for another day.

Day 21, Part 1

Here, we have ingredient lists in a language we don’t understand, of foods containing ingredients such as “sqjhc”, “mxmxvkd”, and “kfcds”. These foods also have allergen lists in English. Each allergen is present in one ingredient and each ingredient contains either zero or one allergen. We have to determine which ingredients contain zero allergens, and count how many times they appear in our input.

Here’s another puzzle where I’m not sure how to get started, and so I decide once more to at least write code to read in the data.

use std::collections::HashSet;

struct Food {
    ingredients: HashSet<String>,
    allergens: HashSet<String>,
}

impl Food {
    fn from_string(s: &str) -> Self {
        let mut split1 = s[0..s.len() - 1].split(" (contains ");
        let (ingredients_list, allergens_list) = (split1.next().unwrap(), split1.next().unwrap());
        let ingredients = ingredients_list.split(' ').map(String::from).collect();
        let allergens = allergens_list.split(", ").map(String::from).collect();
        Food {
            ingredients,
            allergens,
        }
    }
}

I also write a test for this, which I’ll copy here since I found the way to assert the contents of a HashSet to be unusually verbose:

#[test]
fn test_parse_food() {
    let food = Food::from_string("mxmxvkd kfcds sqjhc nhms (contains dairy, fish)");
    assert_eq!(
        food.ingredients,
        ["mxmxvkd", "kfcds", "sqjhc", "nhms"]
            .iter()
            .cloned()
            .map(String::from)
            .collect()
    );
    assert_eq!(
        food.allergens,
        ["dairy", "fish"]
            .iter()
            .cloned()
            .map(String::from)
            .collect()
    );
}

It would be nice if we could say something like assert_contains!(food.ingredients, ["mxmxvkd", "kfcds", "sqjhc", "nhms"]).

I’m having trouble figuring out how to get the answer not because I’m not sure about how something works in Rust, but just because it’s not even clear to me how to solve the example problem.

I take a break and think about it some more. I wonder if we could take the tuple combinations of all foods, and compare the foods in each tuple; if they have a common allergen, then all the ingredients that are in one of the foods but not both, are non-allergens.

I write this code:

fn find_non_allergens(foods: &[Food]) -> HashSet<String> {
    foods
        .iter()
        .tuple_combinations()
        .flat_map(|(food1, food2)| {
            if food1.allergens.union(&food2.allergens).count() > 0 {
                food1
                    .ingredients
                    .symmetric_difference(&food2.ingredients)
                    .map(String::from)
                    .collect()
            } else {
                vec![]
            }
        })
        .collect()
}

That doesn’t work, though! The list of non-allergens that it yields on the example problem is too long, including ingredients that might have allergens. This is because of something in the puzzle description that I forgot to take into account: foods might not list all the allergens that they have.

My second attempt makes a list of ingredients possible_allergens that initially could contain any allergen, and removes them as they are found to be impossible:

fn find_non_allergens(foods: &[Food]) -> HashSet<String> {
    let all_allergens: HashSet<_> = foods
        .iter()
        .flat_map(|food| food.allergens.clone())
        .collect();
    let all_ingredients: Vec<_> = foods
        .iter()
        .flat_map(|food| food.ingredients.clone())
        .collect();
    let mut possible_allergens: HashMap<_, HashSet<_>> = all_ingredients
        .iter()
        .map(|ingredient| (ingredient.clone(), all_allergens.clone()))
        .collect();
    for (food1, food2) in foods.iter().tuple_combinations() {
        let allergens_in_both: Vec<_> = food1.allergens.intersection(&food2.allergens).collect();
        let ingredients_not_in_both: Vec<_> = food1
            .ingredients
            .symmetric_difference(&food2.ingredients)
            .map(String::from)
            .collect();
        for ingredient in &ingredients_not_in_both {
            for &allergen in &allergens_in_both {
                possible_allergens
                    .get_mut(ingredient)
                    .unwrap()
                    .remove(allergen);
            }
        }
    }
    possible_allergens
        .iter()
        .filter(|(_, allergens)| allergens.len() == 0)
        .map(|(ingredient, _)| ingredient.clone())
        .collect()
}

This doesn’t work either; “soy” is not ruled out for any of the ingredients, because there are no two foods in the example data that both contain “soy”.

I note that the compiler’s error message when trying to mutate a HashMap value gotten with get() is not very enlightening:

error[E0596]: cannot borrow data in a `&` reference as mutable
  --> puzzle21.rs:45:17
   |
45 |                 possible_allergens.get(ingredient).unwrap().remove(allergen);
   |                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ cannot borrow as mutable

Maybe it should suggest using get_mut() here!

While writing this I notice that I mistakenly used union() in the previous example instead of intersection(), so I quickly go back and try that, but it doesn’t work either.

Then I have a brainwave and realize that I don’t need to compare pairs of foods at all. If a food is listed as containing allergens, then the ingredients that are not in that food cannot contain those allergens. I write this code and get the correct answer from both the example data and the real puzzle input:

fn find_non_allergens(foods: &[Food]) -> HashSet<String> {
    let all_allergens: HashSet<_> = foods
        .iter()
        .flat_map(|food| food.allergens.clone())
        .collect();
    let all_ingredients: Vec<_> = foods
        .iter()
        .flat_map(|food| food.ingredients.clone())
        .collect();
    let mut possible_allergens: HashMap<_, HashSet<_>> = all_ingredients
        .iter()
        .map(|ingredient| (ingredient.clone(), all_allergens.clone()))
        .collect();
    for food in foods {
        for ingredient in all_ingredients
            .iter()
            .filter(|&ingredient| !food.ingredients.contains(ingredient))
        {
            for allergen in &food.allergens {
                possible_allergens
                    .get_mut(ingredient)
                    .unwrap()
                    .remove(allergen);
            }
        }
    }
    possible_allergens
        .iter()
        .filter(|(_, allergens)| allergens.is_empty())
        .map(|(ingredient, _)| ingredient.clone())
        .collect()
}

fn main() {
    let input = include_str!("input");
    let foods: Vec<Food> = input.lines().map(|s| Food::from_string(s)).collect();
    let non_allergens = find_non_allergens(&foods);
    let count: usize = non_allergens
        .iter()
        .map(|ingredient| {
            foods
                .iter()
                .filter(|food| food.ingredients.contains(ingredient))
                .count()
        })
        .sum();
    println!("{}", count);
}

Day 21, Part 2

Part 2 of the puzzle, as one might have expected, is to figure out which ingredients do contain which allergens. The answer to the puzzle is a comma-separated list of ingredients, sorted by allergen alphabetically.

For this we need to reuse possible_allergens, so I first split find_non_allergens() into a find_possible_allergens() function that returns possible_allergens, and a new find_non_allergens() function that does the filtering and mapping on that.

Then we can copy part of the solution from Day 16:

fn determine_allergens(
    possible_allergens: &HashMap<String, HashSet<String>>,
) -> HashMap<String, String> {
    let mut to_be_determined: Vec<_> = possible_allergens
        .iter()
        .map(|(s, set)| (s.clone(), set.clone()))
        .collect();

    let mut dangerous_ingredient_list = HashMap::new();
    while !to_be_determined.is_empty() {
        to_be_determined.sort_by_key(|(_, set)| set.len());
        to_be_determined.reverse();

        let (ingredient, allergens) = to_be_determined.pop().unwrap();
        if allergens.is_empty() {
            continue;
        }
        assert!(allergens.len() == 1, "unable to determine allergens");
        let allergen = allergens.iter().next().unwrap();
        dangerous_ingredient_list.insert(allergen.clone(), ingredient.clone());
        for (_, remaining_allergens) in &mut to_be_determined {
            remaining_allergens.remove(allergen);
        }
    }
    dangerous_ingredient_list
}

The difference is that we have to re-sort the list every iteration, since in one iteration you might rule out soy, but the next item might not have soy as a possibility because it was ruled out from a later item — as I find out by a panic when trying to run it.

Then to get the answer, I write:

let mut dangerous_ingredient_list = determine_allergens(&possible_allergens);
let mut dangerous_ingredients = dangerous_ingredient_list.drain().collect::<Vec<_>>();
dangerous_ingredients.sort_by(|(allergen1, _), (allergen2, _)| allergen1.cmp(allergen2));
let list = dangerous_ingredients
    .drain(..)
    .map(|(_, ingredient)| ingredient)
    .collect::<Vec<_>>()
    .join(",");
println!("{}", list);

The full code is on the repository.

Afterword

The puzzles are definitely getting more difficult! In many of the previous puzzles, I’ve felt like I had a general idea about how to proceed, but I didn’t feel that on Day 20. Instead, this is the first time that I actually gave up on a puzzle and went on to the next one.

There certainly is a lot of .iter()....collect() in the code from both days, to convert between Vec, HashSet, and HashMap. This seems unnecessarily verbose, I wonder if there’s a more idiomatic way that I’m missing?

Advent of Rust 18 and 19: Parsers and New Math

It’s another two days of the ongoing chronicle of me trying to teach myself the Rust programming language by doing programming puzzles from Advent of Code 2020. I’m well over halfway, in fact today’s post includes the three-quarters mark.

I mentioned it last time, but I’ve found this series from an experienced Rust programmer also doing these puzzles in Rust to be very enlightening (hat tip, Federico Mena Quintero.)

Day 18, Part 1

Today we have to solve arithmetic homework problems, from a bizarro parallel universe where there is no precedence of operators. We get an input file with homework problems that look like 1 + 2 * 3 + 4 * 5 + 6 to which the answer is not 33 as you might expect, but 71 because in the absence of parentheses you just do all the operations from left to right.

I have in the past had to build a parser for (normal) arithmetic expressions, so in theory I should know how to do this. However, reading the Faster than Lime posts, I have seen that the author is often using a Rust parser generator package called PEG for the problems where I used scan_fmt!(), and it looks quite easy to use. So I decide to use PEG as well to generate this parser.

Luckily there is literally the exact thing I need, a parser for arithmetic expressions with precedence of operators, in one of the examples in the PEG documentation! I just need to tweak it so that the precedence of addition and multiplication is equal:

extern crate peg;

peg::parser! {
    grammar bizarro_arithmetic() for str {
        rule number() -> u64 = n:$(['0'..='9']) { n.parse().unwrap() }
        pub rule expr() -> u64 = precedence!{
            x:(@) " + " y:@ { x + y }
            x:(@) " * " y:@ { x * y }
            --
            n:number() { n }
            "(" e:expr() ")" { e }
        }
    }
}

It’s slightly weird, and trips me up for a little while, that in order to accommodate the spaces in the strings I have to explicitly use the token " + ", and can’t just tell it to tokenize on whitespace. But eventually I figure it out.

Another thing that Faster than Lime has been doing is writing inline tests! This is pretty cool, and I decide to do it here with the examples in the puzzle description:

#[test]
fn part1_examples() {
    assert_eq!(bizarro_arithmetic::expr("1 + 2 * 3 + 4 * 5 + 6"), Ok(71));
    assert_eq!(bizarro_arithmetic::expr("1 + (2 * 3) + (4 * (5 + 6))"), Ok(51));
    assert_eq!(bizarro_arithmetic::expr("2 * 3 + (4 * 5)"), Ok(26));
    assert_eq!(bizarro_arithmetic::expr("5 + (8 * 3 + 9 + 3 * 4 * 3)"), Ok(437));
    assert_eq!(bizarro_arithmetic::expr("5 * 9 * (7 * 3 * 3 + 9 * 3 + (8 + 6 * 4))"), Ok(12240));
    assert_eq!(bizarro_arithmetic::expr("((2 + 4 * 9) * (6 + 9 * 8 + 6) + 6) + 2 + 4 * 2"), Ok(13632));
}

Running cargo test will execute these tests, and that helps me fix the bug that I mentioned above where I had "+" instead of " + ".

Once that is working, I’m pleasantly surprised that I’ve gotten to the point of confidence that the main() function practically writes itself:

fn main() {
    let input = include_str!("input");
    let answer: u64 = input
        .lines()
        .map(bizarro_arithmetic::expr)
        .map(|n| n.unwrap())
        .sum();
    println!("{}", answer);
}

Thanks to PEG, this has been one of the easiest puzzles so far, unless you consider using a parser generator “cheating” (which I most certainly don’t.)

Day 18, Part 2

Part 2 of the puzzle is just the same as Part 1, only with addition given a higher precedence than multiplication. According to the PEG documentation this can be achieved just by swapping the order and adding a -- to separate the two. I add a rule to the parser generator:

pub rule expr2() -> u64 = precedence!{
    x:(@) " * " y:@ { x * y }
    --
    x:(@) " + " y:@ { x + y }
    --
    n:number() { n }
    "(" e:expr2() ")" { e }
}

I also write inline tests for this one using the examples in the puzzle description. This inline testing thing is brilliant!

Then I change the map() call in main() to use the correct parser depending on whether we are running Part 1 or Part 2:

.map(if is_part2() {
    bizarro_arithmetic::expr2
} else {
    bizarro_arithmetic::expr
})

On to the next puzzle!

Day 19, Part 1

Today’s puzzle is validating a bunch of messages against rules given in a grammar-like form. The grammar has a certain syntax, which makes me think I can use what I learned yesterday about PEG to parse it. But instead of using a PEG parser that gives a number as the parsed result, we have to build a parser that gives… another, dynamically-generated, parser.

This sounds really daunting, and I almost say “oh no!” out loud when I read the puzzle description.

I take a long break and by the time I come back to it, it has occurred to me that maybe instead of another parser, the PEG parser can give a regular expression that we can use to match the messages? Ultimately, a regular expression is really a sort of dynamically-generated parser. I feel good about this idea.

After thinking about it some more after that, I realize I might have to have one intermediate step, because rules can reference other rules that haven’t been defined yet. So I will have to read them all in, parse them into an intermediate form such as an enum, and then generate a regular expression against which I match all the messages.

The rules are in a form like this:

0: 1 2
1: "a"
2: 1 3 | 3 1
3: "b"

This means that rule 0 consists of rule 1 followed by rule 2, rule 1 is the 'a' character, rule 3 is the 'b' character, and rule 2 consists of either 1 followed by 3, or 3 followed by 1, in other words "ab" or "ba". The rules are guaranteed to have no loops. Ideally this would yield the regular expression ^a(ab|ba)$ which I could then match against the list of messages.

I write a Rule enum and a RuleSet type, during which I learn that enum variants may not reference other enum variants. The compiler suggests using Box, so that’s what I do:

#[derive(Debug)]
enum Rule {
    Literal(char),
    Ref(usize),
    Seq(Box<Rule>, Box<Rule>),
    Choice(Box<Rule>, Box<Rule>),
}

type RuleSet = HashMap<usize, Rule>;

Using what I learned from yesterday’s puzzle, the parser follows:

peg::parser! {
    grammar rule_set() for str {
        rule index() -> usize = n:$(['0'..='9']+) ":" { n.parse().unwrap() }
        rule number() -> Rule = n:$(['0'..='9']+) { Rule::Ref(n.parse().unwrap()) }
        rule literal() -> Rule = "\"" c:$(['a'..='z' | 'A'..='Z']) "\"" {
            Rule::Literal(c.chars().next().unwrap())
        }
        rule seq() -> Rule = a:number() " " b:number() { Rule::Seq(Box::new(a), Box::new(b)) }
        rule choice_side() -> Rule = seq() / number()
        rule choice() -> Rule = a:choice_side() " | " b:choice_side() {
            Rule::Choice(Box::new(a), Box::new(b))
        }
        pub rule parse_line() -> (usize, Rule) =
            ix:index() " " expr:(choice() / seq() / number() / literal()) { (ix, expr) }
    }
}

This doesn’t compile:

error[E0446]: private type `Rule` in public interface
  --> puzzle19.rs:15:2
   |
6  |   enum Rule {
   |   - `Rule` declared as private
...
15 |   peg::parser! {
   |  __^
16 | |     grammar rule_set() for str {
17 | |         rule index() -> usize = n:$(['0'..='9']+) ":" { n.parse().unwrap() }
18 | |         rule number() -> Rule = n:$(['0'..='9']+) { Rule::Ref(n.parse().unwrap()) }
...  |
24 | |     }
25 | | }
   | |_^ can't leak private type
   |
   = note: this error originates in a macro (in Nightly builds, run with -Z macro-backtrace for more info)

I’m not sure why this is happening, because enum Rule is at the top level and so is the PEG parser, so they ought to just have access to each other? In any case, I change it to pub enum Rule and it compiles

I then write a test for this parser:

#[test]
fn example1() {
    let mut rule_set = RuleSet::new();
    let example1 = ["0: 1 2", "1: \"a\"", "2: 1 3 | 3 1", "3: \"b\""];
    for line in example1.iter() {
        let (ix, rule) = rules_grammar::parse_line(line).unwrap();
        rule_set.insert(ix, rule);
    }

    use Rule::*;
    assert_eq!(rule_set.get(0), Some(Seq(Ref(1), Ref(2))));
    assert_eq!(rule_set.get(1), Some(Literal('a')));
    assert_eq!(
        rule_set.get(2),
        Some(Choice(Seq(Ref(1), Ref(3)), Seq(Ref(3), Ref(1))))
    );
    assert_eq!(rule_set.get(3), Some(Literal('b')));
}

It’s very wrong according to the compiler!

error[E0308]: mismatched types
  --> puzzle19.rs:46:29
   |
46 |     assert_eq!(rule_set.get(0), Some(Seq(Ref(1), Ref(2))));
   |                             ^
   |                             |
   |                             expected `&usize`, found integer
   |                             help: consider borrowing here: `&0`

error[E0308]: mismatched types
  --> puzzle19.rs:46:42
   |
46 |     assert_eq!(rule_set.get(0), Some(Seq(Ref(1), Ref(2))));
   |                                          ^^^^^^
   |                                          |
   |                                          expected struct `Box`, found enum `Rule`
   |                                          help: store this in the heap by calling `Box::new`: `Box::new(Ref(1))`
   |
   = note: expected struct `Box<Rule>`
                found enum `Rule`
   = note: for more on the distinction between the stack and the heap, read https://doc.rust-lang.org/book/ch15-01-box.html, https://doc.rust-lang.org/rust-by-example/std/box.html, and https://doc.rust-lang.org/std/boxed/index.html

error[E0308]: mismatched types
  --> puzzle19.rs:46:50
   |
46 |     assert_eq!(rule_set.get(0), Some(Seq(Ref(1), Ref(2))));
   |                                                  ^^^^^^
   |                                                  |
   |                                                  expected struct `Box`, found enum `Rule`
   |                                                  help: store this in the heap by calling `Box::new`: `Box::new(Ref(2))`
   |
   = note: expected struct `Box<Rule>`
                found enum `Rule`
   = note: for more on the distinction between the stack and the heap, read https://doc.rust-lang.org/book/ch15-01-box.html, https://doc.rust-lang.org/rust-by-example/std/box.html, and https://doc.rust-lang.org/std/boxed/index.html

error[E0369]: binary operation `==` cannot be applied to type `Option<&Rule>`
  --> puzzle19.rs:46:5
   |
46 |     assert_eq!(rule_set.get(0), Some(Seq(Ref(1), Ref(2))));
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |     |
   |     Option<&Rule>
   |     Option<Rule>
   |
   = note: this error originates in a macro (in Nightly builds, run with -Z macro-backtrace for more info)

First of all, I’m not sure why the integer has to be borrowed to index the hash map! The second and third errors I do understand, because the rules need a Box::new() around them, though I’m not sure how that will work with asserting equality! Will it compare the addresses of the Boxes? And I don’t understand the fourth error, can’t assert_eq!() just check that the rules contain all the same variants?

Even if I do this to reference the right side:

assert_eq!(rule_set.get(&0), Some(&Seq(Box::new(Ref(1)), Box::new(Ref(2)))));

I still get an error such as this:

error[E0369]: binary operation `==` cannot be applied to type `Rule`
  --> puzzle19.rs:51:5
   |
51 |       assert_eq!(
   |  _____^
   | |_____|
   | |
52 | |         *rule_set.get(&0).unwrap(),
53 | |         Seq(Box::new(Ref(1)), Box::new(Ref(2)))
54 | |     );
   | |      ^
   | |______|
   | |______Rule
   |        Rule
   |
   = note: an implementation of `std::cmp::PartialEq` might be missing for `Rule`

(This hint doesn’t show up in the editor inline messages, but it does on the command line. Strange.) I guess PartialEq is exactly what’s missing, because adding it makes the tests pass, so apparently my worry about Box comparing by address was unfounded.

I also write the second example from the puzzle description as a test, but the first line 0: 4 1 5 already poses a problem, since I’ve written Seq so that it takes only a number, not another Seq. I have to rewrite the Rule::Seq member to be defined as Seq(Vec(Rule))1 and then rewrite the grammar to correspond to that. PEG’s ** operator with an optional minimum number of repetitions is very handy here:

rule seq() -> Rule = refs:(number() **<2,> " ") { Rule::Seq(refs) }

While debugging I also notice that order is important in /, which I’d originally gotten wrong.

I then write a trio of functions that convert rule 0 of a rule set into regex code for matching the input:

fn rule_to_regex(rule_set: &RuleSet, rule: &Rule) -> String {
    use Rule::*;
    match rule {
        Literal(c) => c.to_string(),
        Ref(ref_ix) => rule_index_to_regex(rule_set, *ref_ix),
        Seq(refs) => refs
            .iter()
            .map(|r| rule_to_regex(rule_set, r))
            .collect::<Vec<String>>()
            .join(""),
        Choice(l, r) => format!(
            "({}|{})",
            rule_to_regex(rule_set, &*l),
            rule_to_regex(rule_set, &*r)
        ),
    }
}

fn rule_index_to_regex(rule_set: &RuleSet, ix: usize) -> String {
    let rule = rule_set.get(&ix).unwrap();
    rule_to_regex(rule_set, rule)
}

fn rule_set_to_regex(rule_set: &RuleSet) -> String {
    format!("^{}$", rule_index_to_regex(rule_set, 0))
}

I add code to my tests such as this, in order to debug it:

let regex = rule_set_to_regex(&rule_set);
assert_eq!(regex, "^a(ab|ba)$");

Once I’ve got it working then I also test the second example against the example messages given in the puzzle description, with code like this:

let matcher = Regex::new(®ex).unwrap();
assert!(matcher.is_match("ababbb"));
assert!(!matcher.is_match("bababa"));
assert!(matcher.is_match("abbbab"));
assert!(!matcher.is_match("aaabbb"));
assert!(!matcher.is_match("aaaabbb"));

I’ve already done most of the work for the main function at this point, I just need to copy it from the tests:

fn main() {
    let input = include_str!("input");
    let mut blocks = input.split("\n\n");

    let rules_block = blocks.next().unwrap();
    let mut rule_set = RuleSet::new();
    for line in rules_block.lines() {
        let (ix, rule) = rules_grammar::parse_line(line).unwrap();
        rule_set.insert(ix, rule);
    }
    let matcher = Regex::new(&rule_set_to_regex(&rule_set)).unwrap();

    let messages_block = blocks.next().unwrap();
    let matches = messages_block
        .lines()
        .map(|line| matcher.is_match(line))
        .count();

    println!("{}", matches);
}

I get an answer and it’s too high. Oh, no! I am probably generating incorrect regex code.

Before I start digging into that, I decide to do a quick reality check, and print out the number of rules in the RuleSet, as well as the number of total messages, to make sure I have gotten all of the ones in the file. The number of rules is correct, but the number of messages is equal to the answer I just got! And then I see it … I used map() instead of filter() to count the number of valid messages. Now I get the correct answer.

Day 19, Part 2

Part 2 of the puzzle asks you to change rule 8 from 8: 42 to 8: 42 | 42 8, and rule 11 from 11: 42 31 | 42 11 31, and then count the number of valid messages again. The puzzle description says that this means the rules do now contain loops, but they give you a very big hint to hard-code this and not make your code generally handle loops.

I look at the two rule modifications. In regex-speak, 8: 42 | 42 8 is really just saying 8: 42+, that is, one or more applications of rule 42. So we could modify rule_index_to_regex() to hard-code an exception when ix == 8, return "(...)+" where ... is the regex code for rule 42. This seems like it should be easy to do.

For the modification to rule 11, on the other hand, I cannot come up with the change that I would need to make to the regex. After some browsing I find that someone else has asked the same thing on Stack Overflow, and it is not possible to do it in a regular expression because such a match is not regular! (The Stack Overflow shows how it can be done in Perl with backreferences, but the documentation tells me that the regular expression engine used in Rust’s regex module does not support this because it can blow up exponentially.2)

I am briefly afraid that I will have to rewrite my entire program to not use regular expressions because the problem is no longer regular.

I realize that I should listen to the hint from the puzzle description, and only deal with the input that I have, instead of trying to solve the puzzle generally. I can get around this limitation by allowing up to a certain number of loops, instead of infinite loops. For example, let’s say that rule 42 is "a" and rule 31 is "b", then rule 11 ought to match ab, aabb, aaabbb, etc. But we know that none of our messages are infinitely long, so there’s a maximum number of as and bs that we have to match. We can write the regex (ab|a{2}b{2}|a{3}b{3}|a{4}b{4}), for example, if that maximum number is 4. We just have to figure out, or more likely, estimate,3 what that maximum number is. The upper bound for that maximum number is the length of our longest message divided by 2, which is 44, but in practice it should be much less, because rules 42 and 31 are not single letters, and rule 11 is not the start symbol.

I start with trying a maximum of 4 repetitions. This is now my rule_index_to_regex() function:

fn rule_index_to_regex(rule_set: &RuleSet, ix: usize, is_part2: bool) -> String {
    let rule = rule_set.get(&ix).unwrap();
    match ix {
        8 if is_part2 => format!("({})+", rule_to_regex(rule_set, rule, is_part2)),
        11 if is_part2 => {
            if let Rule::Seq(refs) = rule {
                format!(
                    "({0}{1}|{0}{{2}}{1}{{2}}|{0}{{3}}{1}{{3}}|{0}{{4}}{1}{{4}})",
                    rule_to_regex(rule_set, &refs[0], is_part2),
                    rule_to_regex(rule_set, &refs[1], is_part2)
                )
            } else {
                panic!("Wrong type for rule 11");
            }
        }
        _ => rule_to_regex(rule_set, rule, is_part2),
    }
}

(I’ve changed the signatures of rule_to_regex() and rule_set_to_regex() accordingly.)

This gets me a correct test result on the test that I’ve written for the example given in Part 2 of the puzzle description. So I try it on the real input, and that gives me the correct answer. Apparently four is enough.

Afterword

Day 18 was only not tricky because of a few circumstances that coincided:

  • I had seen similar problems before, and knew what sort of tools I needed to solve it, before I tried to write any code.
  • I had been primed with the idea of using the PEG package by the blog posts that I’d read.
  • There was an example in the PEG documentation consisting of almost exactly what I needed to solve the puzzle.

If any of these three had not applied, I’m sure it would have taken me much longer to do, as Day 19 did.

Part 2 of Day 19, with the a{n}b{n} regex, is the first time during this series where I’ve been held back by not having a computer science degree — it seems likely to me that this is something I’d have learned in school. Nonetheless, I did manage to compensate the gap in my knowledge enough to solve the puzzle, just by reading Stack Overflow.4 This is why Stack Overflow is such a great resource.

It doesn’t sit well with me that there are a few instances of the borrow operator here that I just don’t understand why they are needed.

Lastly, now that I’ve gotten a bit more awareness of what I know and don’t know about Rust, going back and reading how an experienced Rust programmer solved the first few days’ puzzles was incredibly helpful. Perhaps the most helpful thing of all that I learned there, is the workflow of writing a function, writing tests for that function right below it, and running cargo test until they pass.


[1] My hunch was that the Box wouldn’t be necessary because the Vec‘s size is known without it, and indeed the compiler accepted it

[2] As we are indeed trying to achieve here?

[3] Or even more likely, try increasing numbers until one works

[4] I literally googled “regex match ab aabb aaabbb” and landed on that Stack Overflow post as the first result, isn’t it wild that this is possible?

Advent of Rust 16 and 17: Really, That’s More Iterators Than I Wanted; and More Adventures With NumRust

The last couple of days I took a break from this chronicle of my attempt to teach myself the Rust programming language by solving the programming puzzles on Advent of Code 2020. But now I’m back with another two days’ worth of puzzles!

One thing that I read in the meantime, thanks to a tip from Federico was the first installment of someone else’s blog who’s doing the same thing as I am. That blog is a really good read, and I think the main difference with my series is that the author is already a Rust expert! The style is also very different, as well; I am mostly trying to emphasize the things that I found surprising, struggled with, or didn’t understand. Their blog is much more didactic.1

One really cool thing that I picked up from that blog post is the include_str!() macro, which makes it possible to read the input file into a string at compile time, and dispense with the read_lines() boilerplate and most of the error handling. I think I will be using this from now on. This way also makes it easy to substitute in the example inputs from the puzzle descriptions.

Also in the meantime, I spent a lot of time trying to configure either of the Rust Enhanced or SublimeLinter-contrib-rustc plugins for my Sublime Text editor. I had a surprisingly hard time with this, neither of them seemed to work. In the latter case it was because the plugin was out of sync with the API of the newest version of SublimeLinter. I thought the former plugin, Rust Enhanced, would be a smooth experience since it claims to be the officially sanctioned Rust plugin for Sublime Text, but it didn’t work either! Whenever I would try to run any of the Rust commands, I would get this message:

Blocking waiting for file lock on build directory

I finally figured out that this error goes away if you run cargo clean. My guess, it’s probably because I copied the puzzle15 folder to puzzle16 today, instead of creating it with cargo new! My bad!

The editor plugin makes development much smoother, since I can get the compiler’s answer directly when I save the file, without even leaving my editor. This makes the endless rounds of compile, add a &, compile, add a *, go much faster.

It is mildly annoying that the plugin shows the compiler messages inline, instead of in the editor gutter like all the SublimeLinter plugins do. One day when I have time, I’ll investigate to see if there is a setting that controls this.

On to the puzzle.

Day 16, Part 1

This puzzle is about train tickets. We get a more free-form input file than usual, and we have to use it to deduce the meanings of fields on train tickets that we’ve scanned. In the input file there is a list of valid ranges for each field, and lists of fields on train tickets. Some of the train tickets are invalid, and that’s what Part 1 of the puzzle is about. The answer is the sum of all the values on any ticket that are not valid no matter what field they belong to.

I start by thinking about what data structure I would use to store the ranges. Some of them are overlapping and it would be nice to be able to collapse those. I google “rust collapse range” and land in the intervallum package, where the IntervalSet type seems like exactly what I want for this. It can collapse two intervals into a single interval set which covers the two intervals, and it is allowed to have one or more holes in the middle. So I can collapse all the valid ranges together, and then check each ticket field value to see if it is contained within the any of the valid ranges.

Here’s the program that I write. I split the input into three blocks, and process the first one (the one with the valid ranges in it.)

extern crate gcollections;
extern crate interval;
#[macro_use]
extern crate scan_fmt;

use gcollections::ops::set::Union;
use interval::interval_set::ToIntervalSet;

fn main() {
    let input = "class: 1-3 or 5-7\n\
row: 6-11 or 33-44\n\
seat: 13-40 or 45-50\n\
\n\
your ticket:\n\
7,1,14\n\
\n\
nearby tickets:\n\
7,3,47\n\
40,4,50\n\
55,2,20\n\
38,6,12\n";
    // let input = include_str!("input");
    let mut blocks = input.split("\n\n");

    let mut constraints = vec![].to_interval_set();
    blocks
        .next()
        .unwrap()
        .lines()
        .map(|line| {
            let mut parts = line.split(": ");
            (parts.next().unwrap(), parts.next().unwrap())
        })
        .flat_map(|(_, intervals)| intervals.split(" or "))
        .map(|interval| {
            scan_fmt!(interval, "{d}-{d}", u16, u16)
                .unwrap()
                .to_interval_set()
        })
        .for_each(|interval| constraints = constraints.union(&interval));
    println!("{}", constraints);

    let my_ticket_block = blocks.next().unwrap();
    assert!(my_ticket_block.starts_with("your ticket:\n"));

    let other_tickets_block = blocks.next().unwrap();
    assert!(other_tickets_block.starts_with("nearby tickets:\n"));
}

I initially thought .collect::<Vec<(u16, u16)>>().to_interval_set() would work, but that gives me a panic: “This operation is only for pushing interval to the back of the array, possibly overlapping with the last element.” so apparently we have to use union() on each item. Having a bit of experience with Rust and its reputation for safety, I’d expect it to return a Result or something if you tried this, instead of crashing. This seems consistent with my impression that some Rust packages are high quality and others are a bit rough around the edges, similar to NPM packages. This one seems a bit rough and underdocumented, but good enough that we can still use it.

To use the union() method, I inexplicably have to include the gcollections package as well.

Once that’s done I can process the third block as well, and calculate the answer with one long iterator chain:

let other_tickets_block = blocks.next().unwrap();
assert!(other_tickets_block.starts_with("nearby tickets:\n"));
let error_rate: u16 = other_tickets_block
    .lines()
    .skip(1)
    .flat_map(|line| line.split(','))
    .map(|s| s.parse().unwrap())
    .filter(|val| !constraints.contains(val))
    .sum();

println!("Error rate: {}", error_rate);

Day 16, Part 2

In Part 2 of the puzzle we have to discard all the tickets that had an invalid value, and with the remaining tickets figure out which field belongs to which field name, by comparing the fields with the valid ranges for each field name. The answer is the product of all the values on our own ticket that correspond to fields whose name starts with “departure”.

A lot of the logic will be the same as in Part 1, so I start by rewriting Part 1 to save the intermediate steps that we’ll need for Part 2 as well:

let mut blocks = input.split("\n\n");

let constraints_block = blocks.next().unwrap();
let field_descriptions: HashMap<&str, interval::interval_set::IntervalSet<u16>> =
    constraints_block
        .lines()
        .map(|line| {
            let mut parts = line.split(": ");
            let field_name = parts.next().unwrap();
            let intervals = parts.next().unwrap();
            let interval_set = intervals
                .split(" or ")
                .map(|interval| scan_fmt!(interval, "{d}-{d}", u16, u16).unwrap())
                .collect::<Vec<(u16, u16)>>()
                .to_interval_set();
            (field_name, interval_set)
        })
        .collect();

let mut all_valid_values = vec![].to_interval_set();
for interval in field_descriptions.values() {
    all_valid_values = all_valid_values.union(interval);
}

let my_ticket_block = blocks.next().unwrap();
assert!(my_ticket_block.starts_with("your ticket:\n"));

let other_tickets_block = blocks.next().unwrap();
assert!(other_tickets_block.starts_with("nearby tickets:\n"));
let (valid_tickets, invalid_tickets): (Vec<Vec<u16>>, Vec<Vec<u16>>) = other_tickets_block
    .lines()
    .skip(1)
    .map(|line| {
        line.split(',')
            .map(|s| s.parse().unwrap())
            .collect::<Vec<u16>>()
    })
    .partition(|ticket| ticket.iter().all(|val| all_valid_values.contains(val)));

if is_part2() {
} else {
    let error_rate: u16 = invalid_tickets
        .iter()
        .flat_map(|ticket| ticket.iter().filter(|val| !all_valid_values.contains(val)))
        .sum();
    println!("Error rate: {}", error_rate);
}

I am excited to use the partition() method, that I found by browsing the documentation, to split the iterator into two vectors, one of valid and one of invalid tickets.

I now have vectors of the numbers from each ticket. However, to solve this puzzle I’ll have to transform those into vectors of all the numbers in each position on the tickets (for example, a vector of all numbers coming first on each ticket, coming second, etc.) instead of vectors of each ticket. This sounds like something I should be able to do with a zip() method which I’m familiar with from Python.

Rust’s zip() takes only two iterators. At first I think that itertools::multizip will solve my problem, but that takes a number of iterators that must be known at compile time, which is not the case here. After some more googling I find this Stack Overflow answer and find a code snippet which I simply copy as-is into my program. I don’t really understand it, but I understand enough to see approximately what it does.

I decide to store the possible fields for each position on the ticket as a vector of hashsets, possible_fields_by_position. The order of the vector is by position of the number on the ticket. The elements of the vector are hash sets consisting of zero or more field numbers, which the numbers in this position might be valid for.

To do this, I have to pre-fill the vector with empty hashsets, and I’m not sure how to do this. Googling “rust fill vector of hashset” sends me here.

If the problem is solvable, then there will be at least one element of the vector where the hash set has only one item in it, and then we will know what field corresponds with that position on the ticket. We can then consider that field “determined” and remove it from all the other hash sets in the vector, which hopefully leaves at least one more hash set with only one item, allowing is to uniquely determine another field, and so on.

One interesting thing to note is that I first had this:

for (_, remaining_fields) in possible_fields_by_position {
    remaining_fields.remove(field_ix);
}

Here, for the first time that I’ve seen, the compiler gives a plain wrong suggestion:

error[E0382]: borrow of moved value: `possible_fields_by_position`
   --> puzzle16.rs:97:15
    |
78  |         let mut possible_fields_by_position: Vec<(usize, HashSet<usize>)> = (0..valid_tickets[0]
    |             ------------------------------- move occurs because `possible_fields_by_position` has type `Vec<(usize, std::collections::HashSet<usize>)>`, which does not implement the `Copy` trait
...
97  |         while possible_fields_by_position.len() > 0 {
    |               ^^^^^^^^^^^^^^^^^^^^^^^^^^^ value borrowed here after move
...
102 |             for (_, remaining_fields) in possible_fields_by_position {
    |                                          ---------------------------
    |                                          |
    |                                          value moved here, in previous iteration of loop
    |                                          help: consider borrowing to avoid moving into the for loop: `&possible_fields_by_position`

error[E0596]: cannot borrow `remaining_fields` as mutable, as it is not declared as mutable
   --> puzzle16.rs:103:17
    |
102 |             for (_, remaining_fields) in possible_fields_by_position {
    |                     ---------------- help: consider changing this to be mutable: `mut remaining_fields`
103 |                 remaining_fields.remove(field_ix);
    |                 ^^^^^^^^^^^^^^^^ cannot borrow as mutable

Even without the above, I certainly had more trouble than usual with getting the & operators right! Maybe it’s time for a re-read of the chapter on ownership in the Rust book.

For the last step I am also left wondering how to pre-fill a vector with zeros. The syntax is [0; number_of_zeros]. I do actually stumble upon a Github issue complaining about it not being documented well enough.

Here is the very long full program:

extern crate gcollections;
extern crate interval;
#[macro_use]
extern crate scan_fmt;

use gcollections::ops::set::{Contains, Union};
use interval::interval_set::{IntervalSet, ToIntervalSet};
use std::collections::HashSet;
use std::env;

// https://stackoverflow.com/a/55292215/172999
struct Multizip<T>(Vec<T>);

impl<T> Iterator for Multizip<T>
where
    T: Iterator,
{
    type Item = Vec<T::Item>;

    fn next(&mut self) -> Option<Self::Item> {
        self.0.iter_mut().map(Iterator::next).collect()
    }
}

fn main() {
    let input = include_str!("input");
    let mut blocks = input.split("\n\n");

    let constraints_block = blocks.next().unwrap();
    let field_descriptions: Vec<(&str, IntervalSet<u16>)> = constraints_block
        .lines()
        .map(|line| {
            let mut parts = line.split(": ");
            let field_name = parts.next().unwrap();
            let interval_set = parts
                .next()
                .unwrap()
                .split(" or ")
                .map(|interval| scan_fmt!(interval, "{d}-{d}", u16, u16).unwrap())
                .collect::<Vec<(u16, u16)>>()
                .to_interval_set();
            (field_name, interval_set)
        })
        .collect();

    let mut all_valid_values = vec![].to_interval_set();
    for (_, interval) in &field_descriptions {
        all_valid_values = all_valid_values.union(interval);
    }

    let my_ticket_block = blocks.next().unwrap();
    assert!(my_ticket_block.starts_with("your ticket:\n"));

    let other_tickets_block = blocks.next().unwrap();
    assert!(other_tickets_block.starts_with("nearby tickets:\n"));
    let (valid_tickets, invalid_tickets): (Vec<Vec<u16>>, Vec<Vec<u16>>) = other_tickets_block
        .lines()
        .skip(1)
        .map(read_csv_numbers)
        .partition(|ticket| ticket.iter().all(|val| all_valid_values.contains(val)));

    if is_part2() {
        let mut possible_fields_by_position: Vec<_> = (0..valid_tickets[0].len())
            .map(|_| HashSet::new())
            .enumerate()
            .collect();
        for (position, position_values) in
            Multizip(valid_tickets.iter().map(|ticket| ticket.iter()).collect()).enumerate()
        {
            for (field_ix, (_, interval)) in field_descriptions.iter().enumerate() {
                if position_values.iter().all(|val| interval.contains(val)) {
                    possible_fields_by_position[position].1.insert(field_ix);
                }
            }
        }

        possible_fields_by_position.sort_by_key(|(_, set)| set.len());
        possible_fields_by_position.reverse();

        let mut determined_fields_by_position = vec![0; possible_fields_by_position.len()];
        while !possible_fields_by_position.is_empty() {
            let (position, possible_fields) = possible_fields_by_position.pop().unwrap();
            assert!(possible_fields.len() == 1, "unable to determine fields");
            let field_ix = possible_fields.iter().next().unwrap();
            determined_fields_by_position[position] = *field_ix;
            for (_, remaining_fields) in &mut possible_fields_by_position {
                remaining_fields.remove(field_ix);
            }
        }

        let my_ticket_values: Vec<u16> = my_ticket_block
            .lines()
            .skip(1)
            .flat_map(read_csv_numbers)
            .collect();

        let answer: u64 = determined_fields_by_position
            .iter()
            .map(|field_ix| field_descriptions[*field_ix].0)
            .zip(my_ticket_values.iter())
            .filter(|(field_name, _)| field_name.starts_with("departure"))
            .map(|(_, value)| *value as u64)
            .product();

        println!("My ticket values {:?}", answer);
    } else {
        let error_rate: u16 = invalid_tickets
            .iter()
            .flat_map(|ticket| ticket.iter().filter(|val| !all_valid_values.contains(val)))
            .sum();
        println!("Error rate: {}", error_rate);
    }
}

fn read_csv_numbers(line: &str) -> Vec<u16> {
    line.split(',').map(|s| s.parse().unwrap()).collect()
}

Day 17, Part 1

I didn’t manage to finish the Day 16 blog post before I started working on Day 17’s puzzle, so I’m tacking it on here. Day 17 brings us a three-dimensional Conway’s Game of Life!

I remember very well implementing Game of Life with a different twist on Day 11, so today I will write some more code using ndarray, copying from Day 11 where I can.

In three dimensions we have 33 − 1 = 26 neighbours instead of the 32 − 1 = 8 that we have in two dimensions. I “hand-unrolled”2 the loop over the 8 neighbours in the calc_neighbours() function from Day 11:

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
}

That will simply not do when we have 26 neighbours! I decide to first rewrite it in the Day 11 code with the outer product of two vectors [-1, 0, 1] and make sure that it still gives the same answer. I find that the cartesian_product() method from Itertools is ideal for this:

fn calc_neighbours(seats: &Array2<i8>) -> Array2<i8> {
    let shape = seats.shape();
    let width = shape[0] as isize;
    let height = shape[1] as isize;
    let mut neighbours = Array2::<i8>::zeros(seats.raw_dim());
    // Add slices of the occupied seats shifted one space in each direction
    for (xstart, ystart) in (-1..=1).cartesian_product(-1..=1) {
        if xstart == 0 && ystart == 0 {
            continue;
        }
        let xdest = xstart.max(0)..(width + xstart).min(width);
        let ydest = ystart.max(0)..(height + ystart).min(height);
        let xsource = (-xstart).max(0)..(width - xstart).min(width);
        let ysource = (-ystart).max(0)..(height - ystart).min(height);
        let mut slice = neighbours.slice_mut(s![xdest, ydest]);
        slice += &seats.slice(s![xsource, ysource]);
    }
    neighbours
}

It’s still pretty verbose, and I suspect it could be done more cleverly, but this is good enough to be straightforwardly adapted to three dimensions for Day 17:

fn calc_neighbours(grid: &Array3<i8>) -> Array3<i8> {
    let shape = grid.shape();
    let width = shape[0] as isize;
    let height = shape[1] as isize;
    let depth = shape[2] as isize;
    let mut neighbours = Array3::<i8>::zeros(grid.raw_dim());
    // Add slices of the occupied grid shifted one space in each direction
    for starts in iter::repeat(-1..=1).take(3).multi_cartesian_product() {
        if starts.iter().all(|start| *start == 0) {
            continue;
        }
        let (xstart, ystart, zstart) = (starts[0], starts[1], starts[2]);
        let xdest = xstart.max(0)..(width + xstart).min(width);
        let ydest = ystart.max(0)..(height + ystart).min(height);
        let zdest = zstart.max(0)..(depth + zstart).min(depth);
        let xsource = (-xstart).max(0)..(width - xstart).min(width);
        let ysource = (-ystart).max(0)..(height - ystart).min(height);
        let zsource = (-zstart).max(0)..(depth - zstart).min(depth);
        let mut slice = neighbours.slice_mut(s![xdest, ydest, zdest]);
        slice += &grid.slice(s![xsource, ysource, zsource]);
    }
    neighbours
}

Unlike on Day 11, the game board is infinite and has no walls. However, also unlike on Day 11 where we had a termination condition for the game, today we have to simulate exactly 6 iterations of the game, so we can actually pretend the board is finite. The occupied cells can expand at by 1 every turn at most, so the board can be bounded at the size of the input board plus the number of iterations in every direction.

In the example given in the puzzle description, the board is 3×3×1 and we simulate 3 iterations, so the maximum board size would be 9×9×7 in the example. (The example’s actual output fits in 7×7×5, but we need an upper bound.)

I’m able to reuse a lot of the code from Day 11, so this should look very familiar if you’ve been following along:

use itertools::Itertools;
use ndarray::{s, Array3};
use std::iter;

fn main() {
    // let input = ".#.\n..#\n###\n";
    let input = include_str!("input");
    let n_turns = 6;
    let mut grid = read_grid(input, n_turns);

    for _ in 0..n_turns {
        let neighbours = calc_neighbours(&grid);
        let activations = &neighbours.mapv(|count| (count == 3) as i16)
            * &grid.mapv(|active| (active == 0) as i16);
        let deactivations = &neighbours.mapv(|count| (count < 2 || count > 3) as i16) * &grid;
        grid = grid + activations - deactivations;
    }

    dump_grid(&grid);
    println!("{}", grid.sum());
}

fn calc_neighbours(grid: &Array3<i16>) -> Array3<i16> {
    let shape = grid.shape();
    let width = shape[0] as isize;
    let height = shape[1] as isize;
    let depth = shape[2] as isize;
    let mut neighbours = Array3::<i16>::zeros(grid.raw_dim());
    // Add slices of the occupied grid shifted one space in each direction
    for starts in iter::repeat(-1..=1).take(3).multi_cartesian_product() {
        if starts.iter().all(|start| *start == 0) {
            continue;
        }
        let (xstart, ystart, zstart) = (starts[0], starts[1], starts[2]);
        let xdest = xstart.max(0)..(width + xstart).min(width);
        let ydest = ystart.max(0)..(height + ystart).min(height);
        let zdest = zstart.max(0)..(depth + zstart).min(depth);
        let xsource = (-xstart).max(0)..(width - xstart).min(width);
        let ysource = (-ystart).max(0)..(height - ystart).min(height);
        let zsource = (-zstart).max(0)..(depth - zstart).min(depth);
        let mut slice = neighbours.slice_mut(s![xdest, ydest, zdest]);
        slice += &grid.slice(s![xsource, ysource, zsource]);
    }
    neighbours
}

fn read_grid(input: &str, padding: usize) -> Array3<i16> {
    let lines: Vec<&str> = input.lines().collect();
    let height = lines.len();
    let width = lines[0].len();
    let mut cells = Array3::zeros((width + 2 * padding, height + 2 * padding, 2 * padding + 1));
    for (y, line) in lines.iter().enumerate() {
        for (x, tile) in line.bytes().enumerate() {
            cells[[x + padding, y + padding, padding]] = match tile {
                b'#' => 1,
                b'.' => 0,
                _ => panic!("Bad tile '{}'", tile),
            };
        }
    }
    cells
}

fn dump_grid(grid: &Array3<i16>) {
    for xy in grid.axis_iter(ndarray::Axis(2)) {
        for x in xy.axis_iter(ndarray::Axis(1)) {
            println!(
                "{}",
                x.mapv(|active| if active != 0 { '#' } else { '.' })
                    .iter()
                    .collect::<String>()
            )
        }
        println!("");
    }
}

The main difference is that I’ve written a dump_grid() function as well.

I remarked on Day 11 that in my opinion the ndarray package suffers from a few deficiencies compared to NumPy, and I ran into those same problems today:

  • The return value of sum() is limited to the data type of the array it is being called on.
  • You can’t easily use boolean arrays as a mask.

Day 17, Part 2

Part 2 of the puzzle is exactly the same as Part 1, only four-dimensional! I briefly wish that I had spent the time on generalizing calc_neighbours() to work with any number of dimensions. But on the other hand, I really don’t feel confident enough with either Rust or ndarray that I could anticipate being able to do that without spending all day on it.

So instead I decide to do the simplest thing: copy the file to another puzzle17-2.rs and add another section to Cargo.toml:

[[bin]]
name = "puzzle17-2"
path = "puzzle17-2.rs"

I notice that you now need to specify which binary to run, which is nice, because I wasn’t sure how I would choose between the two:

error: `cargo run` could not determine which binary to run. Use the `--bin` option to specify a binary, or the `default-run` manifest key.
available binaries: puzzle17, puzzle17-2

Then I just change all the Array3 to Array4 and add an extra index where needed:

use itertools::Itertools;
use ndarray::{s, Array4};
use std::iter;

fn main() {
    let input = include_str!("input");
    let n_turns = 6;
    let mut grid = read_grid(input, n_turns);

    for _ in 0..n_turns {
        let neighbours = calc_neighbours(&grid);
        let activations = &neighbours.mapv(|count| (count == 3) as i16)
            * &grid.mapv(|active| (active == 0) as i16);
        let deactivations = &neighbours.mapv(|count| (count < 2 || count > 3) as i16) * &grid;
        grid = grid + activations - deactivations;
    }

    println!("{}", grid.sum());
}

fn calc_neighbours(grid: &Array4<i16>) -> Array4<i16> {
    let shape = grid.shape();
    let width = shape[0] as isize;
    let height = shape[1] as isize;
    let depth = shape[2] as isize;
    let limit4 = shape[3] as isize;
    let mut neighbours = Array4::<i16>::zeros(grid.raw_dim());
    // Add slices of the occupied grid shifted one space in each direction
    for starts in iter::repeat(-1..=1).take(4).multi_cartesian_product() {
        if starts.iter().all(|start| *start == 0) {
            continue;
        }
        let (xstart, ystart, zstart, wstart) = (starts[0], starts[1], starts[2], starts[3]);
        let xdest = xstart.max(0)..(width + xstart).min(width);
        let ydest = ystart.max(0)..(height + ystart).min(height);
        let zdest = zstart.max(0)..(depth + zstart).min(depth);
        let wdest = wstart.max(0)..(limit4 + wstart).min(limit4);
        let xsource = (-xstart).max(0)..(width - xstart).min(width);
        let ysource = (-ystart).max(0)..(height - ystart).min(height);
        let zsource = (-zstart).max(0)..(depth - zstart).min(depth);
        let wsource = (-wstart).max(0)..(limit4 - wstart).min(limit4);
        let mut slice = neighbours.slice_mut(s![xdest, ydest, zdest, wdest]);
        slice += &grid.slice(s![xsource, ysource, zsource, wsource]);
    }
    neighbours
}

fn read_grid(input: &str, padding: usize) -> Array4<i16> {
    let lines: Vec<&str> = input.lines().collect();
    let height = lines.len();
    let width = lines[0].len();
    let mut cells = Array4::zeros((
        width + 2 * padding,
        height + 2 * padding,
        2 * padding + 1,
        2 * padding + 1,
    ));
    for (y, line) in lines.iter().enumerate() {
        for (x, tile) in line.bytes().enumerate() {
            cells[[x + padding, y + padding, padding, padding]] = match tile {
                b'#' => 1,
                b'.' => 0,
                _ => panic!("Bad tile '{}'", tile),
            };
        }
    }
    cells
}

This gives me the right answer.

Afterword

The puzzles seem to be getting harder as we go along, particularly Day 16 more than Day 17. I am almost certain that Day 16 could be solved much more elegantly than the solution that I had. Day 17, on the other hand, gave me a chance to improve on the solution that I already had for Day 11.

Having the compiler messages directly in my editor is a mixed blessing! It’s definitely streamlined things, but on the other hand I think it has actually made me more lazy and less inclined to learn about when the & operator is necessary — I’ve caught myself just adding them here and there in likely places without bothering to think, and letting the compiler sort the rest out. I’m definitely not this careless with pointers in C!


[1] And therefore probably more useful if you actually want to learn Rust yourself

[2] Or more like, the loop was never rolled in the first place because it was too complicated for me to write at the time

Advent of Rust 14 and 15: Bits And/Or Pieces

This blog: chronicling my adventure of teaching myself the Rust programming language since December 1, courtesy of the programming puzzles at Advent of Code 2020. I’m not sure if anyone is reading anymore at this point 😆

Day 14, Part 1

Today’s puzzle is once again simulating some computer instructions, although the model this time is simple enough that I don’t feel I have to write a struct with methods to simulate it.

We have to write values into memory addresses, with a bitmask: XX1100XX (left to right, most significant to least significant, which I’ll refer to as bit 7 through 0) means that bits 7 and 6 of the value to be written are left unchanged, bits 5 and 4 are overwritten with 0, bits 3 and 2 are overwritten with 1, and bits 1 and 0 are also left unchanged. The answer to the puzzle is the sum of all the values in memory.

Contrary to what people might expect about programmers, I have not memorized how to set a bit to 0 or 1 in a number, so I always look it up to make sure I’m doing it correctly, before I do it. To set a bit to 0, use the bitwise AND operator (& in most languages) with an integer consisting of all bits 1 except the bit you want to set to 0; and to set a bit to 1, use the bitwise OR operator (| in most languages) with the bit that you want to set to 1. Based on this, I decide to write a function to parse the bitmask string, and it will split the bitmask into two bitmasks: an AND-mask to set bits to 0, and an OR-mask to set them to 1. So in the example I gave above, the AND-mask would be 11110011 and the OR-mask would be 00110000.

To read the other lines in the file I’ll use my old friend scan_fmt!(). Finally, to emulate the memory, I’ll use a HashMap<u64, u64>. Naively emulating it in an array that spans the entire 236-word address space would be a bit big (288 GiB). I do quickly look up “rust sparse array” but don’t find anything that seems more compelling than a hash map.

While writing the program I do need to look up “rust exponentiation” and find that numbers have a pow() method. But I do get an error:

error[E0689]: can't call method `pow` on ambiguous numeric type `{integer}`
  --> puzzle14.rs:38:35
   |
38 |             b'0' => and_mask -= 2.pow(ix),
   |                                   ^^^
   |
help: you must specify a concrete type for this numeric value, like `i32`
   |
38 |             b'0' => and_mask -= 2_i32.pow(ix),
   |                                 ^^^^^

That syntax (2_i32) is new to me, I haven’t seen it (or seen it suggested by the compiler) before.

error[E0308]: mismatched types
  --> puzzle14.rs:38:43
   |
38 |             b'0' => and_mask -= 2_u64.pow(ix),
   |                                           ^^ expected `u32`, found `usize`
   |
help: you can convert an `usize` to `u32` and panic if the converted value wouldn't fit
   |
38 |             b'0' => and_mask -= 2_u64.pow(ix.try_into().unwrap()),
   |                                           ^^^^^^^^^^^^^^^^^^^^^^

This I’m also surprised at, why does u64::pow() take u32 specifically and not u64 or usize?

error[E0599]: no method named `try_into` found for type `usize` in the current scope
  --> puzzle14.rs:41:45
   |
41 |             b'1' => or_mask += 2_u64.pow(ix.try_into()?),
   |                                             ^^^^^^^^ method not found in `usize`
   |
   = help: items from traits can only be used if the trait is in scope
help: the following trait is implemented but not in scope; perhaps add a `use` for it:
   |
1  | use std::convert::TryInto;
   |

It would be nice if the compiler would suggest that when suggesting try_into() in the first place!

Otherwise, writing the solution to Part 1 goes smoothly:1

use std::collections::HashMap;
use std::convert::TryInto;
use std::num;

#[macro_use]
extern crate scan_fmt;

fn main() -> Result<(), Box<dyn Error>> {
    let mut memory = HashMap::new();
    let mut or_mask: u64 = 0;
    let mut and_mask: u64 = u64::MAX;

    let file = fs::File::open("input")?;
    for line in read_lines(file) {
        if line.starts_with("mask") {
            let (new_or_mask, new_and_mask) = parse_mask(&line[7..])?;
            or_mask = new_or_mask;
            and_mask = new_and_mask;
            continue;
        }
        let (addr, value) = scan_fmt!(&line, "mem[{}] = {}", u64, u64)?;
        memory.insert(addr, value & and_mask | or_mask);
    }

    println!("{}", memory.values().sum::<u64>());

    Ok(())
}

fn parse_mask(line: &str) -> Result<(u64, u64), num::TryFromIntError> {
    let mut or_mask: u64 = 0;
    let mut and_mask: u64 = u64::MAX;

    for (ix, byte) in line.bytes().rev().enumerate() {
        match byte {
            b'0' => and_mask -= 2_u64.pow(ix.try_into()?),
            b'1' => or_mask += 2_u64.pow(ix.try_into()?),
            b'X' => (),
            _ => panic!("Bad byte {}", byte),
        }
    }
    Ok((or_mask, and_mask))
}

I’m slightly surprised at a few of these type annotations:

  • memory has type HashMap<u64, u64>, so memory.values() has type Iterator<Item = u64>, so memory.values().sum() should unambiguously be u64?
  • and_mask and or_mask have type u64, so if I add or subtract 2ix then that could be assumed to be u64 as well?

Day 14, Part 2

In Part 2, the meaning of the bitmask changes. Now it applies to the address being written to, not the value being written. A zero in the mask now has no effect on the value, so we ignore the AND-mask; a one in the mask means the same thing as in Part 1, so we continue to use the OR-mask; and now the Xs mean that that bit in the mask is “floating”, meaning that we have to write the value to both of the memory addresses in which that bit is either 0 or 1. (And if we have two Xs in the mask, then we have to write to four memory addresses, etc.)

Nonetheless, the program can almost remain the same! First I change parse_mask() to return a third mask as well, the float_mask, which has 1s in the bits that are supposed to be floating:

fn parse_mask(line: &str) -> Result<(u64, u64, u64), num::TryFromIntError> {
    let mut or_mask: u64 = 0;
    let mut and_mask: u64 = u64::MAX;
    let mut float_mask: u64 = 0;

    for (ix, byte) in line.bytes().rev().enumerate() {
        let bit = 2_u64.pow(ix.try_into()?);
        match byte {
            b'0' => and_mask -= bit,
            b'1' => or_mask += bit,
            b'X' => float_mask += bit,
            _ => panic!("Bad byte {}", byte),
        }
    }
    Ok((or_mask, and_mask, float_mask))
}

I change the memory.insert(addr, value & and_mask | or_mask); line to instead do write_floating_memory(&mut memory, addr | or_mask, value, float_mask); if we are in Part 2.

The write_floating_memory() function is a bit more involved. I do know that we have to write the value to 2n addresses, where n is the number of 1-bits in the float mask, so I know I can iterate through the values from 0 to 2n − 1 and use each bit of each of those values in place of one of the floating bits. But I struggle somewhat with getting those bits into the right place.

I try a few things and then I realize that I can use the iterated value as a vector of bits, where I can pop bits off the end after I’ve used them, with the right shift operator (>>). So that’s what I write:

fn write_floating_memory(memory: &mut HashMap<u64, u64>, addr: u64, value: u64, float_mask: u64) {
    for mut floating_bits in 0..2_u64.pow(float_mask.count_ones()) {
        let mut masked_addr = addr;
        for bit_ix in 0..36 {
            let bit = 2_u64.pow(bit_ix);
            if float_mask & bit != 0 {
                match floating_bits & 1 {
                    0 => masked_addr &= !bit,
                    1 => masked_addr |= bit,
                    _ => panic!("Not possible"),
                };
                floating_bits >>= 1;
            }
        }
        memory.insert(masked_addr, value);
    }
}

There’s probably a more efficient way to do that by using bit-manipulation operators, but doing that intuitively is not my strong suit, and I’d rather not have to think hard about it when I can just solve the puzzle this way.

I initially get the wrong answer from the example input because I forgot to ignore the AND-mask (I had addr & and_mask | or_mask.) While debugging this, I learn the {:b} and {:036b} formats for println!(), which are useful for printing out the masks.

Once that is solved, though, I get the right answer for the example input, and then for the real puzzle.

Instead of “Not possible” it seems like it would be useful to have bit pattern matching in the match expression. I’m not the only one to have suggested this and I find the bitmatch package, but I don’t bother changing anything at this point now that I’ve got the answer.

Day 15, Part 1

I happened to solve the Day 15 puzzle within about 20 minutes after it was released, so I’m tacking it on to today’s entry.

The puzzle is a counting game played by the elves at the North Pole. Each person takes a turn reading off a list of starting numbers, and once the starting numbers are done, the game begins. The next player considers whether the last player’s number had been spoken before. If not, they say 0. If so, they say the number of turns between the previous time the number was spoken, and the last turn number. The puzzle answer is the number that’s spoken on turn 2020.

A few considerations that I made when writing the program below:

  • This time we don’t even have to read the input from a file, it’s given in the puzzle, so I delete read_lines() from the boilerplate.
  • I originally think I have to store the last two occurrences of the given number, and shift them along when the number occurs again, but the last occurrence is actually always the previous turn. I only have to store the second-to-last occurrence, and insert the previous turn’s number after the calculation for this turn.
  • I use 0-based turn numbers internally, but 1-based when printing them out. “Turn 2020” is a human-readable 1-based number, so it’s actually turn 2019 internally.
  • The number spoken after the starting numbers are done is always 0, because the starting numbers each occur for the first time.
fn main() {
    let input = vec![15, 12, 0, 14, 3, 1];
    let mut last_seen: HashMap<u16, u16> = input
        .iter()
        .enumerate()
        .map(|(turn, starting_number)| (*starting_number, turn as u16))
        .collect();
    let mut last_turn_number = 0;

    for turn in (input.len() as u16 + 1)..2020 {
        let this_turn_number = match last_seen.get(&last_turn_number) {
            Some(prev_seen) => turn - 1 - prev_seen,
            None => 0,
        };
        last_seen.insert(last_turn_number, turn - 1);
        last_turn_number = this_turn_number;

        println!("Turn {}: {}", turn + 1, this_turn_number);
    }
}

Day 15, Part 2

The answer to Part 2 is the number that is spoken on turn 30 million. I figure this will take an inconvenient amount of time to calculate, but not so inconvenient that I don’t want to try a brute force solution. I change the types of the integers to usize everywhere, to accommodate the larger numbers, and add an if expression, and that’s it, really. It takes a few minutes to run, but it’s done.

fn main() {
    let input = vec![15, 12, 0, 14, 3, 1];
    let mut last_seen: HashMap<usize, usize> = input
        .iter()
        .enumerate()
        .map(|(turn, starting_number)| (*starting_number, turn))
        .collect();
    let mut last_turn_number = 0;

    for turn in (input.len() + 1)..if is_part2() { 30000000 } else { 2020 } {
        let this_turn_number = match last_seen.get(&last_turn_number) {
            Some(prev_seen) => turn - 1 - prev_seen,
            None => 0,
        };
        last_seen.insert(last_turn_number, turn - 1);
        last_turn_number = this_turn_number;

        println!("Turn {}: {}", turn + 1, this_turn_number);
    }
}

Afterword

After Day 14 I was going to say that it seems like the puzzles follow a general pattern of having Part 1 be a fairly straightforward problem, and Part 2 adding a complication that makes you have to think harder about it. But Day 15 breaks that mold!


[1] For certain definitions of “smoothly,” that is. I’ve gotten used to always having a few rounds of compilation where I fix the borrow operators, and any program that I post here should be understood to have been bashed into shape by the compiler — I still can’t write Rust

Advent of Rust 13: Lucky Numbers

It’s time for the 13th installment of the chronicle of me doing programming puzzles from Advent of Code 2020 to teach myself the Rust programming language.

Looking at the lessons that I learned from previous days, today I resolve to be more systematic about debugging. If I get the wrong answer I will try my program on the example input first, before changing up a bunch of other things.

Day 13, Part 1

Today’s puzzle is about which bus to take from the airport. We get an input file consisting of only two lines of text: our arrival time at the airport, and a list of bus line numbers that are in service, with some xs denoting bus lines that are not in service. Each bus line departs from the airport at an interval of minutes equal to its number, so bus 77 departs when time % 77 == 0.

Since there are only two lines of text in the input file, and they both mean something different, I’m not looping over read_lines() today. To read the arrival time, I would really like to do this:

let arrival: u32 = lines.next()?.parse()?;

But, just as on Day 8, I can’t figure out how to get these dang error types to line up, without a lot of boilerplate (for example, implement From for every library error that I intend to handle, as I did and regretted on Day 8.) In my mind at least, this really ought to work:

fn main() -> Result<(), impl error::Error>

But I already tried that on Day 8 and it didn’t work, giving me errors such as:

error[E0277]: `?` couldn't convert the error to `impl std::error::Error`
 --> puzzle13.rs:7:39
  |
6 | fn main() -> Result<(), impl Error> {
  |              ---------------------- expected `impl std::error::Error` because of this
7 |     let file = fs::File::open("input")?;
  |                                       ^ the trait `From<std::io::Error>` is not implemented for `impl std::error::Error`
  |
  = note: the question mark operation (`?`) implicitly performs a conversion on the error value using the `From` trait
  = note: required by `from`

error[E0277]: `?` couldn't convert the error to `impl std::error::Error`
 --> puzzle13.rs:9:36
  |
6 | fn main() -> Result<(), impl Error> {
  |              ---------------------- expected `impl std::error::Error` because of this
...
9 |     let arrival: u64 = lines.next()?.parse()?;
  |                                    ^ the trait `From<NoneError>` is not implemented for `impl std::error::Error`
  |
  = note: the question mark operation (`?`) implicitly performs a conversion on the error value using the `From` trait
  = note: required by `from`
help: consider converting the `Option<T>` into a `Result<T, _>` using `Option::ok_or` or `Option::ok_or_else`
  |
9 |     let arrival: u64 = lines.next().ok_or_else(|| /* error value */)?.parse()?;
  |                                    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

error[E0277]: `?` couldn't convert the error to `impl std::error::Error`
 --> puzzle13.rs:9:45
  |
6 | fn main() -> Result<(), impl Error> {
  |              ---------------------- expected `impl std::error::Error` because of this
...
9 |     let arrival: u64 = lines.next()?.parse()?;
  |                                             ^ the trait `From<ParseIntError>` is not implemented for `impl std::error::Error`
  |
  = note: the question mark operation (`?`) implicitly performs a conversion on the error value using the `From` trait
  = note: required by `from`

error[E0720]: cannot resolve opaque type
  --> puzzle13.rs:6:25
   |
6  | fn main() -> Result<(), impl Error> {
   |                         ^^^^^^^^^^ recursive opaque type
7  |     let file = fs::File::open("input")?;
   |                                       - returning here with type `std::result::Result<(), impl std::error::Error>`
8  |     let mut lines = read_lines(file);
9  |     let arrival: u64 = lines.next()?.parse()?;
   |                                    -        - returning here with type `std::result::Result<(), impl std::error::Error>`
   |                                    |
   |                                    returning here with type `std::result::Result<(), impl std::error::Error>`
...
51 |     Ok(())
   |     ------ returning here with type `std::result::Result<(), impl std::error::Error>`

As far as I can tell, the first three error messages mean I’d need to implement the From trait on each of those errors, and I don’t understand the final error message.

Since I wish so badly that I could do this, I spend a bit more time searching, and find this. It’s not quite relevant to me, although I do learn some interesting facts about the Termination trait and why we can have different return types for main(). But I do see Box<Error> in some example code there, which I try instead of impl Error. The compiler tells me to use Box<dyn Error> instead. That actually works for the io::Error and ParseIntError, but I still have to unwrap() the Option from Iterator::next() — that doesn’t automatically convert into an Error.

I read about NoneError which is an experimental API, so maybe that will be possible in the future?

Anyway, I’m pleased at least that I can now use ? on Result types that carry different error types, so it’s progress, even though what I was hoping for is not (yet) possible. I guess -> Result<(), Box<dyn Error>> will become my new idiom.

Back to the puzzle! Here’s the program that I write:

use std::error::Error;

fn main() -> Result<(), Box<dyn Error>> {
    let file = fs::File::open("input")?;
    let mut lines = read_lines(file);
    let arrival: u32 = lines.next().unwrap().parse()?;

    let (bus_number, wait_time) = lines
        .next()
        .unwrap()
        .split(',')
        .filter_map(|s| s.parse::<u32>().ok()) // available bus lines
        .map(|interval| (interval, interval - arrival % interval)) // (bus_number, wait time)
        .min_by_key(|(_, wait_time)| *wait_time)
        .unwrap();

    println!("{}", bus_number * wait_time);
    Ok(())
}

I write this without any major complications, and it gives the correct answer. I learn the filter_map() and min_by_key() iterator methods along the way.

This input had so few entries that it may well have been faster to calculate it by hand, though! But then again, it’s basically a one-liner with these fantastic Iterator methods, and I didn’t even need Itertools this time.

Day 13, Part 2

The second part of the puzzle is to find a time that satisfies a number of constraints. Given the example input 17,x,13,19, you have to find a time t at which bus 17 departs, bus 13 departs 2 minutes later, and bus 19 departs 3 minutes later. (The x means there are no restrictions on what buses might depart one minute after t.) Additionally, the puzzle description gives the hint that t is at least 100000000000000, so I start by changing the integer types in my program to u64 because that won’t fit in a u32.

I first decide to try a brute force solution, because as I learned on Day 10, I might spend a lot of time dissecting the puzzle when I just could have written a program to do it without trying to be clever.

Writing my program, I’m a bit surprised about this:

error: literal out of range for `i32`
  --> puzzle13.rs:15:17
   |
15 |         let t = 100000000000000;
   |                 ^^^^^^^^^^^^^^^
   |
   = note: `#[deny(overflowing_literals)]` on by default
   = note: the literal `100000000000000` does not fit into the type `i32` whose range is `-2147483648..=2147483647`

Why can’t the compiler infer that t is used later in other expressions of type u64, or at least guess a default type for t that’s big enough to fit the literal, or at the very least suggest adding a type annotation?

Here’s the brute force program that I write:

let mut t: u64 = 100000000000000;
let mut constraints: Vec<(usize, u64)> = entries
    .enumerate()
    .filter_map(|(ix, s)| s.parse::<u64>().map(|n| (ix, n)).ok()) // (index, bus_number)
    .collect();
constraints.sort_unstable_by_key(|(_, bus_number)| *bus_number);
constraints.reverse();

loop {
    if constraints
        .iter()
        .all(|(ix, bus)| t + *ix as u64 % *bus == 0)
    {
        break;
    }
    t += 1;
}

println!("{}", t);

Many minutes later, after a coffee break, it’s still running! Clearly this will not do.

While the program is running for so long I do decide to check if it works on the example input, to carry out my resolution from the beginning of the day. In fact, the example input does not give the correct result. I am missing parentheses in (t + *ix as u64) % *bus. With the missing parentheses added, all the example inputs on the puzzle page do produce the correct answer. But given the real input, the program still runs for many minutes without finding an answer.

Taking the example input 17,x,13,19 again, we have a system where we have to determine t from the following equations, where cn are positive integers:

t = 17 × c1
t + 2 = 13 × c2
t + 3 = 19 × c3

Here we have a system with 3 equations and 4 unknowns, so we cannot solve it directly,1 because there is more than one solution. There is also the constraint that t must be the smallest possible solution that’s greater than 0 (or, greater than 100000000000000 with the real input), which fixes our solution unambiguously.

Put more generally, we have a system of equations of the form

t + bn = an × cn

where an and bn are given.

The lowest common multiple is a special case of this system where all bn = 0. Interesting that it’s so easy to calculate the lowest common multiple and not easy to calculate this!

My partner points out that all the an in the puzzle input are prime, and that there would be no answer to the puzzle if, for example, all the an were even and any of the bn were odd.

I try to speed the program up by not bothering to check numbers that I know won’t satisfy the first constraint. I set the starting number to the first number which satisfies the first constraint, skip checking the first constraint, and use a step size of the first bus line number instead of 1:

let (first_delay, first_bus) = &constraints[0];
t += (*first_bus - t % *first_bus);
t -= *first_delay as u64;
loop {
    println!("trying {}", t);
    if constraints
        .iter()
        .skip(1)
        .all(|(delay, bus)| {
            println!("  {} + {} % {} == {}", t, *delay, *bus, (t + *delay as u64) % *bus);
            (t + *delay as u64) % *bus == 0
        })
    {
        break;
    }
    t += first_bus;
}

This speeds up the calculation of the example inputs noticeably, but the calculation of the actual puzzle answer is still taking a long time.

I try running it again on the example input 17,x,13,19 and looking at the debug output to see if there are patterns. In the case of the program above, this means: the step is 19, the constraints are [(3, 19), (0, 17), (2, 13)], and the first constraint is always satisfied. I notice that the iterations that satisfy the second constraint are always 17 steps apart. This suggests to me that once I find a number that satisfies the second constraint, I can continue with a step of 19 × 17 = 323 until I find a number that satisfies the third constraint as well. In fact, this is generalizable to include the speedup that I just wrote: I can start with a step of 1, iterate until I satisfy the first constraint, multiply the step by 19 (giving 19), iterate until I satisfy the second constraint, multiply the step by 17 (giving 323), and then iterate until I satisfy the third constraint, at which point I have the answer.

After a few false starts, I manage to write the following loop:

let mut step = 1;
let mut constraints_satisfied = 0;
loop {
    match constraints
        .iter()
        .position(|(delay, bus)| (t + *delay as u64) % *bus != 0)
    {
        None => break,
        Some(ix) => {
            if ix > constraints_satisfied {
                constraints_satisfied += 1;
                step *= constraints[ix - 1].1;
            }
        }
    }
    t += step;
}

The position() method is a new thing that I’ve learned while doing this, I found it by googling “rust find index” because I was doing something like constraints.iter().enumerate().find(...) and taking the position from there. (Maybe cargo clippy should look for this pattern.)

This gives the correct output on all the example inputs, and finds the correct answer to the puzzle in a very short time. The full code is on the repository.

Afterword

Today I actually found the opposite of what I found a few days ago: writing the brute force program first was not actually that helpful, and I did have to sit down and think a lot more about the problem, and explore the input, before I was able to get the answer.

I suspect it’s still worth it to write the brute force program first when doing programming puzzles, though. It’s only not helpful in a case like this, where brute force calculation is really not feasible.


[1] It doesn’t matter that we don’t actually care about the values of cn; they are still unknowns

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