Advent of Code 2015 - Day 9: All in a Single Night

Part 1

Description

Every year, Santa manages to deliver all of his presents in a single night.
This year, however, he has some new locations to visit; his elves have provided him the distances between every pair of locations. He can start and end at any two (different) locations he wants, but he must visit each location exactly once. What is the shortest distance he can travel to achieve this?
For example, given the following distances:

London to Dublin = 464
London to Belfast = 518
Dublin to Belfast = 141

The possible routes are therefore:

Dublin -> London -> Belfast = 982
London -> Dublin -> Belfast = 605
London -> Belfast -> Dublin = 659
Dublin -> Belfast -> London = 659
Belfast -> Dublin -> London = 605
Belfast -> London -> Dublin = 982

The shortest of these is London -> Dublin -> Belfast = 605, and so the answer is 605 in this example.
What is the distance of the shortest route?

Input

Solution

This problem is also known as traveling salesman problem, with exception, that Santa doesn't go back to the starting point. I don't have any better solution than this. First, I paste and split the input.

Then, I put those numbers into a table. Because there are eight locations, I made an 8×8 table, pairing each of them.

As you can see, the table shows all the distance between those locations, marked with numbers 1-8. There are 8! (40320) possibilities of routes taken. Or precisely, there are just half of it, because the distance of route 1-2-3-4-5-6-7-8 is the same as route 8-7-6-5-4-3-2-1. So, I made a list of all possible permutation from these  numbers, like this:

Here is the way to do it. I went to a blank sheet and paste the following formula in A1.

= IF(ROW()<=FACT(COLUMN()-1),COLUMN(),
INDIRECT(ADDRESS(ROW()-FACT(SUMPRODUCT(((ROW()-1)>=FACT(ROW($A$2:$A$10)))+0)+1),
IF(COLUMN()=(SUMPRODUCT(((ROW()-1)>=FACT(ROW($A$2:$A$10)))+0)+2),1,COLUMN()+1))))

Then, by dragging the formula to 8 columns and 40320 rows, I get the permutation I need. Next, I put another formula in seven columns (Q-X), one for each distance between two adjacent places, and sum them up. The formula in Q13 is:

=INDEX($H$4:$O$11,H13,I13)

And, finally a formula to return the smallest value of the sum of the distances:

=SMALL(X13:X40332,1)

Part 2

Description

The next year, just to show off, Santa decides to take the route with the longest distance instead.
He can still start and end at any two (different) locations he wants, and he still must visit each location exactly once.
For example, given the distances above, the longest route would be 982 via (for example) Dublin -> London -> Belfast.
What is the distance of the longest route?

Solution

For the part 2, I just need to modify the formula to get the longest route.

=LARGE(X13:X40332,1)