Boggle Solver

I've been working on a pet project with App Engine to try and get a better feel for it. It’s a Boggle puzzle solver that does some AJAXy tricks to multithread the solving work. The source code is online as well for anyone that’s curious. (There is a popular knockoff called “Scramble” on Facebook that is either different enough to keep Hasbro from filing a lawsuit or Hasbro’s lawyers are waiting around for them to make some money before bothering.)

In the case of App Engine it's particularly sensitive to requests that take “too long” to process. This was a particular hassle when I was importing the dictionary that is used. In order to solve a Boggle puzzle fairly quickly you want to have all the possible words arranged in a trie. This way you can stop quickly if you’re following letters that will never spell anything as you traverse the puzzle board. It took splitting the dictionary into 5000 separate pieces to get it to load without pushing me over my quota for “long” requests. Luckily we only have to do that once.

Next came the challenge of the puzzle solving itself. Again, solving the whole board in one request takes a while to process, apparently more than is allowed without running into that “long” request quota. Even in an optimized form (see the links to Dan Vanderkam’s work at the end of this entry), the full dictionary trie is 3MB and that takes a non-trivial amount of time to load in when you’re trying to handle requests within a few hundred milliseconds.

The solution was to reload the dictionary again but this time to break it up by initial trigrams. For every initial three letters, I store the appropriate shard of the dictionary (all the words that start with that combination) as a trie. There is also a blacklist of trigrams that form no words (for instance “frw”).

The javascript calls in with a copy of the puzzle and a point on the board to solve from. The server code then finds all the trigrams starting from the specified point and loads the appropriate dictionary shards. Since we're only solving from one point on the board there won't be more than 72 shards to load for any javascript call. (9 directions from the point and then 8 directions from each of those points because we're not allowed to backtrack.) The server then traverses the board using the dictionary tries hunting for words. When it finds them it stores the word and the places on the board where the word was found.

This information is all reduced into JSON and returned back to the browser that made the javascript call. The javascript on the browser is then responsible for taking all the found words and locations and sorting them in a sane way and displaying them for the end user.

Dan Vanderkam has written some interesting code and blog posts about optimizations in solving Boggle puzzles.

...but how many Big Macs will it buy?

There was a conversation about investment at work that mentioned stocks, gold and the "Big Mac Index" so I decided to do a quick analysis.

Year	Big Mac	DJIA	Big Macs per DJIA	$/oz Gold	Big Macs per oz Gold
2001	$2.54	10790	4248	271	106
2002	$2.49	10259	4120	278	111
2003	$2.65	8601	3245	343	129
2004	$2.90	10409	3589	417	143
2005	$3.15	10827	3437	428	135
2006	$3.15	10883	3454	530	168
2007	$3.22	12474	3873	640	198

It didn't quite work out the way I had expected it to. Plotting the CPI (or the Euro) against these numbers might also be interesting.

Math Education

The TiVo has been recording CBS’s “Numb3rs” show for us for a while. Upon further investigation, and not totally unrelated to my last post, I’ve found they have a whole site at www.weallusematheveryday.com with practical mathematics exercises for high school kids (or older kids with rusty math knowledge) based on things mentioned on the show.

It’s good stuff. It would be interesting if one of the many medical shows focused just a little on teaching tools like this rather than obsessing over the love lives of the characters. If real medical professionals led lives like those depicted on every hospital drama I’ve ever seen on TV, our life expectancy would be much lower.

Not My Dream App

There’s a new contest at MyDreamApp.com for new Mac OS X software. The format for the contest with celebrity judges and open submissions from the user community and prizes for the top 3 entrants sounds like a lot of fun. A lot of fun, that is until you read the fine print.

Participants are forbidden from making their dream app open source if it’s selected as a winner. That’s right, by participating in the contest you agree to give up all interest in your idea and any code you put behind it to the group organizing the contest. If you wanted to give back to the community by offering your awesome idea for free or, better yet, offering it as open source software, you’re out of luck.

But wait, there’s more; the deal gets even better. In return for giving away your idea they’ll offer you a meager 15% royalty from ”net income” from the Mac version of the idea. “Net” in this context means if they spend money advertising, promoting or paying developers/QA/writers to work on the Mac version of the product that gets subtracted from the amount you get 15% of. This is exactly how many musicians get screwed out of the proceeds from their music by record companies. “You know it cost a lot to promote your album, so here’s a free cup of coffee. We look forward to your next effort.”

Just to top it all off, some top finishers get free equipment. The catch? The taxes on the giveaway are your responsibility. So you have to pay out of pocket federal, state and local taxes (let’s say 28%) of the value of the “free” item. I’m going to guess that the 15% of “net income” may not be enough to cover the taxes on the free item.

Did I mention the liability release provision potentially allows the organizers to skip out and not pay you anything? And if they do pay you it will be through PayPal. And if your submission is accepted you may not even be able to claim it was your idea on your resume without their permission. And, worst of all, if the effort required for them to follow through on making your idea a shiny product is more than “reasonable” they can just walk away and develop it for Windows instead. (And pay you nothing.)

It’s an interesting way for some people to feed on the creativity of others, and I guess if people understand all this and still participate, that’s their business. I’m a little dismayed that Woz and other luminaries are participating in something that seems so potentially abusive of it’s “winners”.

This isn’t to suggest that the people organizing the contest will do any of these nasty unkind things, only that they could if they wanted to. I don’t know any of them, and I hope, for the sake of those who participate, they stay honorable.

It would be nice if someone had an open source-friendly contest (with nicer rules) along these lines for great new open source Cocoa titles in the tradition of Adium and Colloquy.