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

## 2 Comments

Sorry, the comment form is closed at this time.

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

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