Solving Transport Tycoon 2 Episode 2.1 With F#

This post describes how I wrote my submission to the Transport Tycoon 2 Episode 2.1 problem. The task is to find the shortest route between two stations given a dataset of connections. See this link 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 this link.

Setting Up

Create a new folder for the code.

Add a file called 'code.fsx'.

Add a new directory called 'resources'.

Create a new file in the 'resources' folder called 'data.csv' and copy the following data into it:

A,B,km
Cogburg,Copperhold,1047
Leverstorm,Irondale,673
Cogburg,Steamdrift,1269
Copperhold,Irondale,345
Copperhold,Leverstorm,569
Leverstorm,Gizbourne,866
Rustport,Cogburg,1421
Rustport,Steamdrift,1947
Rustport,Gizbourne,1220
Irondale,Gizbourne,526
Cogburg,Irondale,1034
Rustport,Irondale,1302

Getting Started

We are going to tackle this problem with the following steps:

1. Load the data

2. Determine all possible routes from start to finish

3. Calculate the shortest route

4. Print the result

Defining the Types

The primary data structure we are going to use is called a Rose Tree. This structure can have different numbers of branches and leaf depth. Thankfully, this structure is easily represented in F# with a hierarchical discriminated union:

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

We use a sequence because it is lazily loaded.

We need two record types: Connection which will hold the data from the csv file and Waypoint that we will use in the tree structure:

type Waypoint = { Location:string; Route:string list; 
Distance:int }

type Connection = { From:string; To:string; 
Distance:int }

Load the data

Since we are going to use the Path class from the .NET CLR, we need to open a reference to System.IO at the top of the file:

open System.IO

After loading the data from the file, we split it into lines and skip the first one as it contains header information:

let lines = 
    Path.Combine(__SOURCE_DIRECTORY__, "resources", 
    "data.csv")
    |> File.ReadAllText
    |> fun data -> data.Split(System.Environment.NewLine)
    |> Array.skip 1

This data will get loaded when the code first runs.

Next, we need to convert each row into Connection records:

let readConnections (rows:array<string>) = [
    for row in rows do
        match row.Split(",") with
        | [|start; finish; distance|] -> 
            { From = start; To = finish; Distance = 
              int distance }
            { From = finish; To = start; Distance = 
              int distance }
        | _ -> ()
]

Notice that we have added code to include the reverse direction so that we can handle travel in any direction. The data gets populated into a list by the use of a list comprehension.

Find Potential Routes

If I have four locations (A, B, C, D) and can travel between any two, at any location, I could travel to three others. However, for this exercise, we need to ignore locations that we have already been to on this route. If we draw out the possible routes as a hierarchy, we get something like this:

A 
  - B 
      - C
          - D
      - D
  - C
      - B
          - D
      - D
  - D

All instances of location D are leaves, whilst all of the other locations are branches.

From any location, we need to ask where can we get to next that we haven't been so far on this route? The filter in this function does just that:

let getChildren connections wayPoint =
    connections
    |> List.filter (fun cn -> cn.From = 
       wayPoint.Location && wayPoint.Route |> 
       List.tryFind (fun loc -> loc = cn.To) = None)
    |> List.map (fun cn -> { Location = cn.To; Route = 
       cn.From :: wayPoint.Route; Distance = cn.Distance + wayPoint.Distance })

The mapping code produces a new Waypoint record for each route, prepends the previous location to the Route list, and adds the distance travelled to the previous value. We could easily not do the accumulation here but it does require more code later on because you need to access each part of the journey rather than only the last one.

Find All Routes From Start to Finish

To find the possible routes, we need to supply the start and finish locations. In addition, we will pass in a partially applied higher order function which consists of the getChildren function and the list of connections that we loaded in. We will re-use this to find the potential next locations for each part of each route.

Building the tree structure can be achieved quite concisely with a sprinkling of recursion:

let findRoutes getChildRoutes start finish =
    let rec createTree findChildRoutes destination 
    current =
        let childRoutes = findChildRoutes current
        if childRoutes |> List.isEmpty |> not && 
                       current.Location <> 
                       destination then
            Branch (current, seq { for next in 
            childRoutes do (createTree findChildRoutes 
            destination next) })
        else Leaf current
    createTree getChildRoutes finish { Location = start; 
    Route = []; Distance = 0}

