Mark Gilbert's Blog

Science and technology, served light and fluffy.

Finding my way with F# – Part 2 of 3

In Part 1 of this series, I laid out the algorithm for finding the number of distinct paths from a given point in a city to another.  One of the three cities that were included with the problem as inputs allowed for cyclical routes, where you could bounce from one point to another infinitely.  In this part, I’ll look at the solution for cities where cyclical routes aren’t possible, and I’ll extend this solution in Part 3 to support cities where they are possible.

In my last post I mention that the algorithm that worked was actually #4.  The implementation of that algorithm proved to be even more difficult.  The solution presented here is actually my third attempt – the third time I started with a completely blank .fs code file.  My difficulties came down to learning how to work with sequences and lists in F#.

To get into the solution, let’s review the major pieces of the algorithm again:

  • Possible Routes (Round 1)
  • Possible Routes (Round 2)
  • Distinct Routes
  • Route Matrix

I’ll go through each of these in turn.

Possible Routes (Round 1)
To start things out, I needed a way to expand the city’s routes starting from every point, and follow the one-way streets until I came to a dead-end.  I recognized pretty early on that that would mean recursion within a loop.

One key piece to see here is that I use both “yield” and “yield!”.  Both are used to generate values to be included in a sequence – as far as I can tell, you can only use these within a seq{} structure.  The former, “yield” kicks out a single value while the latter, “yield!” kicks out a sequence of values.  By “kick out”, I mean the value or values are sent all the way up to the top-most seq{} structure, whether I’m one level deep in recursion, or 20.

The loop of this step is handled by the BuildRouteTree function:

let BuildRouteTree cityStreets =
    seq {
        // NOTE: If I say 
        //         for initialRoute:int list in cityA do 
        // It can infer the type as a list of integers. With the below for loop, 
        // however, working on cityStreets, it can't infer the type, so I have to 
        // explicitly declare initialRoute. 
        for initialRoute:int list in cityStreets do 
            let NextSteps = List.filter(fun (route:int list) -> route.Head = initialRoute.Tail.Head) cityStreets

            if NextSteps.IsEmpty then 
                // This returns the paths that only involve 2 points 
                yield initialRoute
            else 
                // This is the recursive call to get the non-trivial paths 
                yield! Seq.toList(BuildRouteBranch cityStreets initialRoute.Tail.Head [initialRoute.Head])
    }

This will walk through every one-way in the city list.  It looks for routes head matches the tail of the current one-way.  If there are no one-ways that meet this requirement, then it’s reached a dead-end right out of the gate, and just returns the current one-way as a 2-point route.  If there is a match, it starts building that branch of the tree by calling the recursive function BuildRouteBranch.

let rec BuildRouteBranch cityStreets startingPoint routeSoFar =
    let NextSteps = List.filter(fun (route:int list) -> route.Head = startingPoint) cityStreets

    seq {
        if NextSteps.IsEmpty then 
            // We're at the end of this branch, so return it; since it was built up in reverse order 
            // re-reverse it now. 
            yield List.rev(startingPoint::routeSoFar)
        else 
            // We still have at least one step to go down this branch, so find all of the sub-branches 
            // and recurse to flesh them out. 
            for nextStep in NextSteps do 
                yield! Seq.toList(BuildRouteBranch cityStreets nextStep.Tail.Head (startingPoint::routeSoFar))
    }

BuildRouteBranch takes three parameters:

  • cityStreets: the list of one-ways in the city
  • startingPoint: the intersection to being building from
  • routeSoFar: the route that we’ve built so far, stored as a sequence of lists of integers

It begins by looking for one-ways whose head matches the startingPoint passed in.  That list is stored in the NextSteps variable.

If NextSteps is empty, then we’ve reached a dead end.  It tacks startingPoint onto routeSoFar, reverses it (since it was built in reverse order up to this point), and returns that route.

If NextSteps is not empty, then I loop through every item in it, and call BuildRouteBranch recursively on each, passing in the following:

  • cityStreets – this just gets passed through
  • startingPoint – this gets nextStep.Tail.Head.  The iterator “nextStep” is a list, and I want to get the second element of that list.  When I call nextStep.Tail, I get a list with a single element.  To get the element itself, as a integer, I access the .Head property.
  • routeSoFar – I tack startingPoint onto the front of the routeSoFar value that got passed in, and pass that concatted list down to the next level of recursion.

The results of that recursive call are kicked out using yield!.

It was this step that ended up being the most difficult of the entire solution, mostly because I was trying to wrap my brain around the data structures, and then trying to wrap my brain around how to populate them with data.  My previous, failed attempts to implement the solution crumbled under their own weight.  I had lists within lists within sequences within even more lists – the logic to process those data structures was just crazy.  Even when I was in the thick of it, my intention was always to just get something that worked, and then I could refactor it into simplicity.  I found it easier to just start over.  Twice.

Possible Routes (Round 2)

Once I had my initial list of routes (technically a sequence of lists of integers), I needed to expand it to show all possible routes through the city.  The routes I have at this point start at an intersection, and go to dead-ends.  Now, I need to find all subroutes of those.

To do that, I make go through every route generated by Round 1.  I want to expand it to include all subroutes that begin with the current route’s head, and then all subroutes that end with the current route’s tail.  For example, if given the route 02341, this expansion would result in the following:

    02
    024
    0243
    02431

    24
    243
    2431

    43
    431

    31

