Expand description
§Knights of the Dinner Table
This problem is very similar to Day 9 and we solve it in almost exactly the same way by
computing an adjacency matrix of happiness then running Held-Karp to find the longest
cycle. If part one were the only problem at hand, the answer would be possible by iterating
over 127 sets and then selecting among seven candidates to close the loop back to whichever
abritrary point we pinned as the start.
However, we are more interested in solving part two at the same time. Do this by noticing that when you insert yourself between two diners, you set the value of their mutual link to zero. This is effectively the same as inserting a ninth node into the algorithm, which we pin as the start node before iterating over 255 sets. Meanwhile, the results for part one can still be found from the table, if we also have an easy way to determine which diner was used to start the path represented by any given g(set,k). We can then manually close the loop of 8 diners by using all 8 g(255,k) plus the distance from k to the start node of that path, while the loop of 9 diners uses g(255,k) with no additional distance.
Functions§
Type Aliases§
- Input 🔒