Launching Swample
The best advice that’s post-it noted to my monitor is “patience/do it now!”. I lean left or right depending on context. It’s been a lean right couple of weeks. It’s better to do something and be making progress than have a great idea. A step forward is a step forward.
So this past week, I wrote and launched Swample. It’s something Richard and I had been talking about throwing together for a while now. Our first serious attempt at a web application. So with the launch of Google App Engine, I finally got around to it and knocked out a prototype.
It’s a pretty trivial little application for now, I’m looking to add features as we go. There was only one algorithmic sticking point. I wanted to tell the user during the game whether or not the words entered were valid. Which meant I had to solve the board up front before I set the user loose. But how can I solve the board fast enough so that the user isn’t waiting forever for a game to load?
Most solutions I saw via google just simply give up at a certain word length. Not counting words with more than 8 letters, presumably because of a scrabble dictionary. This certainly simplifies the solving algorithm and the space required for a dictionary. But for me wasn’t a valid solution.
In the unlikely event that a users finds a word that’s more than 8 letters, I didn’t want to disappoint with an ‘word not found’. And a brute force breadth first search was simply too slow. So I solved the problem by pruning the breadth first search.
If you’re looking at words and your word starts off with ‘QuZR’, there’s no point looking any more. So at each step along the way, only consider the segment of the dictionary that starts with the word you’ve built so far. For example, in python:
#narrow dictionary before next step of bfs ndict = dict([(word, 0) for word in words if word.startswith(start)])
This cuts huge dead end paths. As well as lowers your time searching in the dictionary, since you’re only searching a subset of it. It’s maybe memory intensive, but that’s the trade-off I was looking to make.
