Jump to content
  • Advertisement
Sign in to follow this  
Darkbouncer4689

algorithms/data structures with boggle boards!

This topic is 2561 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I recently received this as an interview question. The interview is over and I did not get the job (so I'm not trying to cheat on an interview, just trying to further my knowledge of algorithms and data structures for the future).

The question is as follows:
[font="Times New Roman"]Write a function which will find all the words on ageneralized Boggle™ board. The functionshould take as input the board dimensions, the board, and a dictionary of validwords and it should output the list of all found words to the calling function. You should consider how your approach willperform with a large dictionary and a large board.

My solution to this was to perform a quicksort on the dictionary words. Then I would do a depth first search to get all of the permutations of letters along the board and use a binary search to see if the permutation is in the dictionary.

Based on the interview I guess this is not the best solution and at the time I could not think of a better one. Assuming the O(n log n) quicksort is a pre computational cost, each binary search is O(log n). The only thing I know of that could be faster than O(log n) would be to hash everything and have constant lookup time.

If anyone has some recommendations on better solutions to solving this problem I would love to hear them.

Thanks![/font]

[font="Times New Roman"][/font]

Share this post


Link to post
Share on other sites
Advertisement
Maybe a trie would be of use here. Build it from the dictionary words, then walk the board tile-by-tile (tagging each as entered), recursively entering the neighbouring tiles and tagging the tile as entered. (do not enter the tile when its tagged). Keep a pointer to the current trie node you are in, and if this tile completes a word, output it. Move on to the next neighbouring tile skipping any tagged tiles(if none are left, return from the recursive function). Move the trie pointer to the new letter if there is one. If not, leave the recursive function. When you exit the recursive function, untag that tile, adjust the trie pointer, and move on to the next. When the top-level recursive function ends, untag the current top-level tile and move on to the next.

Share this post


Link to post
Share on other sites
Nice answer! I had actually used a trie structure before but didn't think about it until you mentioned it. I think this structure would definitely be more efficient than peforming a binary search each time. Since you would traverse the tree as you form potential words it would be constant time with little overhead for each lookup right?

What is the general lookup time for a structure such as this? Most tree structures are log n, but since this tree isn't balanced it makes things a little different.

Share this post


Link to post
Share on other sites
Since you will be pointing to the current letter (partial word), I guess it would depend on looking up the sub-nodes. If you use a vector, you will have to iterate to find the next letter. an array of 26 elements would be faster (since you can index the letter) but this could be expensive memory-wise.

Share this post


Link to post
Share on other sites
I would perhaps approach this the other way around. Step through the dictionary from start to finish and for each word see if you can find it on the board, making only legal moves.
As a bonus, there is no need to sort first, but if you do then the results come out in sorted order.

You can also buld a set of all letters that are on the board and if the word contains letters not on the board, then skip it immediately.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!