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.
The Mad Scientist Review 