This is accomplished by first calling GrowRouteTree:

let GrowRouteTree cityRoutes:int list seq =
    seq {
        for currentRoute:int list in Seq.toList(cityRoutes) do 
            for i = 0 to currentRoute.Length-1 do 
                yield! (FindRoutesInBranchWithThisHead (currentRoute |> Seq.skip i |> Seq.toList) [])
    }

This loops through every route generated in Route 1.  For each currentRoute, it then loops through the route, and calls the recursive function FindRoutesInBrandWithThisHead to do just that.  The inner loop walks through the points in the route, and generates a subroute using this structure:

(currentRoute |> Seq.skip i |> Seq.toList)

Which says “start with the currentRoute, skip i elements and convert the rest to a list”.  The second parameter of FindRoutesInBranchWithThisHead, routesWithHead, will accumulate the subroutes.  I initialize it by passing in an empty list. The FindRoutesInBranchWithThisHead itself looks like this:

let rec FindRoutesInBranchWithThisHead (currentRoute:int list) routesWithHead =
    if currentRoute.Length < 2 then 
        []
    elif currentRoute.Length = 2 then 
        currentRoute::routesWithHead
    else 
        let newSubRoute = currentRoute |> Seq.take (currentRoute.Length-1) |> Seq.toList
        FindRoutesInBranchWithThisHead newSubRoute (currentRoute::routesWithHead)

This does a series of checks on the currentRoute passed in.  If currentRoute has length 0 or 1, then there’s nothing to do.  We don’t have a valid route anymore, so just return an empty list.  If currentRoute has length 2, then we return the entire route.  If currentRoute is longer than 2, we create a new subroute by taking every element from currentRoute’s head up to but NOT including it’s tail.  We tack the original currentRoute onto the list of routesWithHead, and recurse with our new subroute.

Distinct Routes

Now that I have all routes and all possible subroutes through the city, I have to boil the list down.  The recursion and looping from the first two Rounds has generated a LOT of duplication.  To de-dup it, I simply convert the sequence to a set, and then back to a sequence.

Anti-climatic, I know.

Route Matrix

Now the time has come to actually tally up the number of ways to get from point A to point B.  To do that, I’ll walk through the list of distinct routes.  I’ll pick off the first and last element of each, and use those as a pair of coordinates in a 2-D matrix.  I’ll add 1 to that cell of the matrix that is represented by that pair.

Before I can do any of that, however, I need to figure out how large to make the matrix.  That’s determined by the largest value across all of the routes, +1 (since the intersections are 0-based):

let maxIndex = (Seq.max (Seq.max cityDistinctRoutes)) + 1

Next, I’ll create the matrix itself, and initialize every cell to 0:

let routeCounts: int[,] = Array2D.zeroCreate maxIndex maxIndex

Finally, I’ll tally up the number of distinct routes using the CountTheRoutes function.  I passed in the 0-initialized matrix, and get a populated one back.

let rec CountTheRoutes (cityRoutes:int list seq) routeCounts: int[,] =
    match Seq.toList(cityRoutes) with 
        | [] -> routeCounts
        | topRoute::remainingRoutes -> let routeStart = topRoute |> List.head;
                                        let routeEnd = topRoute |> List.rev |> List.head;
                                        routeCounts.[routeStart,routeEnd] <- routeCounts.[routeStart,routeEnd] + 1
                                        CountTheRoutes remainingRoutes routeCounts

CountTheRoutes is a recursive function that pulls off the top route, processes it, and then calls itself with the remaining routes.  Once it runs out of routes to look at, it returns the now-populated routeCounts matrix.  The “processing” part for a given pair is three lines:

  • Populate a variable called routeStart.  This is first element of topRoute, obtained via the .Head property.
  • Populate a variable called routeEnd.  This is the last element of topRoute, obtained by first reversing topRoute, then taking the Head.
  • Increment (by 1) the routeCounts cell where routeStart is the first index and routeEnd is the second.

I also created several utility functions for printing out the data structures:

let verbose = true;

let printSeqVertical seq1 = Seq.iter (printfn "%A") seq1; printfn "" 
let printSeq seq1 = Seq.iter (printf "%A") seq1; printfn "" 
let printVerbose message = if verbose then printfn " %s" message
let printMatrix mat1 = printfn "%A" mat1

The names should be self-explanatory.

Full source code for the general solution (cyclical and non-cyclical cities) can be found in the OneWays.zip archive at http://TinyURL.com/MarkGilbertSource.  In my third and final post, I’ll show how I extended the above solution to support cities where cyclical routes were possible.  This solution was developed with Visual Studio 2008, with F# installed (the latter can be downloaded for free here: http://research.microsoft.com/en-us/um/cambridge/projects/fsharp/release.aspx).

Advertisements

August 30, 2011 - Posted by | F#

1 Comment

  1. […] for finding the number of distinct paths from a given point in a city to another.  In Part 2 of this series, I went through the solution for cities where cyclical routes weren’t possible.  In […]

    Pingback by Finding my way with F# – Part 3 of 3 « Mark Gilbert’s Blog | September 3, 2011


Sorry, the comment form is closed at this time.

%d bloggers like this: