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/solvingtransporttycoon2episode21withf.
The task is to find the shortest route between two stations given a dataset of connections. See https://github.com/trustbit/exercises/blob/master/transporttycoon_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/transporttycoon/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 reusing 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 reuse 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 treerelated 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
totryFindShortestRoute
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/shortestroutekata/blob/main/Brownbag01/kataloop22.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: