In de eerste aflevering van de animatiereeks Pokémon begon Ash Ketchum — een 10-jarige jongen uit Pallet Town — aan een wereldreis met één doel: de beste Pokémontrainer ter wereld te worden. In seizoen 25 ging die droom eindelijk in vervulling: met de hulp van zijn eerste Pokémon én tevens beste vriend Pikachu werd hij wereldkampioen.

Tijd voor iets nieuws dus, moeten de makers van de animatiereeks gedacht hebben. Ash en Pikachu mochten nog een ererondje lopen in de laatste afleveringen van seizoen 25, maar daarna moesten ze onherroepelijk plaats ruimen voor nieuwe protagonisten. Via de hashtag #ThankYouAshAndPikachu¹ deelden fans hun favoriete momenten uit de animatiereeks en bedankten ze het duo voor de mooie tijden.

Opgave

Als eerbetoon aan het onafscheidelijke duo Ash Ketchum en Pikachu uit de animatiereeks Pokémon hebben we het volgende geheimschrift bedacht. De sleutel van het geheimschrift wordt vastgelegd in een tekstbestand waarvan elke regel bestaat uit een unieke ID (een natuurlijk getal), gevolgd door een spatie en een unieke naam. Als voorbeeld gebruiken we deze toepasselijke sleutel met de volgnummers en namen van alle Pokémon uit de eerste 25 seizoenen van de animatiereeks (pokemon.txt²).

1 Bulbasaur
2 Ivysaur
3 Venusaur
4 Charmander
5 Charmeleon
6 Charizard
7 Squirtle
8 Wartortle
9 Blastoise
10 Caterpie
…

In het tekstbestand mogen namen naast letters ook nog spaties, cijfers, leestekens en andere karakters bevatten. Het geheimschrift werkt echter met de normaalvorm van de namen: de normaalvorm van een string $$s$$ (str) bestaat uit de opeenvolgende letters van $$s$$ die omgezet zijn naar hoofdletters. Zo is MRMIME de normaalvorm van Mr. Mime — de naam van de Pokémon met ID 122.

Om de klare tekst Thank you Ash and Pikachu te coderen, zetten we ook die eerst om naar zijn normaalvorm: THANKYOUASKANDPIKACHU. Dit is dus dezelfde normaalvorm die we zouden coderen voor de klare tekst #ThankYouAshAndPikachu.

Daarna zoeken we de Pokémon wiens naam een langste prefix gemeen heeft met de klare tekst (waarbij we zowel de normaalvorm gebruiken van de naam als van de klare tekst). In dit geval zijn er geen Pokémon waarvan de naam begint met THA, maar zijn er vier Pokémon waarvan de naam begint met TH: THROH (538), THUNDURUS (642), THWACKEY (811), en THIEVUL (828). De langste prefix die een Pokémon gemeen heeft met de klare tekst is dus TH, met lengte 2. Omdat er meerdere Pokémon zijn waarvan de naam een langste prefix gemeen heeft met de klare tekst, selecteren we de Pokémon wiens naam lexicografisch eerst komt: THIEVUL (828).

Deze prefix van de klare tekst wordt voorgesteld door de code #0828.2 die bestaat uit een hekje (#), gevolgd door de ID van de geselecteerde Pokémon (828), een punt (.) en de lengte van de langste prefix (2). De ID van de geselecteerde Pokémon wordt in de code aangevuld met voorloopnullen tot die uit minstens 4 cijfers bestaat.

Ten slotte verwijderen we de prefix van de klare tekst, zodat we nog ANKYOUASKANDPIKACHU overhouden. We blijven deze procedure herhalen tot we alle letters van de klare tekst omgezet hebben naar codes. Onderstaande tabel beschrijft de opeenvolgende stappen van de procedure voor het coderen van de klare tekst Thank you Ash and Pikachu. Daarbij hebben we telkens de lexicografisch eerste naam van de Pokémon die een langste prefix deelt met het resterende deel van de klare tekst in het vet gezet.

De cijfertekst bestaat dan uit de opeenvolgende codes die telkens van elkaar gescheiden worden door een spatie:

#0828.2 #0979.2 #0382.3 #0197.1 #0460.1 #0319.3 #0932.1 #0927.1 #0025.7

