Expand description
§All in a Single Night
This is a variant of the classic NP-hard Travelling Salesman Problem.
There are 8 locations, so naively it would require checking 8! = 40,320 permutations. We can reduce this to 7!/2 = 2,520 permutations by arbitrarily choosing one of the locations as the start, and skipping lexically reversed permutations (since the path a->b->c has the same length as c->b->a).
We then compute the distance to complete the trip and return to the original location. Since the problem does not ask us to end up in the same location we then “break” the cycle. To compute the shortest journey we remove the longest single journey and to compute the longest journey we remove the shortest single journey.
For speed we first convert each location into an index, then store the distances between
every pair of locations in an array for fast lookup. Our utility half_permutations method uses
Steinhaus-Johnson-Trotter’s algorithm for efficiency,
modifying the slice in place.
Functions§
Type Aliases§
- Result 🔒