Module advent_of_code_2021::day_9

This is my solution for Advent of Code - Day 9 - Smoke Basin

Note: At the time of writing Grid was part of the Day 9 module. Parts that were reused for Day 11 have since been extracted into a utility module.

Today’s task was to find local minima (part one) of a grid of digits and the area within the watershed of those (part two). For this I built a type to represent a Grid and implemented a bunch of methods to build towards a solution. I’ve tried to lean more on the standard library and built in traits to accomplish some of this, specifically using impl From<String> for Grid for the initial parsing, and providing Grid::iter which returns a crate::util::grid::GridCoords which has an implementation for Iterator as a standard way to iterate all the cells in the grid.

I had to work at getting Grid::iter correct and my original code was implementing IntoIterator for Grid, and the iterator was contained the grid itself, which in turn was (because I was struggling with exactly where the lifetime constraints needed to go to satisfy the compiler. This meant I needed to clone the whole grid each time I wanted to iterate over it as the iterator took ownership of the grid it was created with. I eventually found an article on Iterators and Reference Lifetimes that explained how to get the lifetimes to work, and I got a small speed improvement now I wasn’t copying the grid all over the place.

To outline my solution, Grid is implemented as a one-dimensional list of numbers, that also has a record of the width of the grid to work out the correct offset in the list for a given x and y, implemented as Grid::get. Working the other way, Grid::get_with_coords is used by the iterator to work out the 2D co-ordinates of its current position. Grid::get_low_points filters the iterator of all points in the grid to just the local minima, this defers to Grid::is_lowest which in turn uses Grid::get_orthogonal_surrounds to check the current value against its four neighbours. Grid::get_risk_level takes the result of Grid::get_low_points and reduces it to the puzzle solution for part one.

To solve part two, Grid::get_basin uses Grid::get_orthogonal_surrounds, filtering to only larger numbers less than the watershed of 9 to recursively build a set of co-ordinates by walking uphill. Grid::get_largest_basin_sizes is a wrapper that calls Grid::get_basin for each low point, and the reduces the returned data into the puzzle solution.

Re-exports

pub use crate::util::grid::Grid;

Functions

run

The entry point for running the solutions with the ‘real’ puzzle input.