Algorithm for quick search of words in the game noodle

Once in one social network I came across a noodle game with non-standard rules (large fields and knots). Pick-up programs mainly work according to the classical rules and on the 5x5 margins. Therefore, I had a sporting interest in writing my matching kit fully adapted to non-standard rules. And not just to write a matching list, but to implement the fastest possible word search algorithm.


A rather interesting mode “knots” is distinguished from non-standard rules, in which you can make a word using one letter up to 2 times (for example, in the screenshot above you can make the word SHALASH, the letters W and A used 2 times). As it turned out later, in the same position, the algorithm searches for all words in the nodule mode almost exactly 1.5 times longer than in the classical mode without nodules (this is not surprising, since there are more variations of words and the words found are longer). At the end of the article, the described algorithm will be tested in a test position in nodule mode.

Vocabulary

In order to make life more difficult for the algorithm, one of the largest dictionaries in such programs will be used. It has approximately 110,000 words.
An important role in the algorithm is played by the method of storing the dictionary in the program's memory. When loading each word is recorded in the structure in the form of a tree. Each node of this tree means a specific letter of the word and refers to no more than 32 subtrees (by the number of letters in the alphabet). The tree node in the program looks like this:

typedef TREE *NEXT; //    struct TREE { NEXT *next; //       char *str; //      char *wrd; //  NULL,      }; 

The str field contains a string with all letters that go out of this node, the size of the next[] array is equal to the length of this string.
The str field is used to find a specific node among the array of nodes next[] for this letter. To do this, we have introduced the ind() function based on strchr():

 int k=ind('',str); //  ()  ''   str 

If k<0 , then this letter is not in str , otherwise next[k] points to the node corresponding to this letter. For example, if str contains the string "" , then exactly 5 subtrees go from this node, and next[2] refers to the letter '' , since str[2]== '' , the same with other letters.
To illustrate all of the above, I will give an example of a tree on a specially prepared dictionary consisting of words:

 , , , ,  

If the field str==NULL , then this node is a sheet and it contains the dictionary word wrd . The node corresponding to the letter '' contains the word "" , nor is it a sheet, because there is another word in this dictionary, starting with - . The wrd field contains a string, which is obtained if you go from the root to the corresponding node, but if this string is not a dictionary word, then wrd contains NULL .
Let's call this tree a dictionary, it contains all the words from the dictionary. In addition to the dictionary tree, you need to prepare another one, which contains all possible inverted prefixes of words for each word (let's call this tree inverted). For example, for the word "" following lines will fall into the inverted tree: "", "", "", "", "" . Even for a test vocabulary with five words, such a tree will be cumbersome, so I’ll give a simplified version:

Words Vocabulary words prefixes in this tree are located backwards. The node in the red circle corresponds to the last letter of the inverted vocabulary prefix, i.e. matches the first letter of the word. To read the beginning of the vocabulary word you need to move from the red node to the root. The only difference between an inverted tree and a dictionary tree is that wrd serves as a flag ( NULL/ NULL ). Those. it does not store the string with the inverted prefix of the word, but:

• 1) The address of the global string (the contents of the string does not matter) if this node corresponds to the first letter of the vocabulary word
• 2) NULL , for all other nodes.

This is done to save space. For all red nodes wrd!=NULL , for the rest wrd==NULL . For example:

 root_inv->str == ””; root_inv->next[0]->str == ””; root_inv->next[5]->next[0]->wrd == NULL; //      root_inv->next[5]->next[0]->next[1]->wrd != NULL; //     

Both trees occupy 33M in memory, and directly from the dictionary they are built in about 5 seconds on i5, so it was decided to save the image of trees to a file and load it in the future. So the download speed was only 300 milliseconds.
')

Search algorithm

According to the rules for the move, you need to select an empty cell, and put there any letter.

Then you need to make a word using the letter. This letter can be both the first letter in a word, and not the first letter (although captaincy, but this is important). If the rules had said that the letter put must be exactly the first, then we simply use the dictionary tree, moving across the field from the set letter while descending down the tree. But since The set letter may not be the first, the dictionary tree cannot be used, because it is not known from which node to start the search. But we still have an inverted tree.
The idea is this: out of the cage with the set letter we move across the field, descending along an inverted tree. If we find a node with wrd!=NULL (red node), then this is a valid inverted word prefix. Having the prefix of a word, it is possible to find a node in the dictionary tree corresponding to the set letter, and then simply donate the remaining piece of the word already in the dictionary tree, starting from this node.
In order for the algorithm not to enter the cells that have already been passed for this word, there is a count in each cell using the count . Before starting the search, this counter is initialized with the number 2 (for knot mode) or 1 (for the classic mode) - this is the only difference between the modes in terms of the algorithm.
More detailed algorithm:

