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 Combat¹, 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 ↩