Definieer een klasse Cijfer waarmee berichten kunnen gecodeerd en gedecodeerd worden volgens het geheimschrift dat we hierboven beschreven hebben. Bij het aanmaken van een nieuw cijfer (Cijfer) moet de locatie (str) doorgegeven worden van het tekstbestand met de sleutel van het cijfer. Een cijfer $$c$$ (Cijfer) moet minstens de volgende methoden ondersteunen:

• Een methode naam waaraan een ID (int) moet doorgegeven worden. Als er volgens de sleutel van cijfer $$c$$ geen naam correspondeert met de gegeven id, dan moet de waarde None teruggeven worden. Anders moet de normaalvorm (str) van de corresponderende naam teruggegeven worden.

• Een methode decodeer waaraan de cijfertekst (str) moet doorgegeven worden van een klare tekst $$t$$ die met cijfer $$c$$ gecodeerd werd. De methode moet de normaalvorm (str) van de klare tekst $$t$$ teruggeven.

• Een methode langste_prefix waaraan een string $$t$$ (str) moet doorgegeven worden. De methode moet een tuple met twee elementen teruggeven: i) een verzameling (set) met alle ID's (int) in de sleutel van cijfer $$c$$ waarvan de normaalvormen van de corresponderende namen een langste prefix gemeen hebben met de normaalvorm van $$t$$, en ii) de lengte (int) van die langste prefix.

• Een methode codeer_prefix waaraan een string $$t$$ (str) moet doorgegeven worden. De methode moet een tuple met twee elementen teruggeven: i) de ID (int) in de sleutel van cijfer $$c$$ waarvan de normaalvorm van de naam de lexicografisch eerste normaalvorm is die een langste prefix gemeen heeft met de normaalvorm van $$t$$, en ii) de lengte (int) van die langste prefix.

• Een methode codeer waaraan een klare tekst $$t$$ (str) moet doorgegeven worden. De methode moet de cijfertekst (str) teruggeven die men bekomt door klare tekst $$t$$ te coderen met cijfer $$c$$.

Of het geheimschrift een klare tekst kan coderen, hangt af van de sleutel. Je mag er echter van uitgaan dat alle methoden van de klasse Cijfer een gegeven klare tekst kunnen coderen, zonder dat dit expliciet moet gecontroleerd worden.

Voorbeeld

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

>>> cijfer = Cijfer('pokemon.txt4')
>>> cijfer.naam(25)
'PIKACHU'
>>> cijfer.naam(83)
'FARFETCHD'
>>> cijfer.naam(474)
'PORYGONZ'
>>> cijfer.naam(538)
'THROH'
>>> cijfer.naam(642)
'THUNDURUS'
>>> cijfer.naam(811)
'THWACKEY'
>>> cijfer.naam(828)
'THIEVUL'
>>> cijfer.naam(994)
'IRONMOTH'
>>> cijfer.naam(1111)

>>> cijfer.decodeer('#0828.2 #0979.2 #0382.3 #0197.1 #0460.1 #0319.3 #0932.1 #0927.1 #0025.7')
'THANKYOUASHANDPIKACHU'

>>> cijfer.langste_prefix('Thank You Ash And Pikachu')
({538, 642, 811, 828}, 2)
>>> cijfer.langste_prefix('ANKYOUASHANDPIKACHU')
({347, 979}, 2)
>>> cijfer.langste_prefix('KYOUASHANDPIKACHU')
({382}, 3)

>>> cijfer.codeer_prefix('Thank You Ash And Pikachu')
(828, 2)
>>> cijfer.codeer_prefix('ANKYOUASHANDPIKACHU')
(979, 2)
>>> cijfer.codeer_prefix('KYOUASHANDPIKACHU')
(382, 3)

>>> cijfer.codeer('Thank You Ash And Pikachu')
'#0828.2 #0979.2 #0382.3 #0197.1 #0460.1 #0319.3 #0932.1 #0927.1 #0025.7'
>>> cijfer.codeer('#ThankYouAshAndPikachu')
'#0828.2 #0979.2 #0382.3 #0197.1 #0460.1 #0319.3 #0932.1 #0927.1 #0025.7'