• 1) enumerate all empty adjacent cells
• 2) For each cell, iterate through all the letters of the alphabet (32 letters)
• 3) We enter in the current cell (let its coordinates be [x, y] ) the current letter s . So we get 32 ​​* n different positions, where n is the number of adjacent cells in the original position
• 4) The entered letter is considered the first letter for the inverted prefixes.
  Therefore, among root_inv->next[] we find the node t_inv corresponding to the current letter, i.e. t_inv is a subtree starting with the current letter:
  

   int k = ind(s, root_inv->str); //s –   if(k<0) continue; //         TREE * t_inv = root_inv->next[k]; 

• 5) Reduce the count[x, y] and call the search function in the find subtree (about which below) for t_inv and the cell [x, y]
• 6) End of a cycle to spell
• 7) End of the cycle on adjacent cells

Naturally, after the cycle, we spell the current adjacent cell.
The search function in the find subtree takes the playing field, the tree node ( tree ), and the cell coordinates (i, j) , from which it is necessary to start moving along the floor, descending along the tree :

• 1) If tree->wrd!=NULL , then a valid substring is found
  
  • a. If this node belonged to the dictionary tree, then this substring is a dictionary word in general, add tree->wrd to the array of found words.
  • b. If the node belonged to an inverted tree, then this substring is the inverted prefix of the word. In the dictionary tree, we find the node t corresponding to this prefix, and call the find function for t and the cell [x, y] (attention! Not the cell that was passed to this function, but the cell that the algorithm went to in step 3):
    

     TREE *t=root; //   loopi(strlen(prefix)) //prefix     { int k=ind(prefix[i],t->str); t=t->next[k]; } find(t,x,y); 

• 2) Regardless of the value of tree->wrd continue
• 3) enumerating the cells adjacent to [i, j] (from 2 in the corner to 4 in the center of the field)
• 4) Analyze the contents of the current adjacent cell [i1, j1]
  
  • a. If it is empty, then go to step (3)
  • b. If the letter in this cell is not in tree->str , then go to step (3)
  • c. If count[i1, j1]==0 , then go to step (3)
  • d. Otherwise, go to step (5)
• 5) Among the tree->next[] we find the node tnext corresponding to the letter in [i1, j1]
• 6) Reduce the usage count[i1, j1] and call find for tnext and cells [i1, j1]
• 7) End of cycle by adjacent letters

Consider the work of the algorithm for the central cell on the example of the following position:

We put each letter from the string ”” into this cell (the remaining letters of the alphabet simply do not exist in root_inv->str and the algorithm for them will end quickly without even starting). For each letter, call find . For the letter function will end quickly, because in the inverted tree there are no branches beginning with -, - and - , the same is true for , , , -

For the remaining letters in the inverted tree, valid prefixes will be found:
– , – , – , – , – . For each prefix, we find a node in the dictionary tree (as described in item 1.b) and call the function find for it.
The prefix “” corresponds to the node root->next[0]->next[0]->next[0] :

The next adjacent letter may be or , but the str field of this node contains “” , so we immediately finish the find function, i.e. There are no branches in the tree starting at - and - . For the prefix “” in the dictionary tree there are no branches starting with -, -, -, - , -, -, -, - , the same is true for the prefixes “” and “” .

The prefix “” corresponds to the node root->next[0]->next[0]->next[2] .
Since wrd!=NULL field wrd!=NULL , put the wrd () string wrd () in the array of found words and continue the search further. For the and there are no branches, we complete the find function for them, but the line contained in the tree, we place it in the array of found words.

results

The algorithm was tested on the following field (of course, not on a test dictionary, but on a dictionary of 110,000 words):

This is a really played game.
Here, the field is 99 , and it is half filled (perhaps this is one of the worst positions for any algorithm, because there are quite a lot of cells where you can go, and quite a good mutual arrangement of letters, because of which many long words can be made). In the nodules mode, the algorithm finds all words in the following time:

• 1) Mac mini i7 - 7 milliseconds (not a native application, but in the iPhone emulator)
• 2) Comp. i5 - 12 milliseconds
• 3) iPad 4 - 30 milliseconds
• 4) Samsung Galaxy Ace (three years old iron) - 50 milliseconds (using NDK)

For other positions, the search time is even less.

application

This algorithm is applied in applications for iOS (available in the app store) and Android. In addition to the search for all words, two more types of search are implemented:

• 1) Local search - if the user desperately needs to occupy any particular empty cell (for example, a prize cell, or cover a cell with too many long words), then the program does double tap on this cell and the program searches only those words that can go into it
• 2) Checking the settings - double tap on a letter will force the program to find all the words passing through this letter. Application: immediately after the opponent's move, check his letter (all of a sudden, he was rigidly substituted), you should check the intended move for your turn

Another feature: the same length words are sorted according to the rarity of the added letter (for example, it is more profitable to go off the letter than the letter ).