Een woord is een string die enkel bestaat uit letters. Bij het vergelijken van woorden maken we geen onderscheid tussen hoofdletters en kleine letters. Het bestand woorden.txt¹ bevat alle woorden uit een Engels woordenboek, waarbij elk woord op een afzonderlijke regel staat.

Een woord $$w_1$$ is verbonden met een woord $$w_2$$ als $$w_2$$ kan bekomen worden door één enkele letter te schrappen uit $$w_1$$. Daarbij moeten alle letters die niet geschrapt worden op hun plaats blijven staan. Op die manier ontstaat een netwerk van woorden die met elkaar verbonden zijn, waarvan we hieronder slechts een klein deeltje tonen. We kunnen nu verschillende eigenschappen van dit netwerk onderzoeken.

Twee woorden worden met elkaar verbonden als het tweede woord kan bekomen worden door uit het eerste woord één enkele letter te schrappen.

Met welk woord zijn er het meest woorden verbonden? Er zijn 28 woorden waarmee vijf andere woorden verbonden zijn (allemaal meervoudsvormen of werkwoordsvormen die eindigen op de letter s) en er is geen enkel woord waarmee meer dan vijf andere woorden verbonden zijn. Zo zijn er bijvoorbeeld vijf woorden verbonden met het woord drivers: divers, driers, driver, drives en rivers.

Een trechter is een reeks woorden waarvan de opeenvolgende woorden met elkaar verbonden zijn. Wat is dan de langste trechter die kan gevormd worden als we beginnen bij een gegeven woord? Voor het woord turntables is dat een trechter die bestaat uit 5 woorden.

De langste trechter die begint bij het woord turntables.

Met welk woord zouden we moeten beginnen om de trechter zo lang mogelijk te maken? Dat woord blijkt uniek te zijn: deze trechter die begint bij het woord complecting is met 10 woorden het langst.

De langste trechter begint bij het woord complecting.

Opgave

Definieer een klasse Woordenboek waarmee zo lang mogelijke trechters kunnen gezocht worden in een netwerk van woorden. Bij het aanmaken van een nieuw woordenboek (Woordenboek) moet de locatie (str) van een tekstbestand doorgegeven worden, waarvan elke regel een uniek woord bevat. Deze woorden vormen de woorden van het netwerk.

Op een woordenboek $$\mathcal{W}$$ (Woordenboek) moet je minstens de volgende methoden kunnen aanroepen, die geen onderscheid mogen maken tussen hoofdletters en kleine letters bij het vergelijken van woorden:

Een methode isverbonden waaraan twee woorden $$w_1$$ en $$w_2$$ (str) moeten doorgegeven worden. De methode moet een Booleaanse waarde (bool) teruggeven die aangeeft of woord $$w_1$$ verbonden is met woord $$w_2$$ in het netwerk van woordenboek $$\mathcal{W}$$.
Een methode verbindingen waaraan een woord $$w$$ (str) moet doorgegeven worden. De methode moet een verzameling (set) teruggeven met alle woorden (str) die verbonden zijn met woord $$w$$ in het netwerk van woordenboek $$\mathcal{W}$$. De woorden uit deze verzameling moeten in kleine letters weergegeven worden.
Een methode istrechter waaraan een reeks (list of tuple) met woorden (str) moet doorgegeven worden. De methode moet een Booleaanse waarde (bool) teruggeven, die aangeeft of de reeks woorden een trechter vormt voor woordenboek $$\mathcal{W}$$.
Een methode langste_trechter waaraan een woord $$w$$ (str) moet doorgegeven worden. De methode moet een lijst (list) teruggeven met de woorden (str) van een langste trechter die begint bij woord $$w$$. De woorden van deze trechter moeten in kleine letters weergegeven worden en moeten allemaal behoren tot woordenboek $$\mathcal{W}$$.

Als aan één van deze methoden een woord $$w$$ wordt doorgegeven dat niet tot woordenboek $$\mathcal{W}$$ behoort, dan moet een AssertionError opgeworpen worden met de boodschap ongeldig woord: w. Kies het eerste woord als er meerdere woorden doorgegeven worden (meerdere argumenten of een reeks woorden als argument) die niet tot woordenboek $$\mathcal{W}$$ behoren.

Voorbeeld

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

        >>> woordenboek = Woordenboek('woorden.txt3')

>>> woordenboek.isverbonden('DRIVER', 'river')
True
>>> woordenboek.isverbonden('drivers', 'river')
False
>>> woordenboek.isverbonden('river', 'driver')
False
>>> woordenboek.isverbonden('Dragoon', 'dragon')
True
>>> woordenboek.isverbonden('beast', 'stab')
False
>>> woordenboek.isverbonden('brand', 'bad')
False
>>> woordenboek.isverbonden('shrubbery', 'spam')
Traceback (most recent call last):
AssertionError: onbekend woord: spam

>>> woordenboek.verbindingen('four')
{'our', 'for', 'fou', 'fur'}
>>> woordenboek.verbindingen('CLAMPS')
{'clams', 'clamp', 'claps', 'camps', 'lamps'}
>>> woordenboek.verbindingen('Drivers')
{'drives', 'rivers', 'divers', 'driers', 'driver'}
>>> woordenboek.verbindingen('tallyman')
set()
>>> woordenboek.verbindingen('Spam')
Traceback (most recent call last):
AssertionError: onbekend woord: Spam

>>> woordenboek.istrechter(['coral', 'ORAL', 'Ora', 'or'])
True
>>> woordenboek.istrechter(('composited', 'composied', 'composed', 'compose'))
Traceback (most recent call last):
AssertionError: onbekend woord: composied
>>> woordenboek.istrechter(['turntables', 'turntable', 'tunable', 'unable'])
False
>>> woordenboek.istrechter(('complecting', 'complecing', 'competing'))
Traceback (most recent call last):
AssertionError: onbekend woord: complecing
>>> woordenboek.istrechter(['shrubbery', 'eggs', 'bacon', 'spam'])
Traceback (most recent call last):
AssertionError: onbekend woord: spam

>>> woordenboek.langste_trechter('coral')
['coral', 'oral', 'ora', 'or']
>>> woordenboek.langste_trechter('DEPRIVING')
['depriving', 'deriving', 'driving', 'diving']
>>> woordenboek.langste_trechter('Implosive')
['implosive']
>>> woordenboek.langste_trechter('turntables')
['turntables', 'turntable', 'turnable', 'tunable', 'unable']
>>> woordenboek.langste_trechter('composited')
['composited', 'composted', 'composed', 'compose', 'compos', 'compo', 'comp', 'cop', 'op']
>>> woordenboek.langste_trechter('PROGRAMMER')
['programmer', 'programer']
>>> woordenboek.langste_trechter('complecting')
['complecting', 'completing', 'competing', 'compting', 'comping', 'coping', 'oping', 'ping', 'pig', 'pi']
>>> woordenboek.langste_trechter('SPAM')
Traceback (most recent call last):
AssertionError: onbekend woord: SPAM

Opgave

Voorbeeld

Epiloog