A More Efficient Solution of the Shortest Route Kata

This post describes how I improved on my submission to the Trustbit Transport Tycoon 2 Episode 2.1 problem. The blog post showing how I arrived at the original solution can be found at https://trustbit.tech/blog/2022/4/26/solving-transport-tycoon-2-episode-21-with-f.

The task is to find the shortest route between two stations given a dataset of connections. See https://github.com/trustbit/exercises/blob/master/transport-tycoon_21.md for more details about the problem.

This category of exercise lends itself to using recursion. If you want to see alternate approaches in F# and some other languages (C#, python, and Swift), have a look at https://github.com/trustbit/exercises/blob/master/transport-tycoon/README.md.

Getting Started⌗

In the initial solution, I chose to tackle this problem with the following steps:

Load the data from the file
Determine all possible routes that we could choose from the start location to the finish location using the file data
Calculate the shortest route
Print the result

There is a video recording of me working through this task for a brown bag session but it hasn’t been released yet.

After the brown bag, I ended up with the following solution which uses a hierarchical discriminated union, which I named Tree<'T>, to determine the routes and store the route data:

open System.IO

type Tree<'T> =
    | Branch of 'T * Tree<'T> seq
    | Leaf of 'T

type Waypoint = {
    Location: string
    Route: string list
    TotalDistance: int
}

type Connection = {
    Start: string
    Finish: string
    Distance: int
}

let loadConnections path =
    path
    |> File.ReadAllLines
    |> Array.skip 1
    |> fun rows -> [
        for row in rows do
            match row.Split(",") with
            | [|start;finish;distance|] ->
                { Start = start; Finish = finish; Distance = int distance }
                { Start = finish; Finish = start; Distance = int distance }
            | _ -> failwith $"{row} is invalid"
    ]
    |> List.groupBy (fun cn -> cn.Start)
    |> Map.ofList

let rec getLeaves tree =
    match tree with
    | Leaf wp -> [wp]
    | Branch (_,xs) -> xs |> Seq.toList |> List.collect getLeaves

let findPossibleRoutes start finish (connections:Map<string,Connection list>) = 
    let rec processWaypoint waypoint =
        let unvisited =
            connections[waypoint.Location]
            |> List.filter (fun cn -> waypoint.Route |> List.exists (fun loc -> loc = cn.Finish) |> not)
            |> List.map (fun cn -> {
                Location = cn.Finish
                Route = cn.Start :: waypoint.Route
                TotalDistance = waypoint.TotalDistance + cn.Distance
            })
        if waypoint.Location = finish || unvisited = [] then
            Leaf waypoint
        else 
            Branch (waypoint, seq { for next in unvisited do processWaypoint next })
    processWaypoint { Location = start; Route = []; TotalDistance = 0 }
    |> getLeaves
    |> List.filter (fun wp -> wp.Location = finish)

let getShortestRoute start finish =
    Path.Combine(__SOURCE_DIRECTORY__, "resources", "data.csv")
    |> loadConnections // load connections
    |> findPossibleRoutes start finish // find possible routes
    |> List.minBy (fun wp -> wp.TotalDistance) // determine shortest
    |> fun wp -> wp.Location :: wp.Route |> List.rev, wp.TotalDistance // display result

getShortestRoute "Cogburg" "Leverstorm"

This takes an exhaustive approach that finds all of the possible routes from one location to another using the data from the source file and then finds the shortest from those. It is quite fast on a modern computer but we are doing work that is unnecessary.

Whilst the code is elegant and concise, it is not as efficient as it could be. With a small dataset, performance is not really an issue but that will rapidly change with a much larger source of data. When writing F# code, the general rule of thumb with F# is:

First, make it work, then make it pretty, and finally, if you need to, make it fast.

Thankfully, using the accumulated data approach will enable us to refactor this code into a more efficient solution by re-using much of what we’ve created.

Starting the Improvements⌗

The principle behind the improved solution is that, on average, the more steps in your journey, the longer it is likely to be. Once you have found one route that reaches the destination, you can filter out any routes that are already longer and just process the remaining routes in the next iteration.

We will be looking to re-use most of what we already have except the core algorithm which is useless as we no longer need a tree structure. The first task is to remove all tree-related code. I’ve added a minimal amount of code to make it compile. We are left with this:

open System.IO

type Waypoint = {
    Location: string
    Route: string list
    TotalDistance: int
}

type Connection = {
    Start: string
    Finish: string
    Distance: int
}

let loadConnections path =
    path
    |> File.ReadAllLines
    |> Array.skip 1
    |> fun rows -> [
        for row in rows do
            match row.Split(",") with
            | [|start;finish;distance|] ->
                { Start = start; Finish = finish; Distance = int distance }
                { Start = finish; Finish = start; Distance = int distance }
            | _ -> failwith $"{row} is invalid"
    ]
    |> List.groupBy (fun cn -> cn.Start)
    |> Map.ofList

