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.

Tenslotte 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

Gevraagd wordt:

• Schrijf een functie normaalvorm waaraan een string $$t$$ (str) moet doorgegeven worden. De functie moet de normaalvorm (str) van $$t$$ teruggeven.

• Schrijf een functie lees_sleutel waaraan de locatie (str) moet doorgegeven worden van een tekstbestand dat een sleutel van het geheimschrift beschrijft. De functie moet een dictionary (dict) teruggeven die elke ID (int) van de sleutel afbeeldt op de normaalvorm (str) van de corresponderende naam. We noemen dit resultaat de dictionaryvoorstelling van de sleutel.

• Schrijf een functie decodeer waaraan twee argumenten moeten doorgegeven worden: i) een cijfertekst (str) die bekomen werd door een klare tekst $$t$$ met het geheimschrift te coderen en ii) de dictionaryvoorstelling (dict) van de sleutel die bij het coderen gebruikt werd. De functie moet de normaalvorm (str) van klare tekst $$t$$ teruggeven.

• Schrijf een functie langste_gemeenschappelijke_prefix waaraan twee strings $$t_1$$ en $$t_2$$ (str) moeten doorgegeven worden. De functie moet de lengte (int) teruggeven van de langste prefix die $$t_1$$ en $$t_2$$ gemeen hebben.
  

• Schrijf een functie langste_prefix waaraan twee argumenten moeten doorgegeven worden: i) een string $$t$$ (str) en ii) de dictionaryvoorstelling (dict) van een sleutel $$s$$ voor het geheimschrift. De functie moet een tuple met twee elementen teruggeven: i) een verzameling (set) met alle ID's (int) uit sleutel $$s$$ 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.

• Schrijf een functie codeer_prefix waaraan twee argumenten moeten doorgegeven worden: i) een string $$t$$ (str) en ii) de dictionaryvoorstelling (dict) van een sleutel $$s$$ voor het geheimschrift. De functie moet een tuple met twee elementen teruggeven: i) de ID (int) uit sleutel $$s$$ 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.

• Schrijf een functie codeer waaraan twee argumenten moeten doorgegeven worden: i) een klare tekst $$t$$ (str) en ii) de dictionaryvoorstelling (dict) van een sleutel $$s$$ voor het geheimschrift. De functie moet de cijfertekst (str) teruggeven die men bekomt door klare tekst $$t$$ te coderen volgens het geheimschrift met sleutel $$s$$.

Of het geheimschrift effectief een klare tekst kan coderen, hangt af van de sleutel. Je mag er echter van uitgaan dat alle functies 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.

>>> normaalvorm('Thank You Ash And Pikachu')
'THANKYOUASHANDPIKACHU'
>>> normaalvorm('#ThankYouAshAndPikachu')
'THANKYOUASHANDPIKACHU'

>>> sleutel = lees_sleutel('pokemon.txt4')
>>> sleutel[25]
'PIKACHU'
>>> sleutel[83]
'FARFETCHD'
>>> sleutel[474]
'PORYGONZ'
>>> sleutel[538]
'THROH'
>>> sleutel[642]
'THUNDURUS'
>>> sleutel[811]
'THWACKEY'
>>> sleutel[828]
'THIEVUL'
>>> sleutel[994]
'IRONMOTH'
>>> sleutel[1111]
Traceback (most recent call last):
KeyError: 1111

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

>>> langste_gemeenschappelijke_prefix('THANKYOUASHANDPIKACHU', 'PIKACHU')
0
>>> langste_gemeenschappelijke_prefix('THANKYOUASHANDPIKACHU', 'THWAKEY')
2
>>> langste_gemeenschappelijke_prefix('ANKYOUASHANDPIKACHU', 'ANORITH')
2
>>> langste_gemeenschappelijke_prefix('KYOUASHANDPIKACHU', 'KYOGRE')
3

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

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

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