Welk beroep zit verborgen in deze lijst van woorden?
CALCIUM, MALCHANCE, BROCHETTE, KOORHEMD, FEMINIST, TIRAMISU, AMETHIST
Het beroep dat we zochten is ALCHEMIST. We hebben de woordenlijst samengesteld door eerst de opeenvolgende $$n$$-grammen van het woord ALCHEMIST te bepalen voor een zekere $$n \in \mathbb{N}$$ (met $$n > 1$$). Voor $$n = 3$$ krijgen we bijvoorbeeld de volgende $$n$$-grammen:
ALC, LCH, CHE, HEM, EMI, MIS, IST
Daarna vervangen we elk $$n$$-gram door een woord waarin het $$n$$-gram voorkomt.
CALCIUM, MALCHANCE, BROCHETTE, KOORHEMD, FEMINIST, TIRAMISU, AMETHIST
Daarbij zorgen we er ook voor dat de prefix die bestaat uit de eerste $$n - 1$$ letters van elk $$n$$-gram slechts één keer in het woord voorkomt. Zo zal het $$n$$-gram CHE bijvoorbeeld nooit vervangen worden door het woord SCHERPSCHUTTER waarin de prefix CH zowel gevolgd wordt door de letter E als door de letter U.
Als we dan weten dat ALC het $$n$$-gram uit het eerste woord is, dan weten we meteen ook dat de suffix die bestaat uit de laatste $$n - 1$$ letters van het $$n$$-gram (LC) slechts één keer in het tweede woord voorkomt. Daarom vormt de letter die in het tweede woord volgt op die suffix (H) de volgende letter van het beroep.
CALCIUM, MALCHANCE, BROCHETTE, KOORHEMD, FEMINIST, TIRAMISU, AMETHIST
Nu we weten dat LCH het $$n$$-gram uit het tweede woord is, kunnen we op dezelfde manier met het derde woord de volgende letter van het beroep bepalen. We weten immers dat de suffix die bestaat uit de laatste $$n - 1$$ letters van het $$n$$-gram (CH) slechts één keer in het derde woord voorkomt. De letter die in het derde woord volgt op die suffix (E) vormt de volgende letter van het beroep.
Analoog kunnen we met de volgende woorden telkens de volgende letter van het beroep bepalen.
Opgave
Een woord wordt voorgesteld als een string (str) die enkel bestaat uit letters. Een woordenlijst wordt voorgesteld als een reeks (list of tuple) van woorden.
Zoek het beroep dat we in een gegeven woordenlijst verborgen hebben op de manier zoals beschreven in de inleiding. Hiervoor ga je als volgt te werk:
-
Schrijf een functie volgende_letter waaraan twee woorden $$v$$ en $$w$$ moeten doorgegeven worden. Als $$v$$ juist één keer voorkomt in $$w$$ en als $$v$$ geen suffix is van $$w$$, dan moet de letter (str) teruggegeven worden die in $$w$$ volgt op $$v$$. Anders moet de lege string (str) teruggegeven worden.
-
Schrijf een functie uitbreiden waaraan een woord $$p$$ en een woordenlijst $$W^{-}$$ moeten doorgegeven worden. Het woord $$p$$ is het eerste $$n$$-gram ($$n > 1$$) van een beroep dat we in een woordenlijst $$W$$ verborgen hebben. De woordenlijst $$W^{-}$$ is de woordenlijst $$W$$ zonder het eerste woord. Als in de woorden van $$W^{-}$$ telkens een volgende letter kan teruggevonden worden, dan moet het verborgen beroep (str) teruggegeven worden. Anders moet de lege string (str) teruggegeven worden.
-
Schrijf een functie beroep waaraan een woordenlijst $$W$$ moet doorgegeven worden waarin we een beroep verborgen hebben. De functie heeft ook nog een optionele parameter lengte (int; standaardwaarde: 2) waaraan de lengte $$n$$ kan doorgegeven worden van de $$n$$-grammen waarmee we de woordenlijst samengesteld hebben. Elk $$n$$-gram van het eerste woord in $$W$$ kan het eerste $$n$$-gram van het verborgen beroep zijn. Als met één van die $$n$$-grammen ook telkens een volgende letter kan teruggevonden worden in de volgende woorden van $$W$$, dan moet het daarmee gevormde woord (str) als het verborgen beroep teruggegeven worden. Anders moet de lege string (str) teruggegeven worden.
Geen enkele van deze functies mag onderscheid maken tussen hoofdletters en kleine letters bij het verwerken van de woorden die eraan doorgegeven worden. Bovendien moeten de strings (str) die ze teruggeven telkens in hoofdletters staan.
Voorbeeld
>>> volgende_letter('a', 'ZESJARIGE')
'R'
>>> volgende_letter('LC', 'malchance')
'H'
>>> volgende_letter('ank', 'Yankee')
'E'
>>> volgende_letter('EURO', 'DOLLAR')
''
>>> volgende_letter('LF', 'ALFALFA')
''
>>> volgende_letter('HUT', 'BOOMHUT')
''
>>> uitbreiden('Pa', ['ZESJARIGE', 'POKERFACE', 'FUCHSIA', 'ORATORIUM', 'SMETVRIJ', 'GLORIEUS', 'NATURISME'])
'PARFUMEUR'
>>> uitbreiden('ALC', ['malchance', 'brochette', 'koorhemd', 'feminist', 'tiramisu', 'amethist'])
'ALCHEMIST'
>>> uitbreiden('ijsb', ['Yankee', 'Blanket', 'Basketbal', 'Voetbal', 'Stortbak', 'Slabakken', 'Makker', 'Lekkerbek'])
''
>>> beroep(['ZEGEPALM', 'ZESJARIGE', 'POKERFACE', 'FUCHSIA', 'ORATORIUM', 'SMETVRIJ', 'GLORIEUS', 'NATURISME'])
'PARFUMEUR'
>>> beroep(['calcium', 'malchance', 'brochette', 'koorhemd', 'feminist', 'tiramisu', 'amethist'], lengte=3)
'ALCHEMIST'
>>> beroep(['IJsbank', 'Yankee', 'Blanket', 'Basketbal', 'Voetbal', 'Stortbak', 'Slabakken', 'Makker', 'Lekkerbek'], 4)
'BANKETBAKKER'
Epiloog: gekleed voor het werk
Het boek Fantastic Costumes of Trades & Professions (1695) van de Parijse graveur Nicolas de Larmessin bevat werklieden gekleed in voorwerpen die gerelateerd zijn aan hun beroep.
