Mark Gilbert's Blog

Science and technology, served light and fluffy.

Solving The Island Problem, Part II

Last Wednesday, we held our monthly FLUNK meeting, and I showed off my implementation of Grand Theft Wumpus.  When I got around to talking about how I solved the island problem, a very interesting conversation developed.  Eventually the conversation became focused on answering the question – what did my technique actually do?  (For a full refresher, see the section titled "Solving the Island Problem" in my previous post.)

For the remainder of this post, I’ll use the convention of referring to individual cells in the matrices using the form "X-Y", where "X" is the 1-indexed row number, and "Y" is the 1-indexed column number.  A 1 in a given cell means that there is an undirected edge that connects nodes X and Y.

The "technique" that I’ll evaluate is representing the graph as a half-matrix, where only the edges below the diagonal are shown.  The technique is broken up into two phases – analysis and bridging.

Q: Does the analysis technique identify the islands? 
A: No.

If you look at the half-matrices for the connected graph and the island graph, the change is rather minute:

Half Matrices Side By Side

My technique says to add 1s so that every row (or column) end up with at least a single 1.  Removing the 4-2 edge doesn’t open up the 4th row.  In fact, it’s no clearer what the islands are in my graph now than before.

Half Matrix - Identifying the Islands

In this image, the edges that form one island is represented by the green box, and the second by the blue box.  The two aren’t separated by a gap that removing the 4-2 edge opened up (i.e., a newly blanked row).

Q: Does the analysis technique even tell us if there islands at all?
A: No.

As before, the matrix representation doesn’t make it any easier to see if we have a single graph that connects every node.  The half-matrix for the connected graph has a complete empty row 3, and a completely empty column 5.  No clues there.

Q: Does the bridging technique connect the islands in a minimal way?  In other words, am I guaranteed that we won’t be building bridges to nodes that were already part of a connected graph?
A: No.

The analysis technique will identify row 3 as having no 1s in the original, connected graph’s half-matrix.  That would have triggered a 1 to be added to cells 3-1, 3-2, or 3-3 (it will pick one of these at random).  However, the original graph was already connected – there should be no need to add another edge at all.

 

My final answer
And now I can answer the original question: What does this technique do? 

It ensures that by the end we will have a single graph that connects all of the nodes.  It won’t be necessarily a minimal graph, but we can be assured there won’t be any islands left.

An “adjoining” thought

As I was writing this post, it occurred to me that you might be able to make an argument that putting a 1 in an “adjoining cell” would connect the islands. 

Half Matrix - Identifying the Islands

To create a graph with islands, I removed a 1 from cell 4-2, which adjoins cell 4-3.  Obviously putting that 1 back to 4-2 would bridge the islands, but adding a 1 to one of the other adjoining cells – 5-3 or 6-2 in this case – would also work.  This bridging technique could be stated as “make sure there is at least one pair of adjoining cells in each island pair have 1s.”

However, being able to use the "adjoining cells" technique only works if you know where the islands are already, and that’s not obvious by just looking at the matrix – I had to effectively traverse the graph to see it.

Furthermore, it only works if the islands are actually adjoined in the matrix.  Imagine a graph if 6 nodes and NO edges.  In this case, the graph would have 6 islands.  The matrix would be all 0s, and I’m hard-pressed to figure out how to color the 6 islands in it – there wouldn’t be any 1s to guide me.  Even if I could color the islands, they wouldn’t be touching each other, and therefore I have no way to identify the “adjoining cells” to put 1s into.

Advertisements

February 15, 2012 Posted by | F# | Comments Off on Solving The Island Problem, Part II

Grand Theft Wumpus – Adventures in F#

My functional language user’s group, FLUNK, is currently working our way through Conrad Barski’s "Land of Lisp".  Barski takes up the challenge to teach Lisp by writing video games with the language.  My functional language of choice is F#, so I’ve been implementing the games using that instead.

