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.

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.

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.

Opgave

Definieer een klasse Woordenboek waarmee zo lang mogelijke trechters kunnen gezocht worden in het netwerk van een gegeven verzameling woorden $$\mathcal{W}$$. Bij het aanmaken van objecten van de klasse Woordenboek moet de locatie van een tekstbestand doorgegeven worden, waarvan elke regel een uniek woord bevat. Deze woorden vormen de verzameling woorden $$\mathcal{W}$$ van het netwerk. Zorg ervoor dat de klasse Woordenboek minstens de volgende methoden ondersteunt:

• Een methode is_verbonden waaraan twee woorden $$w_1$$ en $$w_2$$ moeten doorgegeven worden. De methode moet een Booleaanse waarde teruggeven die aangeeft of woord $$w_1$$ verbonden is met woord $$w_2$$.

• Een methode verbindingen waaraan een woord $$w_1$$ moet doorgegeven worden. De methode moet een verzameling teruggegeven met alle woorden $$w_2 \in \mathcal{W}$$ die verbonden zijn met woord $$w_1$$. De woorden uit deze verzameling moeten in kleine letters weergegeven worden.

• Een methode is_trechter waaraan een reeks woorden (een lijst of een tuple) moet doorgegeven worden. De methode moet een Booleaanse waarde teruggeven die aangeeft of de gegeven reeks woorden een trechter is.

• Een methode langste_trechter waaraan een woord moet doorgegeven worden. De methode moet een lijst teruggeven met de woorden van een langste trechter die begint bij het gegeven woord. De woorden uit deze lijst moeten in kleine letters weergegeven worden en moeten allemaal behoren tot de verzameling $$\mathcal{W}$$.

Als aan één van deze methoden een woord $$w$$ doorgegeven wordt dat niet tot de verzameling $$\mathcal{W}$$ behoort, dan moet een AssertionError opgeworpen worden met de boodschap ongeldig woord: w. Kies het eerste woord als er meerdere woorden zijn (meerdere argumenten of een reeks woorden als argument) die niet tot de verzameling $$\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.txt')

>>> woordenboek.is_verbonden('DRIVER', 'river')
True
>>> woordenboek.is_verbonden('drivers', 'river')
False
>>> woordenboek.is_verbonden('river', 'driver')
False
>>> woordenboek.is_verbonden('Dragoon', 'dragon')
True
>>> woordenboek.is_verbonden('beast', 'stab')
False
>>> woordenboek.is_verbonden('brand', 'bad')
False
>>> woordenboek.is_verbonden('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.is_trechter(['coral', 'ORAL', 'Ora', 'or'])
True
>>> woordenboek.is_trechter(('composited', 'composied', 'composed', 'compose'))
Traceback (most recent call last):
AssertionError: onbekend woord: composied
>>> woordenboek.is_trechter(['turntables', 'turntable', 'tunable', 'unable'])
False
>>> woordenboek.is_trechter(('complecting', 'complecing', 'competing'))
Traceback (most recent call last):
AssertionError: onbekend woord: complecing
>>> woordenboek.is_trechter(['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