# Advent of Code Day 9 Solved in C# and F#

- Posted in:
- Advent of Code
- C#
- F#
- LINQ

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[1].Value, To = g[2].Value, Distance = int.Parse(g[3].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"