Swype¹ and SwiftKey² are two virtual keyboard³ apps for touchscreen⁴ smartphones and tablets, where words are entered by sliding a finger or a stylus from the first letter of a word to its last letter, while passing through all intermediate letters of the word. This only requires lifting the finger or stylus in between words.

Assignment

A word $$w$$ is a string (str) that only contains lowercase letters (at least 3). The outside of $$w$$ is the concatenation of the first and last letter of $$w$$. The inside of $$w$$ is obtained by deleting the first and last letter of $$w$$. For example, the outside of the word quick is qk, and its inside is uic.

A word $$w_1$$ is a subword of word $$w_2$$ if it can be derived from $$w_2$$ by deleting some or no letters without changing the order of the remaining letters. For example, the word king is a subword of skintight. In addition, it is also allowed that repetitions of a letter in $$w_1$$ are mapped onto the same letter in $$w_2$$. As a result, the word queen is a subword of qxuyezn, despite the fact that the letter e only appears once in the second word.

A word $$w_1$$ is a wandering through word $$w_2$$ if i) its first letter equals the first letter of $$w_2$$, ii) its last letter equals the last letter of $$w_2$$ and iii) it is a subword of $$w_2$$.

A dictionary is a text file that contains a sequence of words, each on a separate line.

Your task:

• Write a function outside that takes a word $$w$$ (str) and returns the outside of $$w$$ (str).

• Write a function inside that takes a word $$w$$ (str) and returns the inside of $$w$$ (str).

• Write a function issubword that takes two words $$w_1$$ and $$w_2$$ (str). The function must return a Boolean value (bool) that indicates if $$w_1$$ is a subword of $$w_2$$.

• Write a function iswandering that takes two words $$w_1$$ and $$w_2$$ (str). The function must return a Boolean value (bool) that indicates if $$w_1$$ is a wandering through $$w_2$$.

• Write a function read_dictionary that takes the location (str) of a dictionary. The function must return a dict $$d$$ whose keys are the outsides (str) of all words in the given dictionary. The dict $$d$$ must map each outside onto the set of insides (str) of all words having that outside in the given dictionary.

• Write a function wanderings that takes two arguments: i) a word $$w$$ (str) and ii) a dict as returned by the function read_dictionary for a given dictionary. The function must return a set containing all words (str) from the given dictionary that are wanderings through $$w$$.

Example

In the following interactive session we assume the text file dictionary.txt⁵ to be located in the current directory.

>>> outside('quick')
'qk'
>>> outside('queen')
'qn'
>>> outside('king')
'kg'
>>> outside('win')
'wn'

>>> inside('quick')
'uic'
>>> inside('queen')
'uee'
>>> inside('king')
'in'
>>> inside('win')
'i'

>>> issubword('quick', 'qwertyuihgfcvbnhjk')
True
>>> issubword('win', 'qwertyuytresdftyuiokn')
True
>>> issubword('queen', 'qwertyuytresdftyuiokn')
True
>>> issubword('quick', 'qwertyuytresdftyuiokn')
False

>>> iswandering('quick', 'qwertyuihgfcvbnhjk')
True
>>> iswandering('win', 'qwertyuytresdftyuiokn')
False
>>> iswandering('queen', 'qwertyuytresdftyuiokn')
True
>>> iswandering('quick', 'qwertyuytresdftyuiokn')
False

>>> dictionary = read_dictionary('dictionary.txt6')
>>> dictionary['qk']
{'uir', 'uar', 'uarterdec', 'uac', 'uarterbac', 'uic'}
>>> dictionary['qn']
{'uotidia', 'uee', 'uestio', 'uicke'}
>>> dictionary['xx']
Traceback (most recent call last):
KeyError: 'xx'

>>> wanderings('qwertyuihgfcvbnhjk', dictionary)
{'quick'}
>>> wanderings('qwertyuytresdftyuiokn', dictionary)
{'queen', 'question'}
>>> wanderings('ghijakjthoijerjidsdfnokg', dictionary)
{'gating', 'geeing', 'goring', 'going', 'gathering'}
>>> wanderings('xkzjunspebfgslddfksdrx', dictionary)
set()

This figure shows why the word quick is a wandering through the letter sequence (top) given in the first example of the function wanderings.

This figure shows why the words queen and question are wanderings through the letter sequence (middle) given in the second example of the function wanderings. Note that the two consecutive letters e in the word queen both use the same letter e in the letter sequence.