Solving Transport Tycoon 2 Episode 2.1 With F#

by Ian Russel | Data Analyst/Architect/Developer

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 TIMETOACT blog.

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"
4/26/22
Blog 3/11/21

Introduction to Web Programming in F# with Giraffe – Part 2

In this series we are investigating web programming with Giraffe and the Giraffe View Engine plus a few other useful F# libraries.
Blog

Function Composition in F# with Unfriendly Functions

Explore how to handle unfriendly library functions in F# by using wrappers, higher-order functions, or inline solutions to keep pipelines clean and functional.
Blog

Using GCP Cloud Functions with F#

Learn how to build and test Google Cloud Functions in F#, using dependency injection, configuration, and pub/sub messaging for real-world cloud apps.
Blog 9/13/22

Introduction to Functional Programming in F# – Part 2

Explore functions, types, and modules in F#. Enhance your skills with practical examples and insights in this detailed guide.
Blog 11/14/23

Part 2: Data Analysis with powerful Python

Analyzing and visualizing data from a SQLite database in Python can be a powerful way to gain insights and present your findings. In Part 2 of this blog series, we will walk you through the steps to retrieve data from a SQLite database file named gold.db and display it in the form of a chart using Python. We'll use some essential tools and libraries for this task.
Referenz

Automated Planning of Transport Routes

Efficient transport route planning through automation and seamless integration.
Blog 3/10/21

Introduction to Web Programming in F# with Giraffe – Part 1

In this series we are investigating web programming with Giraffe and the Giraffe View Engine plus a few other useful F# libraries.
Blog 3/12/21

Introduction to Web Programming in F# with Giraffe – Part 3

In this series we are investigating web programming with Giraffe and the Giraffe View Engine plus a few other useful F# libraries.
Blog 8/7/20

Understanding F# Type Aliases

In this post, we discuss the difference between F# types and aliases that from a glance may appear to be the same thing.

Branche 9/5/25

Digital Pole Position for Transport and Logistics

We create transparency, automate processes and ensure compliance – for IT that puts your logistics in the lead.
Use Case

Use Case: Cantonal transport authority uses data smarter

Predictive analytics & visualisation: weather, crash & image data linked – for prevention, planning & safety.
Blog

Functional Validation in F# Using Applicatives

Learn how to implement functional validation in F# using applicatives. Handle multiple errors elegantly with Railway-Oriented Programming and concise functional patterns.
Blog 5/18/22

Introduction to Functional Programming in F#

Dive into functional programming with F# in our introductory series. Learn how to solve real business problems using F#'s functional programming features. This first part covers setting up your environment, basic F# syntax, and implementing a simple use case. Perfect for developers looking to enhance their skills in functional programming.
Blog 7/21/20

Understanding F# applicatives and custom operators

In this post, Jonathan Channon, a newcomer to F#, discusses how he learnt about a slightly more advanced functional concept — Applicatives.

Blog 11/30/22

Introduction to Partial Function Application in F#

Partial Function Application is one of the core functional programming concepts that everyone should understand as it is widely used in most F# codebases.In this post I will introduce you to the grace and power of partial application. We will start with tupled arguments that most devs will recognise and then move onto curried arguments that allow us to use partial application.

Leistung 9/22/20

Working with CLOUDPILOTS

With the perfect partner at your side, many things are easier and more efficient, although a direct relationship with the manufacturer is appealing at first glance. But only at first glance!
Blog

Digitization with security

Conditions of the German economy for the cloud: what companies in Germany expect from secure and sovereign cloud solutions
novaCapta: Ihr Partner für die digitale Transformation mit Microsoft Technologien
Service

Intranet with SharePoint

For many employees, the intranet is the door to collaboration and networking. Use the potential of Office 365 to take full advantage of the opportunities.
young business woman smiles it jobs timetoact group
Jobs

(Senior) Consultant SAP FI (f/m/d)

Walldorf Consulting | Walldorf | Full-time & Permanent employment | Available now
two colleagues working together it jobs timetoact group
Jobs

(Senior) Consultant SAP MM (f/m/d)

Walldorf Consulting | Walldorf | Full-time & Permanent employment | Available now

Bleiben Sie mit dem TIMETOACT GROUP Newsletter auf dem Laufenden!