The latest one is a takeoff of a 1970s game called "Hunt the Wumpus" (http://en.wikipedia.org/wiki/Hunt_the_Wumpus).  True to form, Barski decides to reboot it as "The most violent programming example ever put into a textbook", and "Grand Theft Wumpus" is born.

To get the full source code and executable for my implementation, download the "GrandTheftWumpus.zip" archive from http://tinyurl.com/MarkGilbertSource.

Visual Improvements
As I worked my way through the requirements, I decided to take a few liberties and improve upon the game.  Several of my improvements were visual.

Barski models Congestion City as a graph of nodes connected to each other by edges, and then uses an open source program called GraphViz (http://www.graphviz.org/) to display it pictorially.  Barski directs you to generate the graph using GraphViz, and open the resulting image in your web browser.  I decided to take a slightly more integrated approach with my implementation: I’d create a C# front-end that would do the job of calling GraphViz, and would immediately refresh an Image box to the new image.  I would call this with every move, and as a result you would constantly be updated with where you were and what was around you.

App Screen Shot 1

Implementing the game engine in F# and the UI in C# meant that the former would have to take commands via a public method, and raise events that the latter could handle. That alone meant that my game engine would look and feel more like an object oriented solution than a functional one.  Furthermore, this game was a lot more involved than I thought it would be, and I ended up working almost down to the wire to get it finished.  As a result, there are several places where I fell back to my OO/imperative habits of loops rather than the more functional lambda expressions and other F# constructs.  I don’t know what these two approaches look like under the covers – they may be optimized down to the same thing – but I still felt like a phony writing it that way.  I may go back and try to revise the loops out later.

A couple of other minor improvements were in how the graphs were drawn.  GraphViz has a lot of options for arranging and coloring the nodes and edges.  For starters, I knew I wanted an easy way to show which node you were standing on.  I was already tracking which node was "current", so I simply color that node green (see the screen shot above).

Another adjustment was in how the edges with police were represented.  As Barski presents the game, if you come upon a node with "Sirens" on it, you can be sure that one or more edges connected to that node have police on them.  However, you don’t know which ones.  That made it very much a crap shoot whether you would walk into a barricade (and lose) with your next move.  It made for a very frustrating game.  To simplify it, and move the game slightly closer to reality, I color the edges with police blue.  That simulates you hearing sirens in a given direction, not just hearing them in general.  That allowed you to still be constrained by the barricades, but still be able to play the game with a certain level of strategy (as opposed to luck).

I also found that if I only included the nodes you had visited and the nodes you could see in the data file pumped through GraphViz, it would arrange those nodes in a given layout.  When I moved to a new node, and additional new nodes were revealed, GraphViz would re-lay out the entire graph, making it hard to figure out where you had already been, and where you had not yet explored.  To get around that issue, I include all nodes and edges every time, but I color the ones that you shouldn’t see yet white (edges, nodes, and node text).  You still get a little shifting when you visit a new node because the text goes from something like "(14) ?" to "(14) Lights Sirens", but not nearly what I was getting originally.  It also explains why the nodes and edges look broken in places – you’re seeing the white lines overlaid on the black/blue ones.

Finally, if you just pass the data file to GraphViz, the nodes overlap quite a bit. To avoid that, I pass an additional command-line parameter of "-Goverlap=scale" which forces the nodes apart.  Unfortunately, GraphViz gets a little overzealous with this sometimes, and as a result the graphs tend to be quite large.

Solving the Island Problem
Of all of the improvements that I made to the game-as-presented, the one I am most proud of is the solution to the island problem.  How do you create a random city of X nodes, and guarantee that you can actually get to all of the nodes when starting from any of them?  In other words, how do you prevent islands?

Once he creates the initial, random city, Barski actually walks the graph to find any islands, recording which nodes he’s visited along the way (and making sure he hits all of them).  I decided to try to find a more elegant way.  Something from my college class on graph-theory must have stuck, because I remembered that you could represent a graph as an NxN matrix.  So, if you had a 6-node graph that looked like this:

ConnectedGraph

You could represent that as a matrix like this:

CompleteGraph-CompleteMatrix

The 1s here represent a connection between those two nodes, and 0s mean there is no direct connection between them.  When the engine originally lays out the city, and it creates an island, the graph might look something like this:

Graph with Islands

The matrix, then looks like this:

IslandGraph-CompleteMatrix

That doesn’t initially appear to really be easier to find the islands, until you look "below the fold".  Nodes in Congestion City don’t connect to themselves, to the diagonal will always be 0s.  This is what I refer to as the "fold":

IslandGraph-CompleteMatrix-FoldHighlit

Technically, the graph is represented twice in this matrix – once above the fold, and once below.  Since this is an undirected graph (where you can go from every node X to Y, and from Y to X), there’s no reason to include both sets.  What if we removed the one from above the fold?

IslandGraph-HalfMatrix - Nothing Highlit

Now the breaks in the graph stand out a bit better.  When the graph has an island, the half-matrix (here defined as below the fold, but you could just as easily look at the matrix above the fold) has at least 1 row and one column that has no 1s.  In our example, these are represented as row 3 and column 5:

IslandGraph-HalfMatrix - RowCol Highlit

Technically row 1 and column 6 also have no 1s in them, but I’m only interested in the ones below the fold.  All I have to do to work the islands out of the structure is check every row or column (as it turns out I don’t even have to check both – I only have to check in one direction to remove the islands) looking for the ones with only 0s in them.  Once I find those, I drop a 1 in a random cell, and move on.  Representing the structure as a matrix made it trivially easy to find and fix the islands.  So much so that that I decided to base the rest of the game engine on a edge-matrix instead of an edge-array as I had originally planned.

After completing in the rows, I then mirror the matrix so that the above-fold numbers match, re-completing it (that makes it easier to do the check of “is node X connected to node Y?).  My city is now islandless.

(And for the record, I find it hard to believe that I’m the first person to use a matrix in this manner to link up graph islands.  Given how developed graph theory is, I have to believe this already has someone’s name attached to it.  Unfortunately, I don’t remember THAT much from my graph theory class, so I don’t even know what questions to ask of the Google to find that person.  I’d love to hear from you if you know.)

Overall, I enjoyed writing Grand Theft Wumpus, and I think it’s a very playable game.  In fact, my older daughter played it a couple of times, and then requested that it be installed on her computer so she could play it whenever.  What do you know?  I have a fan!

February 7, 2012 Posted by | F# | Comments Off on Grand Theft Wumpus – Adventures in F#

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.

September 3, 2011 Posted by | F# | 1 Comment

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

August 30, 2011 Posted by | F# | 1 Comment

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.

August 27, 2011 Posted by | F# | 2 Comments

Balancing Chemical Equations with F#

Hi.  I’m Mark, and I’m a FLUNKy.  FLUNK stands for the Functional Language User’s Network in Kalamazoo.  We meet the second Wednesdays of the month at 5:30 at the Biggs|Gilmore office in downtown Kalamazoo (261 E Kalamazoo Ave).

The first meeting, we decided that everyone should select a functional language, and we would select a problem to solve.  Each of us would attempt to solve it in our own language, and then we could compare notes on the solutions.  We have people working in languages such as Javascript, ML, Lisp, Python, and Scheme.  When I was looking for a language to work in, I ended up boiling it down to Haskel and F#.  I ended up selecting F# primarily because of it’s strength with math (for example, many common mathematical constants are built right into the language).  It was a bonus that as a Microsoft language it also had full access to the .NET Framework – something that’s come in handy a few times already.

One of our recent problems involved writing a program that would determine if a given chemical equation was balanced or not.  The input was the equation in string format (all of the subscripted numbers were made normal to simplify the parsing), and the program simply had to return True or False for each.  If your high school chemistry is failing you, “balanced” means having the same number and type of atoms on each side of a reaction.  For example, the equation

2Na + 2H2O = 2NaOH + H2

is balanced, while this equation

C6H12O6 = 3C2H2 + 3O2

is not (there are 6 hydrogen atoms missing from the right side).

My basic solution to the problem was to first break up the input string into its constituent parts, or tokens, and then count the number of atoms on each side of the equation.  Atoms on the left side of the equals sign would be added to the total, and atoms on the right would be subtracted.  The equation would be declared balanced if all of the atom tallies were 0 at the end.

 

A token of goodwill

Before I could tokenize the original string, I needed to decide what actually counted as a token – what kinds of characters do I actually care about?  I settled on this list:

  • PlusSign
  • EqualsSign
  • A number
  • A string (of 1 or more characters)

The plus sign would denote the end of one molecule, and the beginning of another.  The equals sign would denote the end of the left side of the equation, and the beginning of the right.  These transitions would prove useful later when we’re tallying up atoms.

A “number” could be a coefficient preceding a molecule, or a subscript following an atom.  The precise meaning of each number would be determined later, when the placement of the number relative to the atom was taken into account (see the next section for the specifics).

A “string” would be single atom.  Some atoms like Hydrogen, Oxygen, and Nitrogen are abbreviated with a single, upper case letter (H, O, and N, respectively).  Most of the rest, such as Sodium, Helium, and Silver are abbreviated with 2 letters – the first uppercase and the second lowercase (Na, He, and Ag, respectively).  When we first reviewed the solutions to this problem, someone brought up that there is a small, but growing, number of atoms that have three letter abbreviations.  Starting with element 110, the elements are abbreviated with 3 letters – the first uppercase, and the following two lowercase: Ununnunium (Uun), Ununbium (Uub), and so on.  Once I got my solution to work for 1- and 2-letter elements, extending it to 3-letter elements turned out be, well, elementary.

Here is my Tokenize method:

// This will recursively tokenize our original equation
let rec Tokenize acc = function
    // end of list; terminates; tokens are pulled off in reverse order, so we re-reverse the list here
    | [] -> List.rev acc 

    // Ignore whitespace
    | whiteSpace :: restOfList when Char.IsWhiteSpace(whiteSpace) -> 
            Tokenize acc restOfList

    // Look for triple letter atoms
    | firstChar :: secondChar :: thirdChar :: restOfList when Char.IsUpper(firstChar) && Char.IsLower(secondChar) && Char.IsLower(thirdChar) -> 
            Tokenize (Token.String(firstChar.ToString() + secondChar.ToString() + thirdChar.ToString()) :: acc) restOfList
    // Look for double letter atoms
    | firstChar :: secondChar :: restOfList when Char.IsUpper(firstChar) && Char.IsLower(secondChar) -> 
            Tokenize (Token.String(firstChar.ToString() + secondChar.ToString()) :: acc) restOfList
    // Look for single letter atoms
    | firstChar :: restOfList when Char.IsUpper(firstChar) -> 
            Tokenize (Token.String(firstChar.ToString()) :: acc) restOfList

    // Look for triple digit numbers
    | firstDigit :: secondDigit :: thirdDigit :: restOfList when Char.IsDigit(firstDigit) && Char.IsDigit(secondDigit) && Char.IsDigit(thirdDigit) -> 
            Tokenize (Token.Number(System.Int32.Parse(firstDigit.ToString() + secondDigit.ToString() + thirdDigit.ToString())) :: acc) restOfList
    // Look for double digit numbers
    | firstDigit :: secondDigit :: restOfList when Char.IsDigit(firstDigit) && Char.IsDigit(secondDigit) -> 
            Tokenize (Token.Number(System.Int32.Parse(firstDigit.ToString() + secondDigit.ToString())) :: acc) restOfList
    // Look for single digit numbers
    | firstDigit :: restOfList when Char.IsDigit(firstDigit) -> 
            Tokenize (Token.Number(System.Int32.Parse(firstDigit.ToString())) :: acc) restOfList

    // Look for +
    | plusSign :: restOfList when plusSign.Equals('+') -> 
            Tokenize (Token.PlusSign :: acc) restOfList

    // Look for =
    | equalsSign :: restOfList when equalsSign.Equals('=') -> 
            Tokenize (Token.EqualsSign :: acc) restOfList

    // All other characters, just terminate
    | _ -> []

This is invoked with this line:

let Tokens = Tokenize [] (List.ofSeq equation)

Where “equation” is my original string, converted to a sequence of characters.  The Tokenize routine performs pattern matching by breaking off the first few characters from the current sequence, and examining them.  When it finds a rule that matches, it creates a token out of those characters, adds that token to the accumulator, and recurses with the rest of the string.  Each “rule” here is denoted with a pipe ( | ).  Let’s walk through them one by one:

  1. The default case is where the incoming sequence is empty.  If that’s the case, it simply returns the accumulator, acc.  This case gets hit when we’ve parsed the entire original equation.
  2. The next rule skips past any whitespace in the equation.  In this case, it strips the whitespace out, and recurses with the rest of the string.
  3. The next three rules look for atoms.  First, we look to see if the next three characters are an uppercase letter followed by two lowercase letter.  If that test fails, then look for one uppercase letter and one lowercase letter.  If that test files, then look for just an uppercase letter.  In all three of these, we make a String token out of the letters found, add that token to the accumulator, and recurse with the rest of the original string.  The order of these three rules is important.  If they were reversed, the “N” of a sodium (Na) atom would be treated as its own token.
  4. The next three rules look for numbers.  My solution only supports 1-, 2-, and 3- digit numbers.  One of the other solutions I saw (in Scheme, if I remember correctly) was able to incorporate a regular expression into the pattern matching so that any length number would be found correctly.  When I wrote this, I couldn’t figure out how to weave the regex into the pattern matching rules.  The individual digits numbers are converted to a string, merged and converted to a Number token, and then added to the list.
  5. The next rule looks for the plus sign.  A PlusSign token is added to the list here.
  6. The next rule looks for the equals sign.  An EqualsSign token is added to the list here.
  7. The final rule looks for any other character in the string, and terminates if any are found.

So, Tokenize will taken a string like this

2Na + 2H2O = 2NaOH + H2

and break it up into a list of tokens:

2 Na + 2 H 2 O = 2 Na O H + H 2

 

I am a beautiful and unique snowflake

The next step was to get a unique list of the different atoms in the entire equation.  That turned out to be one of the most elegant lines of code in the entire solution:

let UniqueAtoms = Tokens |> List.filter (fun t -> (t.GetType().Name.Equals("String"))) |> Set.ofList |> Set.toList

The |> operator is kind of like a pipe ( | ) in Unix – it takes the output of the previous function, and passes it in as the input of the next one.  With that in mind, let’s break this line down:

  • Start with Tokens (the list of all tokens created in the previous step).
  • Run it through List.filter, and find all of the tokens that have the name of “String”.  These are the atoms.
  • Convert that filtered list to a Set…
  • And then convert it back to a List.  Store this in UniqueAtoms.

The real magic here is the last two steps – converting the list to a set and back again automatically de-dups the list.  Voila!  A list of unique atoms.

 

Tally ho!

Now it’s time to count.  We want to count up the number of atoms on each side of the equals sign, taking into account the molecule coefficients and the atom subscripts.  I decided that I would maintain a list of key-value pairs, one pair for each atom.  The key would be the atom token, and the value would be the total number of that kind of atom in the equation (from both sides).  That list is called AtomCounts, and it is populated with this line:

// Next, create a list of key/value pairs, to hold the count for each atom.
// Initialize the counts by calling SumAtoms for each element
let AtomCounts = [ for atom in UniqueAtoms do yield (GetTokenValue atom, SumAtoms atom 0 1 1 Tokens) ]

This is another dense line, so we’ll take it in pieces:

  • This line creates a list using the square brackets [ ].
  • It populates that list using a “for” statement that walks through every “atom” in the UniqueAtoms list.
  • It yields key-value pairs (also known as tuples) where the key is the value of the “atom” token, and the value is the net sum of that kind of atom in the equation.

To get the value of the “atom” token (meaning the string like “Na” or “H” that represents the atom itself), I wrote a small function called GetTokenValue:

let GetTokenValue myToken = 
    match myToken with
    | Number n -> n.ToString()
    | String s -> s
    | _ -> ""

The SumAtoms function takes 5 parameters:

  • The atom token that we’re looking for.
  • A “0” for the initial tally for this atom.
  • A “1” for the initial sign.  While we’re counting atoms on the left of the equals sign, the sign will be positive.  When we hit the equals sign, we’ll flip this to “–1” so that we subtract instead of add. (Remember, the goal is to get all of the atoms to tally to 0; that will mean the equation is balanced.)
  • A “1” for the initial multiplier.  The “multiplier” in this case corresponds to the molecule coefficient.  If we have a molecule like H2O, then we have 2 hydrogen atoms and 1 oxygen, and there is an implied multiplier of “1” here.  If we have a molecule such as 4H2O, then the “4” is the multiplier for this atom, and as a result we have 8 hydrogen atoms and 4 oxygen.
  • The “Tokens” list, which is what we’ll parse through.

The SumAtoms function is as follows:

// This will recursively count up the number of each atom in the token list
// NOTE: The list that this operates on is the last parameter passed in; it is not shown in the parameter list here
let rec SumAtoms myAtom acc sign multiplier = function
    // If we're done processing tokens, then just return
    | [] -> acc

    // If we find our atom-with-subscript, increment the accumulator accordingly
    | currentToken :: currentSubscript :: restOfList when currentToken = myAtom && currentSubscript.GetType().Name.Equals("Number") -> 
            SumAtoms myAtom (acc+(multiplier * Convert.ToInt32(GetTokenValue currentSubscript) * sign)) sign multiplier restOfList

    // If we find our atom-without-subscript, increment the accumulator accordingly
    | currentToken :: restOfList when currentToken = myAtom -> 
            SumAtoms myAtom (acc+(multiplier * sign)) sign multiplier restOfList

    // If we find a different atom-with-subscript, skip it and keep moving
    | currentToken :: currentSubscript :: restOfList when currentToken.GetType().Name.Equals("String") && currentSubscript.GetType().Name.Equals("Number") && currentToken <> myAtom -> 
            SumAtoms myAtom acc sign multiplier restOfList

    // If we find a different atom-without-subscript), skip it and keep moving
    | currentToken :: restOfList when currentToken.GetType().Name.Equals("String") && currentToken <> myAtom -> 
            SumAtoms myAtom acc sign multiplier restOfList

    // Once we hit the equals sign, change the sign to negative, and reset the multiplier
    | currentToken :: restOfList when currentToken = EqualsSign ->
            SumAtoms myAtom acc -1 1 restOfList
    
    // If we hit a coefficient, it becomes the new multiplier
    | currentToken :: restOfList when currentToken.GetType().Name.Equals("Number") ->
            SumAtoms myAtom acc sign (Convert.ToInt32(GetTokenValue currentToken)) restOfList
    
    // Once we hit a plus sign, reset the multiplier
    | currentToken :: restOfList when currentToken = PlusSign ->
            SumAtoms myAtom acc sign 1 restOfList

    // Ignore all other tokens
    | _ -> acc

The basic idea is the same as with the Tokenize function – break off pieces of the list, and compare it to the rules defined.  When we find a match, process it and recuse with the rest of the list.  Let’s look at the rules one by one:

  1. If the list we’re processing (Tokens, in this case) is empty, then just return the accumulator, “acc”, which has the tally of the net number of this atom in the equation.
  2. If we find the target atom with a subscript after it, add “multiplier * subscript * sign” to the accumulator.  This adds (or subtracts if we’re on the right side of the equation) the total number of this atom in this molecule.  Recurse with the rest of the list, leaving the sign and multiplier values alone.
  3. If we find the target atom without a subscript after it, then add “multiplier * sign” to the accumulator.  Recurse with the rest of the list, leaving the sign and multiplier values alone.
  4. If we find a different atom, skip it, and recurse with the rest of the list, leaving the sign and multiplier values alone.
  5. If we hit the equals sign, recurse with the rest of the list, but this time change the sign to –1.  The multiplier is left alone.
  6. If we hit a coefficient, recurse with the rest of the list, but this time change the multiplier to the newly-found coefficient.  The sign is left alone.
  7. If we hit a plus sign, then it means that we finished one molecule, and are about to start another.  Recurse with the rest of the list, but reset the multiplier to 1, and leave the sign alone.
  8. If we hit any other token, stop and return the accumulator.

 

Survey says…

The last step is to see if all of our tallies are 0.  If they are, it means that the equation is balanced:

GoodSoFar <- List.forall(fun (key,value) -> value = 0) AtomCounts

This iterates through the AtomCounts list, and makes sure every value is 0.  If it is, then GoodSoFar is set to True.  This single, Boolean value is returned from the function.

 

Final thoughts

I’ve already mentioned one of the limitations of this solution – it only supports 1-, 2-, and 3-digit numbers.

A second limitation to this solution is it won’t handle “functional groups”.  This is a different kind of notation that arranges the atoms in the molecule to show the structure of the molecule better.  The poster-child molecule was boric acid: B(OH)3.  The “3” here is actually a coefficient that applies to everything in the parentheses.  For my solution to handle this correctly, you have to rewrite it as BO3H3.  Modifying my solution to handle this would require new rules in Tokenize to recognize the parens correctly, and then new rules in SumAtoms to treat the trailing number properly.

These aren’t the only two.  I remember seeing even more complicated notation in high school and elsewhere, so this solution definitely has a way to go being general.

This was the third or fourth F# program that I wrote, but it was the first time that I felt like I started to grasp some of the core concepts of a functional language – recursion and immutables.  The latter refers to a variable that gets created and initialized once, and then never changes value after that.  It becomes extremely useful when the program is running in parallel – no more synchronization or locking of data variables is needed.

This was also the first time I tried invoking an F# program from a VB unit test.  All of the logic above was developed test-driven, and my unit tests consisted of various test equations.  This was an important step for me to take because I think it will be much more like that I would write a library in F# and invoke it from a VB/C# application, rather than building a completely solution in F#.

My complete solution, including the unit tests, can be found in the archive “FSharp_BalancingChemicalEquations.zip” here: http://tinyurl.com/3qwvgo9.  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).  The unit tests were written with NUnit 2.5.2.

August 15, 2011 Posted by | F# | 1 Comment