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.
Then we can use Held-Karp’s dynamic programming algorithm to determine the
shortest cycle. The problem asks us to start from node 0, which conveniently means that the
value g(127, k) is the shortest path to k, and adding the distance from k back to 0 for part 2
is also trivial. Thus, this day completes with only 7*6/2*128/2 or 1,344 comparisons, quite a
bit better than the 2,520 comparisons needed for an approach with 7!/2 permutations. A
slight complication is that set bit 0 maps to node 1.
Functions§
Type Aliases§
- Input 🔒