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
}
