DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»

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.

Create account Log in
Cover image for AoC 2015 - Day 9 - Travelling Salesman!
Jules
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:

Screenshot of Advent of Code puzzle

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)
Enter fullscreen mode Exit fullscreen mode

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
}
Enter fullscreen mode Exit fullscreen mode

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))
Enter fullscreen mode Exit fullscreen mode

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

Screenshot of Advent of Code puzzle

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))
Enter fullscreen mode Exit fullscreen mode

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:]))
Enter fullscreen mode Exit fullscreen mode

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).

Top comments (0)

Take a look at this:

Settings

Go to your customization settings to nudge your home feed to show content more relevant to your developer experience level. πŸ›