# Understanding How To Approach A Permutational Word Search

This question is carried over from StackOverflow... First time posting here, so bear with me.

The topic is constructing a search made up of a given string, and a series of letters, where each of the letters individually mutates the string into all possible forms by prepending, substituting, and appending to the base string. The goal is a match of the mutated string in a dictionary, or as a substring that matches to a word in the dictionary.A further constraint regards white space preceding and following the found db match.

Easier to get the picture in context: the basic working code in Swift is at the end, with some efficiency code removed.

I have a game that uses a library of standard words, and a pool of up to 9 letters that the user has to play with. There is also a board, that contains 0-11 letters that have been placed by the player.

The game allows the player to only play one tile at a time, and only attached at either one end or the other of the letters on the board. When there are four or more letters on the board, they can also replace a letter already placed.

The key thing is that only letters combinations that either form a word, or a fragment of a word in the dictionary are permitted. So, some letters that the player has may be valid, because they can be used to form a word or fragment, composed of the letters on the board plus the letter. Others will not have a match, and be invalid choices to play.

In practice (the game is functional and on the App Store https://apps.apple.com/us/app/wordsby2/id1553717309 ), this means that I have a strategy for searching for legal combinations of letters. The form this takes is to form all the permutations of letters possible given the rules. This would always be formed of the existing board letters, and one letter from the user's rack of letters; by default, each letter in the player's pool is permitted through the base word on the board.

If Red is about to play, I generate all the combinations that can be formed with the letters on the board [J O I N], and all the unique letters in the rack of letters that Red has [R U E P O]. If it was Blue, Id substitute those for [M I O X A Z R].

The simpler problem is Red, because there are fewer letters. I would generate a word list like

RJOIN
JRIN
JORN
JOIR
JOINR
UJOIN
UOIN
JUIN
JOUN
JOIU
JOINU


, etc.

An extra caveat is, that I'm only interested in determining the board positions that can be played to. So, if I found that there was a word, or a word with a fragment "JORN", I would not need to do any subsequent searches for any letter that involved the third position in the word JOIN -> JO!N would be stored internally when that word or word fragment was found.

Complicating this is that if I don't find a complete word, then I have to be sure that the word the combination is a fragment of would fit in the 11 spaces on the board, not requiring any spaces off the board, so the search would be something like

**RJOIN*****
***JRIN*****
***JORN*****
***JOIR*****
***JOINR****
**UJOIN*****
***UOIN*****
***JUIN*****
***JOUN*****
***JOIU*****
***JOINU****


The current deployment is written in Swift, and uses CoreData, so basically SOLite. This is surprisingly quick, but there are searches that cause a momentary pause while the information is returned.

But we're contemplating a Web version, so we'll have the option to port the DB to Postgres (our default choice). Because our codebase is in Swift, any functions that have to performed on the back end will be lifted directly from the existing game, and run in Vapor.

This task is one that will definitely not be a browser side task, but I worry about what the compute costs and performance will be. So, obviously, the best thing to do is to optimize the DB searches now.

The current model works; the DB is a single-table so I don't think there are any magic indexes that will improve it.

Is there a standard way to deal with this kind of problem?

Here's the routine that does the base form of the search:

public func wordMatcher (pad: Int, word: Array<String>, substitutes : Set<String> ) -> Set<Int> {
//        scans db for any words currently possible using current word + 1 of the current rack lotters
openBoard(empty: true)
if word.count == 0 {
openBoard()
return lFreq
} // now we are dealing with non-zero length words, proceed
if substitutes.count == 0 {
return lFreq
} // now we have a non-zero length set of substitute letters, proceed
let context = CoreDataManager.shared.persistentContainer.viewContext
var pad_ = pad
var query: Array<String>
var predMatch: String
//        var foundPositions : Set<Int> = []
let rq: NSFetchRequest<Word> = Word.fetchRequest()
rq.fetchLimit = 1
let subs = "[\(substitutes.joined())]"
//        if word.count >= 4 { // because those locations will be blocked off anyway otherwise
let start = pad > 0 ? -1 : 0
let finish = 11 - (pad + word.count) > 0 ? word.count + 1 : word.count
for i in start..<finish {
query = word
var _pad = 11 - (pad + word.count)
if i == -1 {
query = Array(arrayLiteral: subs) + query
pad_ -= 1
} else if i >= word.count {
query.append(subs)
_pad -= 1
} else { // MARK: THIS IS PROBABLY NOT TESTING ALL INTERNAL POSITIONS
pad_ = pad
query[i] = subs
}
let endPad = _pad > 0 ? "[a-z]{0,\(_pad)}" : ""
let prePad = pad_ > 0 ? "[a-z]{0,\(pad_)}" : ""
predMatch = "^\(prePad)\(query.joined())\(endPad)"
//            print(predMatch)
rq.predicate = NSPredicate(format: "word MATCHES[cd] %@", predMatch)
do {
if try context.fetch(rq).count != 0 {
print("VALID: \(predMatch)")
lFreq.insert(i + pad)
}
} catch {
print("error searching")
}
//            }
}
print("lFreq is \(lFreq)")
if word.count < 4 {
clearWord(start: pad, length: word.count)
}
return lFreq
}

• In the “JOIN” example, don’t forget “ROIN” Commented Mar 9, 2022 at 9:15
• well, those word lists are manual examples. As the code shows, all permutations are automatically generated. Commented Mar 15, 2022 at 7:17

## 1 Answer

There are many ways to speed up a problem like this. You are asking for a server-side way, so it must be cheap in processing-time/energy-consuption. Fast response is a secondary goal.

## Precompute valid boards

The classic approach is static precomputation. For every word in your dictionary produce all combinations of letters replaced by blanks. All strings have the length of the original word. Then shift all of them to all possible positions in your 11-char board. This will result in a number of 11-char-strings roughly 400 times the size of your dictionary. Peanuts for a server. There you do a simple lookup for validity.

### Example

Your dictionary has two words {'a', 'as'} and your board is of size 3.

You get the combinations {'a', '#'} for 'a' and the combinations {'as', 'a#', '#s', '##'} for word 'as'.

Shifting inside the board results in 3 shifts for the one letter word 'a' ,resulting in at most 3x2=6 boards, where {'a##', '#a#', '##a', '###'} remain as the shifted blank word collapses to a single one. The two possible shifts for 'as' result in potentially 2x4=8 boards again collapsing partially to 7 entries.

The final set of valid boards for the whole dictionary has 8 entries as e.g. '#a#' is in both sets.

## Fast Response

For fast response on the client side you may query all possible next moves for the player immediately after a move. The lookup is cheap, the amount of data is small.

• Wrapping my head around this, is the problem that I'm also looking for fragments of words? taking a string like "and", that produces at the four letter word band, hand,land,sand,wand as valid words, each of which would have to exist in 7 positions, so the ratio is 35:1, roughly. But there are many words that contain "and" as a fragment, each of which would have to be accounted, potentially producing many hundreds more combinations, it seems to me, and that's for one three-letter combination. How does this work for word fragments? Commented Mar 15, 2022 at 7:15