Swype en SwiftKey zijn twee virtual keyboard apps voor smartphones en tablets met aanraakschermen, die toelaten om woorden in te voeren door een vinger of een stylus van de eerste naar de laatste letter van elk woord te slepen, en onderweg over alle opeenvolgende letters van het woord te slepen. Op die manier moet de vinger of de stylus enkel tussen twee woorden opgetild worden.

Opgave

Een woord $$w$$ is een string (str) die enkel kleine letters bevat (minstens 3). De buitenkant van $$w$$ wordt gevormd door de aaneenschakeling van de eerste en de laatste letter van $$w$$. De binnenkant van $$w$$ wordt verkregen door de eerste en de laatste letter van $$w$$ te schrappen. Zo is de buitenkant van het woord quick bijvoorbeeld gelijk aan qk, en is de binnenkant van dat woord gelijk aan uic.

Een woord $$w_1$$ is een deelwoord van woord $$w_2$$ als het kan bekomen worden door letters uit $$w_2$$ te schrappen zonder de volgorde van de overblijvende letters te veranderen. Zo is king bijvoorbeeld een deelwoord van skintight. Bovendien is het ook toegelaten om opeenvolgende gelijke letters van $$w_1$$ op dezelfde letter van $$w_2$$ af te beelden. Op die manier is queen bijvoorbeeld toch een deelwoord van qxuyezn, ondanks het feit dat de letter e maar één keer voorkomt in het tweede woord.

Een woord $$w_1$$ is een wandeling door woord $$w_2$$ als i) zijn eerste letter gelijk is aan de eerste letter van $$w_2$$, ii) zijn laatste letter gelijk is aan de laatste letter van $$w_2$$ en iii) het een deelwoord is van $$w_2$$.

Een woordenboek is een tekstbestand met een reeks woorden die elk op een afzonderlijke regel staan.

Gevraagd wordt:

• Schrijf een functie buitenkant waaraan een woord $$w$$ (str) moeten doorgegeven worden. De functie moet de buitenkant van $$w$$ (str) teruggeven.

• Schrijf een functie binnenkant waaraan een woord $$w$$ (str) moeten doorgegeven worden. De functie moet de binnenkant van $$w$$ (str) teruggeven.

• Schrijf een functie isdeelwoord waaraan twee woorden $$w_1$$ en $$w_2$$ (str) moeten doorgegeven worden. De functie moet een Booleaanse waarde (bool) teruggeven die aangeeft of $$w_1$$ een deelwoord is van $$w_2$$.

• Schrijf een functie iswandeling waaraan twee woorden $$w_1$$ en $$w_2$$ (str) moeten doorgegeven worden. De functie moet een Booleaanse waarde (bool) teruggeven die aangeeft of $$w_1$$ een wandeling is door $$w_2$$.

• Schrijf een functie woordenboek_inlezen waaraan de locatie (str) van een woordenboek moet doorgegeven worden. De functie moet een dictionary $$d$$ (dict) teruggeven waarvan de sleutels gevormd worden door de buitenkanten (str) van alle woorden uit het gegeven woordenboek. Elke buitenkant moet door $$d$$ afgebeeld worden op de verzameling (set) van binnenkanten (str) van alle woorden in het woordenboek die die buitenkant hebben.

• Schrijf een functie wandelingen waaraan twee argumenten moeten doorgegeven worden: i) een woord $$w$$ (str) en ii) een dictionary (dict) zoals die voor een woordenboek wordt teruggegeven door de functie woordenboek_inlezen. De functie moet een verzameling (set) teruggeven met alle woorden (str) uit het woordenboek die wandelingen zijn door $$w$$.

Voorbeeld

In onderstaande voorbeeldsessie gaan we ervan uit dat het tekstbestand woordenboek.txt zich in de huidige directory bevindt.

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

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

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

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

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

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

Onderstaande figuur toont waarom het woord quick een wandeling is door de gegeven reeks letters (bovenaan) in het eerste voorbeeld van de functie wandelingen.

Onderstaande figuur toont waarom de woorden queen en question wandelingen zijn door de gegeven reeks letters (midden) in het tweede voorbeeld van de functie wandelingen. Let hierbij op het feit dat de twee opeenvolgende letters e in het woord queen alletwee gebruikmaken van dezelfde letter e in de reeks letters.