Mark Gilbert's Blog

Science and technology, served light and fluffy.

Finding my way with F# – Part 3 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.  In Part 2 of this series, I went through the solution for cities where cyclical routes weren’t possible.  In today’s post, Part 3, I’ll extend this solution to support cities that have cyclical routes possible.

Modifications to "Possible Routes (Round 1)"
Oddly enough, detecting when I was in an infinite route was not the hard part.  If I try to add a new point to a route, and that point is ALREADY in the route, then I have an infinite route on my hands.  The hard part was two-fold.

First, how do I represent an infinite route?  To represent an infinite route in the final matrix, the question (#2 from the UC Berkeley from the Fall 2010 Programming Contest, http://www.cs.berkeley.edu/~hilfingr/programming-contest/f2010-contest.pdf) required that I show this with a -1.  That would mean that there were an infinite number of ways to get from point A to point B.  Since all of my data structures boiled down to lists of integers, I decided stored -1 in the route would be a sufficient flag.

Second, how do I keep going after I found the infinite part of the route?  An infinite route could look like this:

    012121212345

Where points 1 and 2 have one-ways going between them, allowing for the cycle.  However, there is another one-way going from point 2 to point 3, allowing you to get out of the loop.  (It feels very much like being trapped in a traffic circle – miss your exit and you’re goin’ around again.)  Once I’ve identified that the subroute 12 can repeat, how do I break out of that to get to point 3?

Both of these are addressed by the extended BuildRouteBranch method:

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
            
                if List.exists(fun(currentItem:int) -> currentItem = startingPoint) routeSoFar then
                    // If startingPoint already in the list, then we've found an infinite route
                    if doesContainNegativeOne routeSoFar then
                        // If this route is ALREADY flagged as infinite, then just return it
                        yield List.rev routeSoFar
                    else
                        // Up to this point, this route has not been flagged as infinite; so, tack on a -1 to NOW 
                        // flag it as infinite, and then recurse as normal.  I still tack on startingPoint so that
                        // circular paths from point X to X are represented correctly as infinite in the final matrix.
                        yield! Seq.toList(BuildRouteBranch cityStreets nextStep.Tail.Head (-1::(startingPoint::routeSoFar)))
                else
                    // startingPoint isn't already in the list, so tack it on, and recurse with the next step
                    yield! Seq.toList(BuildRouteBranch cityStreets nextStep.Tail.Head (startingPoint::routeSoFar))
    }      

Previously, the meat of the "for nextStep in NextSteps do" loop was to simply call BuildRouteBranch recursively.  To support cycles, I have to now check if the item I’m about to add to the route – startingPoint – already exists in the route.

If it does already exist, then we have an infinite route on our hands.  I then check to see if I’ve already flagged this route as infinite (by checking to see if there is already a -1 in the route).  If I haven’t, then I call BuildRouteBranch recursively, and add not only startingPoint to the route, but a -1 as well.  So, in our previous example, the partial route would look like this at this point:

    012-1

When I call BuildRouteBranch, I pass it nextStep.Tail.Head as the new startingPoint, just as before.  That’s because I want to make sure there aren’t other ways out of point 2 than just going back to point 1.

Now, to get back to the case where I find I’m in an infinite route, and this route is ALREADY flagged as being infinite, I just return the current route.  Basically, I treat this as a dead-end, and I don’t go further with it.

These modifications allow me to detect and flag the route as being infinite, and then keep going to find any subsequent, non-infinite pieces of the route.


Modifications to "Possible Routes (Round 2)"

Expanding the initial set of routes to find all possible subroutes turned out to be very easy.  I want to preserve the -1s in the routes, because I’m going to use these as markers later when I count up the possible paths.  What I want to avoid is a "possible subroute" that consists of a -1 and some other number.  The -1s are purely flags – they aren’t real data points.

So, I added a new check to FindRoutesInBranchWithThisHead, specifically the check for where the incoming route has exactly 2 points.

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

If one of those two points is a -1, I just return an empty list; otherwise, I tack that 2-member route onto the routesWithHead accumulator, just as before.


Modifications to "Distinct Routes"

Since I want to pass the -1s through to the counting step, I can treat them as valid points here, and let the de-duping process work just as before.  As a result, there are not modifications to this step.


Modifications to "Route Matrix"

It is in this step that I use the -1s as the flags that they are.

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

                                        if doesContainNegativeOne topRoute then
                                            // If we found an infinite version of this route, flag it in the matrix as such

                                            // If the proposed route end is the negative -1, back up one more to get the real end of the route
                                            let routeEnd = if (topRoute |> List.rev |> List.head < 0) then (topRoute |> List.rev |> List.tail |> List.head) else (topRoute |> List.rev |> List.head)
                                            routeCounts.[routeStart,routeEnd] <- -1

                                        else
                                            let routeEnd = topRoute |> List.rev |> List.head;

                                            // Make sure this pair wasn't already flagged as infinite
                                            if routeCounts.[routeStart,routeEnd] >= 0 then
                                                routeCounts.[routeStart,routeEnd] <- routeCounts.[routeStart,routeEnd] + 1

                                        CountTheRoutes remainingRoutes routeCounts

Where can the -1s be in a given route?  As it turns out, through the process above, a route cannot start with a -1.  Therefore, I can compute the routeStart variable just as before.  A route can contain a -1 or it can terminate with a -1.  The latter fact means that the calculation for routeEnd needs to be modified since -1 is not a valid index.

First, I check to see if the current route contains a -1 at all.  If it does, then the corresponding cell in the matrix will be set to -1 – regardless of the value that is currently there.  I have routeStart, so now I need to calculate routeEnd.  To do this, I need to take into the possibility that there is a -1 at the end of the route.  If we have a route like this:

    123-1

Then we can’t use the -1 as the index.  What we really want is is the 3, since that is the true end of this route.  To calculate routeEnd, then, I use a ternary operator.  If the last point in the route is negative, grab the second-to-last point; else use the last point.  (The case where the -1 appears somewhere in the middle of the route will fall into the latter case.)

If I didn’t have a -1 in the route at all, then I can calculate routeEnd just as we did before – reverse the list and take the head.

Before we update the matrix, however, I need to check to see if there is a -1 there already.  If there is, then this particular route has already been marked as infinite, so I move on to the next route.  If it’s 0 or something positive, then I can increment like I did before.


Final Thoughts

Looking back, I don’t think this is a horrible solution.  It certainly works, but I feel like there should be a simpler way to solve this.  It seems like there should be a way to merge BuildRouteTree and BuildRouteBranch into a single routine, and that I should be able to merge GrowRouteTree and FindRoutesInBranchWithThisHead into a single method.  Doing that may also mean that a lot of the duplication of routes would disappear, eliminating the need for the third step of the algorithm. 

All of my data sets were tiny, so performance bottlenecks weren’t evident.  I have to believe that they’re there given the amount of looping and recursion I’m doing – just not evident.

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.  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).           

And finally, don’t ever visit to City C – you’ll be driving around in circles for hours.  For that matter, don’t go to Cities A or B, either – there are whole sections of each that you either can’t get to, or can’t get out of.

Advertisements

September 3, 2011 - Posted by | F#

1 Comment

  1. Thanks.
    PLH OOE Art

    Comment by Art Scott (@Semasiographic) | January 5, 2012


Sorry, the comment form is closed at this time.

%d bloggers like this: