**Part 1:** Given a list of distances between cities of the form `London to Dublin = 464`

, calculate the shortest route that visits each city exactly once.

```
routes = collections.defaultdict(
lambda : collections.defaultdict(
lambda : float("inf")
)
)
for line in sys.stdin:
src, dst, dist = re.match(r'(\w+) to (\w+) = (\d+)', line).groups()
dist = int(dist)
routes[src][dst] = dist
routes[dst][src] = dist
best_length, best_ordering = min(
(sum(
routes[src][dst]
for src, dst in zip(ordering, ordering[1:])
), ordering)
for ordering in itertools.permutations(routes.keys())
)
print(best_length)
```

There are a few neat tricks here that I’ve used. First `routes`

is defined as nested `defaultdict`

, with an eventual default value of `float("inf")`

. This solves two problems:

- We don’t have to explicitly check if a station exists before adding a route to it:
`python routes[src][dst] = dist`

rather than`python if src in routes: routes[src][dst] = dist else: routes[src] = {dst: dist}`

- Any missing routes will have an infinite distance, which will work correctly with
`+`

and`min`

.

We add each distance to both `routes[src][dst]`

and `routes[dst][src]`

so that we don’t have to worry about ordering when we calculate full routes. The other way to do this would be to sort `src`

and `dst`

so that `src < dst`

is always true. I think this way is a little cleaner.

Next, we use a bunch of tools to calculate the shortest route.

First, `itertools.permutations`

will give us every possible ordering:

```
>>> pprint.pprint(list(itertools.permutations(routes.keys())))
[('London', 'Belfast', 'Dublin'),
('London', 'Dublin', 'Belfast'),
('Belfast', 'London', 'Dublin'),
('Belfast', 'Dublin', 'London'),
('Dublin', 'London', 'Belfast'),
('Dublin', 'Belfast', 'London')]
```

Next, `zip`

over `ordering`

and `ordering[1:]`

will give us the pairs of stations (since `zip`

after exhausting its shortest argument):

```
>>> ordering = ('Dublin', 'Belfast', 'London')
>>> pprint.pprint(list(zip(ordering, ordering[1:])))
[('Dublin', 'Belfast'), ('Belfast', 'London')]
```

Next, we can get the distance for each pairing and `sum`

them all up. This is where `float("inf")`

really comes in handy (although in this smaller example, we don’t need it):

```
>>> orderings = (routes[src][dst] for src, dst in zip(ordering, ordering[1:]))
>>> pprint.pprint(list(orderings))
[141, 518]
>>> pprint.pprint(sum(orderings))
659
```

That, we wrap up in a tuple of `(distance, ordering)`

so that they are sortable. Then, apply `min`

to that to find the route with the minimum distance and unpack the tuple again.

And that’s it. Minimum distance.

It’s certainly a brute force solution in that it will try every possible route to find the shortest one. There are probably a few dynamic programming tricks that could cut that down a bit. On the other hand, the input is relatively short (28 connections between 8 stations for a total of 40320 orderings), so just do them all.

**Part 2:** Find the longest route.

Just change `min`

to `max`

.

This wouldn’t work if there wasn’t a connection listed between every possible station (there is in my given input, since 8 stations will have `8*7/2 = 28`

connections). That’s solveable though. Just use `float("-inf")`

for the default distance, so that any routes with invalid stations will have an infinitely small distance.

This was a pretty cool problem again!