let getUnvisited waypoint connections =
    connections
    |> List.filter (fun cn -> waypoint.Route |> List.exists (fun loc -> loc = cn.Finish) |> not)
    |> List.map (fun cn -> {
        Location = cn.Finish
        Route = cn.Start :: waypoint.Route
        TotalDistance = waypoint.TotalDistance + cn.Distance
    })

let tryFindShortestRoute start finish (connections:Map<string,Connection list>) = 
    let rec loop (routes:Waypoint list) (shortest:Waypoint option) =
        match routes with
        | [] -> shortest
        | _ -> loop [] shortest
    loop [{ Location = start; Route = []; TotalDistance = 0 }] None

let getShortestRoute start finish =
    Path.Combine(__SOURCE_DIRECTORY__, "resources", "data.csv")
    |> loadConnections // load connections
    |> tryFindShortestRoute start finish // find shortest route
    |> function
        | None -> failwith "No shortest route found"
        | Some wp -> wp.Location :: wp.Route |> List.rev, wp.TotalDistance // output data

getShortestRoute "Cogburg" "Leverstorm"

This code will compile but will not produce a meaningful result.

The changes I have made are:

I have moved the code for determining unvisited locations from the core function into its own function.
Changed findShortestRoute to tryFindShortestRoute as it returns an Option. It is unlikely but we could find a journey that is not possible.
We no longer need to filter for the shortest route since it is returned by tryFindShortestRoute.

Building the Algorithm⌗

We are still using a recursive function but it works on a list of Waypoints rather than a single Waypoint.

let tryFindShortestRoute start finish (connections:Map<string,Connection list>) = 
    let rec loop (routes:Waypoint list) (shortest:Waypoint option) =
        match routes with
        | [] -> shortest
        | _ -> loop [] shortest
    loop [{ Location = start; Route = []; TotalDistance = 0 }] None

The recursive function exits when the base case, when there are no more Waypoints to process, is met. In this case, we return the current shortest Waypoint.

The steps we are going to follow in our new algorithm are:

Get next routes and split into those that have reached their destination and those that haven’t
Find the shortest from the current iteration
Compare the current shortest with the one from the latest iteration
Filter out routes where the total distance is already greater than the shortest route
Repeat until no routes are left to process

Let’s add those steps into the tryFindShortestRoute function:

let tryFindShortestRoute start finish (connections:Map<string,Connection list>) = 
    let rec loop (routes:Waypoint list) (shortest:Waypoint option) =
        match routes with
        | [] -> shortest
        | _ -> 
            // get next routes and split into those that have reached destination and those that haven't
            // find shortest from current iteration
            // compare current shortest with the one from latest iteration
            // filter out routes where the total distance is already greater than shortest route
            loop [] shortest
    loop [{ Location = start; Route = []; TotalDistance = 0 }] None

Now we can start to implement the first step.

For each Waypoint passed in, we find their unvisited locations, concatenate the resulting lists into a single list, and finally, partition the data into two parts; those that have reached the destination and those that haven’t by using the list.partition function:

// get next routes and split into those that have reached destination and those that haven't
let (ended, potential) = 
    routes
    |> List.collect (fun current -> getUnvisited current connections[current.Location])
    |> List.partition (fun wp -> wp.Location = finish)

We now find try to find the shortest route from those Waypoints that have reached the destination in this iteration:

// find shortest from current iteration
let shortEnded = 
    match ended with
    | [] -> None
    | _ -> ended |> List.minBy (fun wp -> wp.TotalDistance) |> Some

Now we compare the shortest route that we passed in to the one that we have just found to determine the shortest overall:

// compare current shortest with the one from latest iteration
let currentShortest = 
    match shortest, shortEnded with
    | None, None -> None
    | None, Some se -> Some se
    | Some s, None -> Some s
    | Some s, Some se -> if s.TotalDistance < se.TotalDistance then Some s else Some se

We filter out all of the routes that are already longer than the current shortest route:

// filter out routes where the total distance is already greater than shortest route
let stillInPlay = 
    match currentShortest with
    | None -> potential
    | Some cs -> potential |> List.filter (fun wp -> wp.TotalDistance < cs.TotalDistance)

The final step required is to set the routes and shortest values for the next iteration:

// compare current shortest with the one from latest iteration
let currentShortest = 
    match shortest, shortEnded with
    | None, None -> None
    | None, Some se -> Some se
    | Some s, None -> Some s
    | Some s, Some se -> if s.TotalDistance < se.TotalDistance then Some s else Some se
// filter out routes where the total distance is already greater than shortest route
let stillInPlay = 
    match currentShortest with
    | None -> potential
    | Some cs -> potential |> List.filter (fun wp -> wp.TotalDistance < cs.TotalDistance)
loop stillInPlay currentShortest

That’s it for the algorithm. We finally end up with:

