This advent of code challenge got us tackling a classic problem: the Travelling Salesman Problem, or in this case, the Travelling Santa Problem. It’s a notoriously hard algorithm to crack, and you pretty much have to try out every possible path to find the shortest route through all the locations.

For C# I used the Permutations method from a pre-release version of MoreLINQ, and for F# I cheated by finding a nice permutations algorithm on Stack Overflow. I did have an attempt at optimizing the performance of my F# as well, but not sure how effective it was.

Here’s my C# code:

``````var path = Path.GetDirectoryName(Util.CurrentQueryPath);
var realInput = File.ReadAllLines(Path.Combine(path, "day9.txt"));

var distances = realInput
.Select(s => Regex.Match(s, @"^(\w+) to (\w+) = (\d+)").Groups)
.Select(g => new { From = g.Value, To = g.Value, Distance = int.Parse(g.Value) })
.ToList();

var places = distances.SelectMany(d => new[] { d.From, d.To }).Distinct().ToList();

Func<string,string,int> getDistance = (a,b) => distances
.FirstOrDefault(d => (d.From == a && d.To == b) ||
(d.To == a && d.From == b)).Distance;
// brute force it
var routeLengths = places.Permutations()
.Select(route => route.Pairwise((from, to) => getDistance(from, to)).Sum());

routeLengths.Min().Dump("a"); // 207
routeLengths.Max().Dump("b"); // 804
``````

Here’s my first F# attempt:

``````let path = Path.Combine(Path.GetDirectoryName(Util.CurrentQueryPath),"day9.txt")
let realInput = path |> File.ReadAllLines |> Seq.toList

let (=~) input pattern =
Regex.Match(input, pattern).Groups.Cast<Group>()
|> Seq.skip 1
|> Seq.map (fun g -> g.Value)
|> Seq.toArray

let parseInput (i:string) =
seq {
let [| a; b; dist |] = i =~ @"^(\w+) to (\w+) = (\d+)"
yield ((a,b),int dist)
yield ((b,a),int dist) }

let distances =
realInput
|> Seq.collect parseInput
|> dict

let getDistance key =
distances.[key]

let places =
distances.Keys
|> Seq.map (fun (a,b) -> a)
|> Seq.distinct
|> Seq.toList

// Jon Harrop F# for Scientists ( http://stackoverflow.com/a/3129136/7532
let rec distribute e = function
| [] -> [[e]]
| x::xs' as xs -> (e::xs)::[for xs in distribute e xs' -> x::xs]

let rec permute = function
| [] -> [[]]
| e::xs -> List.collect (distribute e) (permute xs)

let getRouteLength route =
route
|> Seq.pairwise
|> Seq.map getDistance //(fun (a,b) -> getDistance a b)
|> Seq.sum

let routeLengths =
places
|> permute
|> List.map getRouteLength

routeLengths
|> Seq.min
|> printfn "a: %d" // 207

routeLengths
|> Seq.max
|> printfn "b: %d" // 804
``````

And here’s an attempt at optimizing the performance in F# by abandoning long routes early. It also has the benefit of actually tracking what the shortest route is:

``````type route = {
path : string list
distance : int
}

let realInput = "day9.txt" |> File.ReadAllLines |> Seq.toList

let (=~) input pattern =
Regex.Match(input, pattern).Groups.Cast<Group>()
|> Seq.skip 1
|> Seq.map (fun g -> g.Value)
|> Seq.toArray

let parseInput (i:string) =
seq {
let [| a; b; dist |] = i =~ @"^(\w+) to (\w+) = (\d+)"
yield ((a,b),int dist)
yield ((b,a),int dist) }

let distances =
realInput
|> Seq.collect parseInput
|> dict

let getDistance key =
distances.[key]

let places =
distances.Keys
|> Seq.map (fun (a,b) -> a)
|> Seq.distinct
|> Seq.toList

let getDistanceR currentRoute target =
match currentRoute.path with
| [] -> 0
| h::tail -> getDistance (h,target)

let shortest test best =
match best with
| None -> test
| Some route -> if test.distance < route.distance then test else route

let isShortestCandidate distance bestRoute =
match bestRoute with
| None -> true
| Some route -> distance < route.distance

let rec findRoute currentRoute toVisit (bestRoute:route option) =
let mutable br = bestRoute
//printfn "%A" currentRoute
for p in toVisit do
let distanceToP = getDistanceR currentRoute p
let stillToVisit = (toVisit |> List.filter (fun f-> f <> p))
let testRoute = { path = p::currentRoute.path; distance = currentRoute.distance + distanceToP }
if stillToVisit = [] then
// a complete route
br <- Some (shortest testRoute br)
elif isShortestCandidate (distanceToP + currentRoute.distance) br then
let bestChildRoute = findRoute testRoute stillToVisit br
match bestChildRoute with
| Some r -> br <- Some (shortest r br)
| None -> ()
br

findRoute { path = []; distance = 0 } places None
|> printfn "ROUTE: %A"
``````
Want to learn more about LINQ? Be sure to check out my Pluralsight course More Effective LINQ.