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:

——-

The Task

——-

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')
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s