Swype is a popular way to type on Android phones — it works by taking the unbroken path of the fingers over letters and surmising what word was intended. An example of a finger-path would be:
Using this I was tasked with creating a program that takes the output from a finger path and reports back possible words that both include all the letters in that order and start and end with the letters.
For this I wrote a program in python. The program is twofold:
- Create a group of smaller dictionaries to significantly reduce my searchspace
- Determine the dictionary of choice and find all words that fit the letter group
Working under the pretense that the word starts and ends on the first and last letter of the desired word this reduces the searchspace by 26^2, or 676 times. Since our dictionary is static the first task should only need to be run once to give us our subdictionaries. Task two is relatively simple, looking at each word in the dictionary and seeing if our letter string could possibly create it. There is a small setting to allow for double-letters (the challenge only wanted one set of double letters to be possible for some reason). The search times that I was getting are roughly equal to those of other solvers
import string def createDictionary(textFile): # i = first letter of word # j = last letter of word for i in string.ascii_lowercase: for j in string.ascii_lowercase: with open(textFile,'r') as ins: array =  for line in ins: #only write entry if it starts and ends with correct letter if (line.startswith(i) and line.endswith(j+"\n") and len(line)>= 6): array.append(line) f = open(i+j+".txt","w") f.writelines(array) f.close() ins.close() print("-done creating dictionary-") def searchDictionary(inputString): array =  with open(inputString+inputString[len(inputString)-1]+".txt",'r') as ins: #opens "qn.txt" for example if input string is "QIEIN". Its the organized dictionary from above for line in ins: temporaryInputString = inputString place = 0 letterCount = 1 doubleLetterUsed = 0 for letter in line: if place >= 0: #place will be -1 if it is unable to find it place = temporaryInputString.find(letter) if doubleLetterUsed == 2: temporaryInputString = temporaryInputString[place+1:] else: temporaryInputString = temporaryInputString[place:] if place == 0: doubleLetterUsed = doubleLetterUsed +1 letterCount = letterCount + 1 if letterCount == len(line): #effectively ignores the newline text at end... array.append(line) print(array) return array #createDictionary("dic.txt") searchDictionary('gijakjthoijerjidsdfnokg')