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

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"