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:

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:

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:

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:

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

This data will get loaded when the code first runs.

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

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:

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:

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:

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:

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

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:

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:

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

Finally, add the following and run in FSI.

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

F#