In the first episode of the Pokémon animated series, Ash Ketchum — a 10-year-old boy from Pallet Town — embarked on a epic journey with one goal: to become the best Pokémon trainer in the world. In season 25, that dream finally came true: with the help of his first Pokémon and best friend Pikachu, he became world champion.

Time for something new, the creators of the animated series must have thought. Ash and Pikachu could run their lap of honor in the last episode of season 25, but then they irrevocably had to make way for new protagonists. Fans shared their favorite moments from the animated series and thanked the duo for all the good times using the hashtag #ThankYouAshAndPikachu¹.

Assignment

As a tribute to the inseparable duo Ash Ketchum and Pikachu from the animated series Pokémon, we've come up with the following cipher. The cipher's key is specified in a text file, with each line containing a unique ID (an integer), followed by a space and a unique name. As an appropriate example, we'll use this key with serial numbers and names of all Pokémon from the first 25 seasons of the animated series (pokemon.txt²).

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

In the text file, names may contain spaces, digits, punctuation and other characters in addition to letters. However, the cipher uses the normal form of the names: the normal form of a string $$s$$ (str) consists of the successive letters of $$s$$ that have been converted to uppercase. For example, MRMIME is the normal form of Mr. Mime — the name of the Pokémon with ID 122.

To encode the plaintext Thank you Ash and Pikachu, it is also first converted into its normal form: THANKYOUASKANDPIKACHU. This is the same normal form we would encode for the plaintext #ThankYouAshAndPikachu.

Then we find the Pokémon whose name has a longest prefix in common with the plaintext (using both the normal form of the name and the plaintext). In this case, there are no Pokémon whose name begins with THA, but there are four Pokémon whose name begins with TH: THROH (538), THUNDURUS (642), THWACKEY (811), and THIEVUL (828). Thus, the longest prefix a Pokémon has in common with the plaintext is TH, with length 2. Since there are multiple Pokémon whose name has a longest prefix in common with the plaintext, we select the Pokémon whose name comes first lexicographically: THIEVUL (828).

This prefix of the plaintext is represented by the code #0828.2 which consists of a hashtag (#), followed by the ID of the selected Pokémon (828), a dot (.) and the length of the longest prefix (2). In the code, the ID of the selected Pokémon is prefixed with leading zeros until it consists of at least 4 digits.

Finally, we remove the prefix from the plaintext, leaving ANKYOUASKANDPIKACHU. We keep repeating this procedure until we have converted all letters of the plaintext into codes. The table below describes the sequential steps of the procedure for encoding the plaintext Thank you Ash and Pikachu. For each step, we have marked the lexicographically first name of the Pokémon who shares a longest prefix with the remainder of the plaintext in bold.

The ciphertext then consists of the consecutive codes, each separated by a space:

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

Define a class Cipher that can be used to encode and decode messages according to the cipher described above. The location (str) of a text file containing the cipher's key must be passed when creating a new cipher (Cipher). A cipher $$c$$ (Cipher) must at least support the following methods:

• A method name that takes an ID (int). The method must return the value None if the given ID does not occur in the key of cipher $$c$$. Otherwise, the normal form (str) of the corresponding name must be returned.

• A method decode that takes the ciphertext (str) resulting from encoding a plaintext $$t$$ with cipher $$c$$. The method must return the normal form (str) of plaintext $$t$$.

• A method longest_prefix that takes a string $$t$$ (str). The method must return a tuple with two elements: i) a set containing all IDs (int) in the key of cipher $$c$$ whose normal forms of the corresponding names have a longest prefix in common with the normal form of $$t$$, and ii) the length (int) of that longest prefix.

• A method encode_prefix that takes a string $$t$$ (str). The method must return a tuple with two elements: i) the ID (int) in the key of cipher $$c$$ whose name's normal form is the lexicographically first normal form that has a longest prefix in common with the normal form of $$t$$, and ii) the length (int) of that longest prefix.

• A method encode that takes a plaintext $$t$$ (str). The method must return the ciphertext (str) obtained by encoding plaintext $$t$$ with cipher $$c$$.

Whether the cipher can effectively encode a plaintext depends on the key. However, you may assume that all methods can encode a given plaintext, without the need to check this explicitly.

Example

This interactive session assumes that the current directory contains the text file pokemon.txt³.

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

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

>>> cipher.longest_prefix('Thank You Ash And Pikachu') # doctest: +SKIP
({538, 642, 811, 828}, 2)
>>> cipher.longest_prefix('ANKYOUASHANDPIKACHU') # doctest: +SKIP
({347, 979}, 2)
>>> cipher.longest_prefix('KYOUASHANDPIKACHU') # doctest: +SKIP
({382}, 3)

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

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