Note the logic in the if expression that states that if a location has no unused connections or is the destination, you should create a leaf node.

We now need to flatten the tree down into a list structure. Again we will use a simple recursive function:

let rec treeToList tree =
    match tree with 
    | Leaf x -> [x]
    | Branch (x, xs) -> x :: (List.collect treeToList 
      (xs |> Seq.toList))

We then need to add this function to the findRoutes function:

let findRoutes getChildRoutes start finish =
  let rec createTree continuation destination current =
        let childRoutes = continuation current
        if childRoutes |> List.isEmpty |> not && 
        current.Location <> destination then
            Branch (current, seq { for next in 
            childRoutes do yield (createTree continuation 
            destination next) })
        else Leaf current
    createTree getChildRoutes finish { Location = start; 
    Route = []; Distance = 0}
    |> treeToList

We have now completed the code to get the available routes. Now it is time to find the shortest route from these.

Find Shortest Route

We are only interested in leaf nodes that have the waypoint location at the finish location. Finding the shortest is then trivial because we accumulated the distance as we traversed the routes:

let selectShortest finish routes =
    routes
    |> List.filter (fun wp -> wp.Location = finish)
    |> List.minBy (fun wp -> wp.Distance)
    |> fun wp -> wp.Location :: wp.Route |> List.rev, 
       wp.Distance

We have to append the finish location to the route and then reverse it to get the correct route order of locations.

Running the code

All that is left is to combine the parts and print out the result:

let run start finish =
    findRoutes (lines |> readConnections |> getChildren) 
    start finish
    |> selectShortest finish
    |> printfn "%A"

Highlight all of this code and run it in FSI by using ALT + ENTER.

Finally, add the following and run in FSI.

run "Cogburg" "Leverstorm"

You should see a tuple returned with the route and the distance.

Summary

This is probably not the most efficient way to solve this problem but it is at least logical and easy to follow. We haven't had to use any features of F# not covered in my Essential Functional-First F# ebook. It is amazing just how much you can do in F# with just the essentials!

I hope that you find this post useful. It is one of many F# posts on the Trustbit blog.

If you are interested in other approaches to this problem, have a look at https://github.com/trustbit/exercises/blob/master/transport-tycoon/README.md.

Addendum: Final Code

open System.IO

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

type Waypoint = { Location:string; Route:string list; 
Distance:int }

type Connection = { From:string; To:string; Distance:int }

let lines = 
    Path.Combine(__SOURCE_DIRECTORY__, "resources", 
    "data.csv")
    |> File.ReadAllText
    |> fun data -> data.Split(System.Environment.NewLine)
    |> Array.skip 1

let readConnections (rows:array<string>) = [
    for row in rows do
        match row.Split(",") with
        | [|start; finish; distance|] -> 
            { From = start; To = finish; Distance = 
              int distance }
            { From = finish; To = start; Distance = 
              int distance }
        | _ -> ()
]

let getChildren connections wayPoint =
    connections
    |> List.filter (fun cn -> cn.From = 
    wayPoint.Location && wayPoint.Route |> List.tryFind
    (fun loc -> loc = cn.To) = None)
    |> List.map (fun cn -> { Location = cn.To; Route 
    = cn.From :: wayPoint.Route; Distance = cn.Distance 
    + wayPoint.Distance })

let rec treeToList tree =
    match tree with 
    | Leaf x -> [x]
    | Branch (x, xs) -> x :: (List.collect treeToList 
    (xs |> Seq.toList))

let findRoutes getChildRoutes start finish =
    let rec createTree findChildRoutes destination 
    current =
        let childRoutes = findChildRoutes current
        if childRoutes |> List.isEmpty |> not && 
        current.Location <> destination then
            Branch (current, seq { for next in 
            childRoutes do yield (createTree continuation 
            destination next) })
        else Leaf current
    createTree getChildRoutes finish { Location = start; 
    Route = []; Distance = 0}
    |> treeToList

let selectShortest finish routes =
    routes
    |> List.filter (fun wp -> wp.Location = finish)
    |> List.minBy (fun wp -> wp.Distance)
    |> fun wp -> wp.Location :: wp.Route |> List.rev, 
    wp.Distance

let run start finish =
    findRoutes (lines |> readConnections |> getChildren) 
    start finish
    |> selectShortest finish
    |> printfn "%A"

run "Cogburg" "Leverstorm"

F#