Advent of Code - Year 2015, Day 09
Problem statement: http://adventofcode.com/2015/day/9
This problem statement is a very fancy way of asking us to solve the Traveling Salesman Problem. It is very easy in concept: Find the path through every city that has the shortest distance. The problem is that it is computationally hard. There are N! (1 * 2 * 3 * ... * N) ways to visit every city, and so small numbers of cities (only 8 cities here) are feasible (40,320 potential paths), but even 10 cities is exponentially harder (3,628,800 potential paths).
I won't go into ways to reduce the difficulty of the problem, because for only eight cities these improvements were not necessary. Both my C# and F# solutions used basic brute-force to evaluate every path, and were able to solve compute the solution in under 1 second, so further techniques would not be beneficial.
The only difference between Part A and Part B is that the paths were ordered by longest path instead of by shortest path.
I copied the
permute function from online, and it took me some time before I understood how it actually worked. The
distribute function has a goal of distributing the value
e into each possible position of the input list, which is matched with either
x::xs. If the list matches
, then it is empty, and the return value is
[[e]], which is a list of one element, which is a list which contains one element,
If the input list has elements, then it matches
x::xs', which says to split the list into two variables, the first element of the list (
x), and all of the remaining elements of the list (
xs'). For example, if the input list was
[ 2; 3 ], then
x would be
xs' would be
[ 3 ].
as xs then means I want a reference to the whole list as well.
If we match this item, then we want to return a new list. The first element will be
e::xs, that is to say
e followed by all of the elements in
1 and the input array again is
[ 2; 3 ], then
e::xs will return
[ 1; 2; 3 ].
Then we join this list as the first item in a list of lists, then remaining items in the list being defined as
[for xs in distribute e xs' -> x::xs]. The first part of this to execute is
distribute e xs'; we're going to pass every element except the first as the array input to a recursive call to
distribute, passing in
e as well. Specifically, given the arguments presented already, we are calling
distribute 1 [ 3 ]. This will ostensibly return
[ [ 1; 3 ]; [ 3; 1 ] ], distributing 1 into each possible position of the list
. Then we're going to do a
foreach over the outer list, renaming
xs to be each of the inner lists, and we're going to map them to return each inner list with
2) prefixed to them. The net effect of everything inside the
[ [ 2; 1; 3 ]; [ 2; 3; 1 ] ]. Then the list calculated at the beginning (
[1; 2; 3]) gets prefixed as the first item in the outer list.
A complicated process, but ultimately simple syntax, to distribute
1 to every possible element in
[ 2; 3 ].
permute simply kicks off this process with every element in the input list, so that you get a list of every possible permutation of the input list.
Once we have an understanding of how to generate a list of permutations, the concept for solving this problem is fairly straight forward. We permute the list of cities, which is effectively every possible path through every city, collect the distance between each pair of cities, calculate the sum of the distances as the path length, and sort the paths by the total distance. The remaining techniques used here have been used in other problems thus far.
I'll admit to having written this code two years ago, and since it worked and isn't too horrible, I only made minor modifications. I copied the
Permutation code from an online source. A quick read of the code shows that it does effectively the same thing as the F#
permute function, albeit with far more syntax.
The solution is functionally the same as the F# solution, and nothing should be new in this code.