Module mbryant_aoc2021::day15

Use Djikstra’s to traverse the grid, as there isn’t a good heuristic for A*.

All real work is done in day15::a_star.

The main difficulty was misreading the instructions and tiling incorrectly. Rust also doesn’t appear to have an efficient priority queue, so we emulate one with a std::collections::BTreeMap and Vec.

Constants

INPUT_DIM

The input map is 100x100.

Functions

a_star

Implement A* with a heuristic of 0, also known as Djikstra’s.

generator

Parse directly to a 2D array.

part1

Directly calls a_star on the input.

part2

Directly calls a_star on the input.

Type Definitions

Coord

We’re limited by memory here, so want the smallest datatypes we can use.

Cost

We’re limited by memory here, so want the smallest datatypes we can use.

Map

We knows the input will be in [0, 9].