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?