Advent of Code, Day 9

This is a Travelling Salesman Problem with 8 cities, a small enough number to brute-force. The input is in the form

No prizes for the sources of the city names. Again, the parser framework gets used, and we build up both a list of cities and a hash of city distances. We then use an algorithm from Knuth to permute the list (lexicographically ordered, but it doesn’t really matter) and just go through it until we find the shortest path. Part 2 asks for the longest path, which is a simple enough matter. Here’s the code:

Copyright © Found
Jim Finnis' personal blog

Built on Notes Blog Core
Powered by WordPress