Posted by Dibash on February 11, 2012 at 10:50 PM
If you guys don't know what the game of boggle is, then take a look at the wiki at http://en.wikipedia.org/wiki/Boggle. I wanted to creat a fast program that given a boggle board and a dictionary, it outputs all possible creatable words. Thinking about the problem for a bit there was a couple of ways to do it.
- 1) Use a trie to store the dictionary and search through the tries for words
- 2) Create a min-heap based solution by storing the current neighbors in a min-heap and recursivle DFS t through it while checking for proper prefix via binary search
- 3) Just do a recursive DFS on the board and perform a binary prefix search on the dictionary for each prefix.
Option 1 is pretty slow, comparitively of course, because it takes a while to build a trie. Option 2 is a little tricky and more complicated than option 3. The advantage option 2 has over option 3 is that, it doesn't have to be sorted since the result will come out presorted already if implemented correctly. My choice was option 3. Its simple, easy, and damn fast. My current working solution is on the hub at
https://github.com/dchhetri/Boggle-Solver" target="_blank" rel="nofollow">http://https://github.com/dchhetri/Boggle-Solver. On my mac, it solves a 4x4 in 0.083s with no optimization on. Anyways, I figured putting up the code would benifit someone on of these days. Its there for your cheating needs. If I have time, I might still try to optimize it mainly by taking advantage of the cache and making the code more cache friendly but I'll see what happens. That's all for now, Happy Coding!!