Mark Gilbert's Blog

Science and technology, served light and fluffy.

Finding my way with F# – Part 1 of 3

Our latest FLUNK assignment was #2 from the UC Berkeley from the Fall 2010 Programming Contest: http://www.cs.berkeley.edu/~hilfingr/programming-contest/f2010-contest.pdf.*  This problem involved determining the number of ways to get from point A to point B in a city.  A “city” was defined as a series of one-way roads connecting two intersections – the latter denoted by numbers.  So the pair “03” means that there is a one-way road between intersection 0 and intersection 3.  We were given a series of one-way roads to go from, and then asked to create an AxB matrix to show the ways to get from intersection A to intersection B.

And then there was the “fun” requirement.  If you encountered any cyclical routes – ones where you’d pass through the same intersection two or more times on the way from A to B – the number of possible routes from A to B needed to be shown as infinite in the final matrix (represented there as -1).  So, if you had a route like 0123, but there was another one-way path defined for 21, you could have the following possible routes from 0 to 3:

    0123
    012123
    01212123
    0121212123
    etc.

It took me three hours of reading, thinking, and doodling with numbers to come up with my first algorithm for solving this.  It took me 3 more algorithm-overhauls to get one that would actually solve it, and even then only for cities that did not have cyclical routes possible.

The Data
One of the original requirements was to read in the data for the city from a text file.  I was anxious to get to the real meat of the problem, not waste time trying to get F# to read a file, so my solution ignores that requirement.  I hard-code each city in as a list of lists:

let cityA = [[0;1];[0;2];[0;4];[2;4];[2;3];[3;1];[4;3]]
let cityB = [[0;2];[0;1];[1;5];[2;5];[2;1]]
let cityC = [[0;1];[0;2];[0;3];[0;4];[1;4];[2;1];[2;0];[3;0];[3;1]]

These contain the pairs of intersections that define the one-way streets in each city. 

The Algorithm
I reasoned that if I could get this working for non-cyclical cities, I could then extend it to work for cyclical ones.  That was a leap of faith, but I was looking for any and all ways to simplify this problem so I could just get started.  On paper, I worked out that cities A and B did not have any cyclical routes possible, but C did, so initially I built the algorithm around City A’s structure.

I break the solution up into four major steps:

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

To find the number of ways that a person could go from point A to point B, I need to figure out how many possible paths are there from A to B.  To do THAT, I need to first follow the paths that originate from every intersection in the city, and go until I reach a dead-end.  For city A, this step called “Possible Routes (Round 1)” generates the following:

    01
    02431
    0231
    0431
    2431
    231
    31
    431

Next was expanding this list to show ALL paths through the city.  Round 1 generates all paths that start at point A and go until a dead-end.  The list of all possible paths also includes

  • Paths where you start at point A and stop somewhere along the path, BEFORE you reach a dead-end
  • Paths where you start somewhere along the way, and end up at the dead-end.

For city A, “Possible Routes (Round 2)” yields the following:

    01 expands to
        01

    02431 expands to
        02
        024
        0243
        02431
        24
        243
        2431
        43
        431
        31

    0231 expands to
        02
        023
        0231
        23
        231
        31

    0431 expands to
        04
        043
        0431
        43
        431
        31

    2431 expands to
        24
        243
        2431
        43
        431
        31

    231 expands to
        23
        231
        31

    31 expands to
        31

    431 expands to
        43
        431
        31

Now that I’ve found all possible start-end pairs in the city, I need to weed out all of the duplicate routes.  These are routes that are perfectly identical to each other (so 231 and 231, for instance).  Routes that have the same start and end points, but different inner-steps, are considered distinct (so 231 and 2341, for instance).  The “Distinct Routes” step through City A, then, are:

    01
    02
    023
    0231
    024
    0243
    02431
    04
    043
    0431
    23
    231
    24
    243
    2431
    31
    43
    431

Now all that’s left is to count the pairs and populate the route matrix.  I create a matrix that is NxN, and for each route that has starting point A and ending point B, add 1 to the tally for that pair:

    [[0; 4; 1; 3; 2]
     [0; 0; 0; 0; 0]
     [0; 2; 0; 2; 1]
     [0; 1; 0; 0; 0]
     [0; 1; 0; 1; 0]]

Full source code for the general solution can be found in the OneWays.zip archive at http://TinyURL.com/MarkGilbertSource.  In my next post, I’ll show you the solution I came up with for non-cyclical cities, and then the post after that I’ll show how I extended it to support cyclical ones.  The latter is the solution that you’ll find in the OneWays.zip archive.  It 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 no, it did not escape my attention that the original programming contest had an 8-hour limit, and this was just one of several problems that the students were being asked to solve.  By the time I finally got a general solution coded for both non-cyclical and cyclical cities, I was WAY past the 8-hour mark.  If you include the time I spent solving the balancing chemical equations problem from this same set, I’m way WAY past the 8-hour mark.

Advertisements

August 27, 2011 - Posted by | F#

2 Comments

  1. […] 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 […]

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

  2. […] 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 […]

    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: