Timeline for How can I find the valid words in a grid of characters?
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 13, 2014 at 15:28 | history | edited | user1430 | CC BY-SA 3.0 |
added 392 characters in body
|
| May 13, 2014 at 15:24 | comment | added | user1430 | (If you want to discuss this further, please consider joining the Game Development Chat as comments should not be used for extended discussion.) | |
| May 13, 2014 at 15:21 | history | edited | user1430 | CC BY-SA 3.0 |
added 392 characters in body
|
| May 13, 2014 at 15:19 | comment | added | user1430 | The technique I am describing is not "store the dictionary in a trie," (that's just a requirement of the technique) it's using trie traversal at each tile on the board to determine if a valid word exists on the tile. The trie allows you to short-circuit the search and avoid wasting time. I added a link to some guy's blog where he discusses the technique (and others), which may help clarify. | |
| May 13, 2014 at 14:38 | comment | added | Tavio | However, the problem I'm facing does not lie within the way I determine whether a word is valid or not, but with checking all combinations on the board that form words that can be valid or not. I may have described the scenario poorly, but I would like to search for words in any direction and even for words that make corners along the way, so long as the tiles are next to each other either horizontally or vertically, but not diagonally. So even with your suggestion, this problem still persists... | |
| May 13, 2014 at 14:37 | comment | added | Tavio | Hello Josh, thanks for the detailed answer. In fact, what you described is pretty much how I store the dictionary in my game, except that I don't assume that words need to end on leaves. The nodes in my tree have a property called "isTerminator" that determines whether that node is the end of a valid word or not. This is to account for cases like the word "rate". In my tree, the 'e' in this case has other children, such as 's' and 'r', but it is also the terminator for the word "rate". So if the search ends in this 'e' after going through "rat", I know I have a valid word. | |
| May 13, 2014 at 12:01 | comment | added | Taemyr | @el.pescade Yup. But that does not allow for shifting rows or columns. | |
| May 13, 2014 at 11:42 | comment | added | el.pescado - нет войне | @Taemyr using plain trie, yes. But one could use Aho-Corasick algorithm which utilizes slightly modified trie is much more effective (linear). With Aho-Corasick algorithm one can find all valid words in nxn matrix in O(n^2) time. | |
| May 13, 2014 at 11:05 | comment | added | Taemyr | Also of interest, using a trie and testing every potential word requires 9300 comparisions for a 5x5 grid. The algorithm for testing the whole nxn grid would have complexity O(n^4). So I would estimate the number of comparisions for a 10x10 grid to be about 16 times as much, or just short of 150000. | |
| May 13, 2014 at 10:35 | comment | added | Taemyr | OTOH I think OP will want a more efficient string matching algorith than what he currently has. | |
| May 13, 2014 at 10:18 | comment | added | Taemyr | OP states that he has an algorithm to match the word to a character string. So I don't think this answers the question. | |
| May 13, 2014 at 5:33 | comment | added | Adam Eberbach | Great answer. A "word" is anything in the game's dictionary full stop. | |
| May 13, 2014 at 3:42 | comment | added | AturSams | Brute force isn't the only way like you explained yourself. :) There are a lot of prefixes that hint there is no point to keep looking. (Most [random] strings aren't words. +1 | |
| May 13, 2014 at 2:30 | history | answered | user1430 | CC BY-SA 3.0 |