let tryFindShortestRoute start finish (connections:Map<string,Connection list>) =
    let rec loop (routes:Waypoint list) (shortest:Waypoint option) = 
        match routes with
        | [] -> shortest
        | _ -> 
            // get next routes and split into those that have reached destination and those that haven't
            let (ended, potential) = 
                routes
                |> List.collect (fun current -> getUnvisited current connections[current.Location])
                |> List.partition (fun wp -> wp.Location = finish)
            // find shortest from latest iteration
            let shortEnded = 
                match ended with
                | [] -> None
                | _ -> ended |> List.minBy (fun wp -> wp.TotalDistance) |> Some
            // compare current shortest with the one from latest iteration
            let currentShortest = 
                match shortest, shortEnded with
                | None, None -> None
                | None, Some se -> Some se
                | Some s, None -> Some s
                | Some s, Some se -> if s.TotalDistance < se.TotalDistance then Some s else Some se
            // filter out routes where the total distance is already greater than shortest route
            let stillInPlay = 
                match currentShortest with
                | None -> potential
                | Some cs -> potential |> List.filter (fun wp -> wp.TotalDistance < cs.TotalDistance)
            loop stillInPlay currentShortest
    loop [{ Location = start; Route = []; TotalDistance = 0 }] None

We should now run our code in FSI to find the shortest route between Cogburg and Leverstorm:

getShortestRoute "Cogburg" "Leverstorm"

We should see a result that states:

(["Cogburg"; "Copperhold"; "Leverstorm"], 1616)

There’s more code and it isn’t quite as elegant as before but it is potentially much more efficient.

Final Code⌗

This is the code we finished with after the performance improvements:

open System.IO

type Waypoint = {
    Location: string
    Route: string list
    TotalDistance: int
}

type Connection = {
    Start:string
    Finish: string
    Distance: int
}

let loadConnections path =
    path
    |> File.ReadAllLines
    |> Array.skip 1
    |> fun rows -> [
        for row in rows do
            match row.Split(",") with
            | [|start;finish;distance|] ->
                { Start = start; Finish = finish; Distance = int distance }
                { Start = finish; Finish = start; Distance = int distance }
            | _ -> failwith $"{row} is invalid"
    ]
    |> List.groupBy (fun cn -> cn.Start)
    |> Map.ofList

let getUnvisited current connections =
    connections
    |> List.filter (fun cn -> current.Route |> List.exists (fun loc -> loc = cn.Finish) |> not)
    |> List.map (fun cn -> {
        Location = cn.Finish
        Route = cn.Start :: current.Route
        TotalDistance = current.TotalDistance + cn.Distance
    })

let tryFindShortestRoute start finish (connections:Map<string,Connection list>) =
    let rec loop (routes:Waypoint list) (shortest:Waypoint option) = 
        match routes with
        | [] -> shortest
        | _ -> 
            // get next routes and split into those that have reached destination and those that haven't
            let (ended, potential) = 
                routes
                |> List.collect (fun current -> getUnvisited current connections[current.Location])
                |> List.partition (fun wp -> wp.Location = finish)
            // find shortest from latest iteration
            let shortEnded = 
                match ended with
                | [] -> None
                | _ -> ended |> List.minBy (fun wp -> wp.TotalDistance) |> Some
            // compare current shortest with the one from latest iteration
            let currentShortest = 
                match shortest, shortEnded with
                | None, None -> None
                | None, Some se -> Some se
                | Some s, None -> Some s
                | Some s, Some se -> if s.TotalDistance < se.TotalDistance then Some s else Some se
            // filter out routes where the total distance is already greater than shortest route
            let stillInPlay = 
                match currentShortest with
                | None -> potential
                | Some cs -> potential |> List.filter (fun wp -> wp.TotalDistance < cs.TotalDistance)
            loop stillInPlay currentShortest
    loop [{ Location = start; Route = []; TotalDistance = 0 }] None

let getShortestRoute start finish =
    Path.Combine(__SOURCE_DIRECTORY__, "resources", "data.csv")
    |> loadConnections // load connections
    |> tryFindShortestRoute start finish // find shortest route
    |> function
        | None -> failwith "No shortest route found"
        | Some wp -> wp.Location :: wp.Route |> List.rev, wp.TotalDistance // output data

getShortestRoute "Cogburg" "Leverstorm"

I also adapted this new code to Exercise 2.2 where we try to find the fastest route given distance and speed values in the CSV file. The code is available here:

https://github.com/ianrussellsoftwarepark/shortest-route-kata/blob/main/Brownbag01/kata-loop-2-2.fsx

Trustbit are intending to produce more tasks and katas like this in the future, so you might want to watch them on Github so that you don’t miss out.

And Finally⌗

If you like this post and want to learn more about F#, I’ve written a free ebook called Essential F# that you can download from:

https://leanpub.com/essential-fsharp