## DEV Community π©βπ»π¨βπ» is a community of 963,274 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Jules

Posted on

# AoC 2015 - Day 9 - Travelling Salesman!

Day 9 is a loosely disguised Travelling Salesman puzzle. You can find out more about these on Wikipedia, but in short, what we're trying to do is calculate the shortest distance between a number of cities, visiting each one once. There doesn't seem to be an easy way to optimise this type of puzzle, so the code will really benefit from the `Itertools` library. Here's Part 1:

There are three cities in the example, but eight in the puzzle input. Each line looks a bit like this: `Faerun to Snowdin = 71` so it's fairly easy to unpack what we need (remember, we can throw away unwanted variables into `_`):

``````with open('src/day09.txt') as f:
for line in f:
t1, _, t2, _, dist = line.split()
distances[(t1, t2)] = int(dist)
distances[(t2, t1)] = int(dist)
towns.extend([t1, t2])
towns = set(towns)
``````

I am storing the distances twice to save time on lookups later, as I don't know which city in each pair I'll be visiting first. So, after processing `Faerun to Snowdin = 71`, I'll have the following in `distances{}`:

``````distances{
('Faerun', 'Snowdin'): 71,
('Snowdin', 'Faerun'): 71
}
``````

The final line takes all the town names we've captured in a list, and squishes them down to a set, which only allows unique items.

The next step is to use `itertools.permutations()` to give us every permutation of those eight towns (8! = 40,320 permutations in all). It's then a case of stepping through each pair of towns in the permutation, and storing the total once we've done it.

The answer to Part 1, after we've done that, is the smallest number in those calculated distances:

``````perms = list(permutations(towns))
route_lengths = []
for perm in perms:
route_length = 0
for town in range(len(perm)-1):
route_length += distances[(perm[town], perm[town+1])]
route_lengths.append(route_length)
print(min(route_lengths))
``````

I used a list instead of a counter for the distances, because who knows what's in Part 2?! And sure enough:

It's a lovely feeling when you have actually coded your solution in a way that makes Part 2 very easy, and this is just about the ultimate example:

``````print(max(route_lengths))
``````

And we're done! We've already calculated what we need, we just have to look it up...

I did see a bit of golfing in the megathread, such as this nice one-liner to sum the distances between the towns in each permutation:

``````route_length = sum(distances[(t1, t2)] for t1, t2 in zip(perm, perm[1:]))
``````

This made me want to look a bit more into the `zip()` function, but when I tried it in my code, it ran about ten times slower over all. This harks back to what I said on Day 1, one-liners are pretty clever, but not always the fastest, or easiest to read (i.e. maintain).