Expand description
§Air Duct Spelunking
This is a variant of the classic
Travelling Salesman Problem and
is similar to Year 2015 Day 13.
We first simplify the problem by finding the distance between all locations using multiple BFS searches starting from each location.
For speed we convert each location into an index, then store the distances between
every pair of locations in an vec for fast lookup. Our utility permutations method uses
Heap’s algorithm for efficiency,
modifying the slice in place.
There are 8 locations, however since we always start at 0 this requires checking only
7! = 5,040 permutations. We find the answer to both part one and two simultaneously.
Functions§
Type Aliases§
- Input 🔒