Module advent_of_code_2021::day_15

This is my solution for Advent of Code - Day 15 - Chiton

I picked up pretty quickly that this needed a shortest-path graph traversal algorithm, and (very) vaguely remembered Dijkstra’s from when it was covered in my A-Level math course. I did some googling to refresh my memory, noted the advice to use a BinaryHeap, found that the Rust std implementation had Dijkstra’s as it’s main example in the docs. I imported Grid from previous days, and updated the example code to work with co-ordinates, and it just worked: find_shortest_path.

For part two I didn’t want to store the much bigger and repeated graph in memory, so I wrote a wrapper ExpandedGrid that would provide implementations for all the methods used by find_shortest_path and work out how to translate that to methods on the underlying sub-grid, get methods being ExpandedGrid::pos_of and ExpandedGrid::get. The wrapper ended up a little messy, but it’ll do for AoC. If I was planning to need to maintain this code, I’d maybe look into extracting some parts to a trait so that I’m not repeating code from Grid.

Structs

Cell

This is juts copied from the example std::collections::BinaryHeap with position swapped for coords.

ExpandedGrid

A wrapper around Grid that handles tiling a smaller sub-grid.

Functions

find_shortest_path

Implement Dijkstra’s shortest path algorithm. Copied from BinaryHeap example and modified to get the edge costs from the provided grid. Originally accepted Grid but it was easier to use one type/method for both parts and the ExpandedGrid works the same as a Grid if it only has one tile on each axis.

run

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