# Swype Implementation

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.

A formal description of the task can be found here

——-

## The Solution

——-

For this I wrote a program in python. The program is twofold:

1. Create a group of smaller dictionaries to significantly reduce my searchspace
2. 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

——-

## The Code

the code can be found here

```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[0]+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')
```