Tuesday, April 3, 2012

Using Google Maps' Directions API

Code: https://github.com/damondoucet/Google-Maps

Consider a complete bipartite graph whose vertices are name-address pairs and whose edges represent the shortest routes between two addresses. Order the edges by length and print the results.

In other words, given two sets of name-address pairs, find the shortest route from each element in one set to every element in the other, and print the lengths all routes ordered by travel time.

What makes this problem interesting is the use of the Google Maps Directions API in order to find the routes between each pair of addresses.*

Our most important class is in the RouteFinder project--the JsonDownloader. We first UrlEncode our addresses and insert them into a query string. Next, we send requests to Google until they give us a valid response; every time they tell us that our query limit has been reached (a response containing "OVER_QUERY_LIMIT"), we increase our sleep between requests by a small increment so that we don't flood the server. Finally, we use a JavaScriptSerializer to convert the JSON response into a dynamic object.

Our RouteFactory simply takes two Location objects (two of the name-address pairs described in the problem) and uses the JsonDownloader to populate a Route object. Populating the Route is simply extracting values from the dynamic JSON object. JSON is, by definition, just a dictionary of values, so we make sure to use array syntax (route["distance"]) rather than object syntax (route.Distance).

With this project, because there's so much input and output, I deferred to using files instead of the console itself. Input should be stored in two separate files; each line is a name separated by an address with a pipe (|). Data is printed to an output.txt file in a tabular fashion. The RouteCollectionPrinter may be an interesting read as well; it uses LINQ to first calculate the column widths (the length of the largest element of each column) and then to print the spaced out values.

*I wrote this before Google introduced its Distance Matrix API; however, since we're not displaying the results on a Google Map (which is an explicit requirement), we have to do it this way anyway.

Monday, March 26, 2012

Evil Hangman

This program involves a word list like the Anagram Finder, although it's a bit more complicated.

You can find the code here: https://github.com/damondoucet/Evil-Hangman

Imagine a game of hangman. One player picks a word and the other player guesses letters until they've either run out of guesses or they've guessed the word. Evil Hangman is a twist (inspired by http://nifty.stanford.edu/ which has a number of other gems) so that the computer will only pick a word when it specifically has to; until then, it decides what the worst possible scenario would be, given the user's guesses.

For example, imagine the following pattern has been established:

B _ _ _

And imagine that the user has guessed 'A'. Let's also assume a tiny dictionary that only consists of the words BALL, BULL, BARN, BODE, BADE, BLAH, BAJA, and BAMA. The words can be categorized as follows:

  • no A (2 words)
  • A only as 2nd letter (3 words)
  • A only as 3rd letter (1 word)
  • A as 2nd and 4th letters (2 words)
The program assumes that picking the category with the largest number of words (in this case, A only as the 2nd letter) will be the best, and although that's technically not always the case it's enough for this program (I'll leave it as an exercise to the reader to find a counterexample). 

The code is split into two projects, one for managing the UI via Console and the other a class library to manage the game. I didn't bother with drawing a "hangman" graphic. 

In the class library there are three classes: MaskGroup, WordList, and Game. The MaskList represents a set of words categorized as above. The WordList provides functionality for reading from a file and applying guesses. The Game class is exposed by the class library and is, of course, used for all the game stuff. 

The magic is really in the WordList and MaskGroup, though. The WordList allows us to narrow our collection of possible words and the MaskGroup categorizes words into their respective subgroups based on guesses. These are actually just cutesy little LINQ functions, which made them pretty fun to write.

The Console project has three classes: one that wraps the game loop, another that offers simple console utilities (formatting an enumerable for printing and getting/validating input), and finally the UI. 

Just like with the AnagramFinder, it's not an extremely complicated program, but it's a lot of fun to play with. As a side note, by default it actually gives you 20 guesses and generally when my friends and I play, we need somewhere around 13-17, so it's not far off. 

Saturday, March 24, 2012

First Post! - An Anagram Finder

So for the next couple of posts, I'll detail some of the programming projects that I've done in the past that I'm rather proud of. I'll post a link to a github repository with the code and briefly explain the purpose of the program and the high points of the code.

Today, I'll talk about my Anagram Finder. It's a rather simple program, but it's really fun to play around with.

You can find the code here:  https://github.com/damondoucet/Anagram-Finder

The basic problem is to find all possible words that can be made from a set of letters. I used the Official Scrabble Dictionary that has about 172,000 words. (Yes, I'm aware that technically an anagram has to use all letters, but it's more fun this way)

Two classes make up the heart of the program: Word and WordList.

The Word class has a constructor that takes a string and a public bool IsSubsetOf(Word). It keeps a private Dictionary that stores how many of each letter are in that word; a word A is a subset of a word B if and only if the letter count of each letter in A is less than or equal to the letter count of that same letter in B.

The WordList class is an IEnumerable<Word> (so that LINQ operations can be performed on it). Its main function is NarrowToSubsetOf(Word), which returns a new WordList that consists only of the words that are subsets of the parameter. It also has two printing functions, Print() and PrintByLength(), which both regrettably print to the Console. Since it's a small program, I didn't bother with making its output dynamic.

Running with "damonalexanderdoucet" shows that you could make the words "nomenclature" and "mononucleated," among others.