Submit All submissions Best solutions PDF Back to list

PROG0413 - Alphabetic encoding

Consider a string that contains all of the 26 letters of the alphabet just once, for example

jfbqpwcvuamozhilgrxtkndesy

This permutation can be used as the key in a substitution cipher, which in case of the above example maps the letter a onto the letter j, the letter b on the letter f, and so on. This key therefore encrypts the word bakery as fjmprs. Notice that the letters of the encrypted word fjmprs are in alphabetic order. The challenge is to find the permutation of letters of the alphabet, that for a given word list maximizes the number of words that are encrypted as words having their letters in alphabetic order.

Assignment

Your task is to write a program that can be used to determine the score of the above optimization problem for a given key and a given list of words. The score is computed as the number of words in the given list that is encrypted as words having their letters in alphabetic order. In order to do so, you have to implement the following functions:

  • Write a function validKey that takes a single argument. The function must return a boolean that indicates whether or not the passed argument is a valid key for a substitution cipher. The argument is valid if it is a string that contains a permutation of the (lowercase) letters of the alphabet.
  • Write a function encode that can be used to encrypt a given word (first argument) according to a substitution cipher using a given key (second argument). The function must return the encrypted word as its result. If the key that is passed to the function is invalid, the function must throw an AssertionError with the message invalid key.
  • Write a function hasAlphabeticOrder to which a word that only contains lowercase letters must be passed as a string argument. The function must return a Boolean value that indicates whether or not the letters of the word are in alphabetic order.
  • Write a function score that indicates how many words contained in a given text file have their letters in alphabetic order, after they are encrypted with a substitution cipher. Two arguments must be passed to the function: the key that is used in the substitution cipher, and the name of a text file that contains the list of words. In this file, each word is on a separate line and only consists of lowercase letters. If the key passed to the function is not valid, the function must throw an AssertionError with the message invalid key.

Example

In the following interactive session we assume the current directory to contain the text file six-letter-words.txt.

>>> validKey('jfbqpwcvuamozhilgrxtkndesy')
True
>>> validKey('jfbqpwcxvuamozhilgrxtkndesy')
False
>>> validKey('jfbqpwvuamozhilgrxtkndesy')
False
>>> validKey('jfbqpwxvuamozhilgrxtkndesy')
False

>>> encode('bakery', 'jfbqpwcvuamozhilgrxtkndesy')
'fjmprs'
>>> encode('butchery', 'jfbqpwcvuamozhilgrxtkndesy')
'fktbvprs'
>>> encode('bullet', 'jfbqpwcvuamozhilgrxtkndesy')
'fkoopt'
>>> encode('bakery', 'jfbqpwxvuamozhilgrxtkndesy')
Traceback (most recent call last):
AssertionError: invalid key

>>> hasAlphabeticOrder('bakery')
False
>>> hasAlphabeticOrder('fjmprs')
True
>>> hasAlphabeticOrder('bullet')
False
>>> hasAlphabeticOrder('fkoopt')
True

>>> score('jfbqpwcvuamozhilgrxtkndesy', 'six-letter-words.txt')
60
>>> score('idsxvaqtobuefpgcjwzrkmhnyl', 'six-letter-words.txt')
474

Beschouw een string die elk van de 26 letters van het alfabet juist één keer bevat, bijvoorbeeld

jfbqpwcvuamozhilgrxtkndesy

Deze permutatie kan gebruikt worden als de sleutel van een substitutiecodering, die in het geval van bovenstaand voorbeeld de letter a afbeeldt op de letter j, de letter b op de letter f, enzoverder. Deze sleutel codeert bijgevolg het woord bakker als fjmmpr. Merk hierbij op dat de letters van het gecodeerde woord fjmmpr in alfabetische volgorde staan. De uitdaging bestaat erin een permutatie van de letters van het alfabet te vinden, die een maximaal aantal woorden uit een gegeven woordenlijst codeert als woorden die in alfabetische volgorde staan.

Opgave

Je opdracht bestaat erin een programma te schrijven dat kan gebruikt worden om de score te bepalen van het bovenstaande optimalisatieprobleem voor een gegeven sleutel en een gegeven woordenlijst. De score wordt bepaald als het aantal woorden van de gegeven woordenlijst die gecodeerd worden als woorden waarvan de letters in alfabetische volgorde staan. Hiervoor ga je als volgt te werk:

  • Schrijf een functie geldigeSleutel waaraan één enkel argument moet doorgegeven worden. De functie moet een Booleaanse waarde teruggeven, die aangeeft of het argument een geldige sleutel is voor een substitutiecodering. Het argument is geldig als het een string is die een permutatie vormt van de (kleine) letters van het alfabet.
  • Schrijf een functie codeer waarmee een gegeven woord (eerste argument) kan gecodeerd worden volgens een substitutiecodering die gebruik maakt van de opgegeven sleutel (tweede argument). De functie moet het gecodeerde woord als resultaat teruggeven. Indien de opgegeven sleutel niet geldig is, dan moet de functie een AssertionError opwerpen met als boodschap ongeldige sleutel.
  • Schrijf een functie alfabetisch waaraan een woord bestaande uit kleine letters als stringargument moet doorgegeven worden. De functie moet een Booleaanse waarde teruggeven, die aangeeft of de letters van het gegeven woord in alfabetische volgorde staan of niet.
  • Schrijf een functie score die aangeeft hoeveel woorden uit een gegeven tekstbestand na substitutiecodering hun letters in alfabetische volgorde hebben staan. Aan de functie moeten twee argumenten doorgegeven worden: de sleutel die gebruikt wordt bij de substitutiecodering, en de bestandsnaam van een tekstbestand dat een lijst van woorden bevat. Elk woord staat daarbij op een afzonderlijke regel, en bestaat enkel uit kleine letters. Indien de opgegeven sleutel niet geldig is, moet de functie een AssertionError opwerpen met als boodschap ongeldige sleutel.

Voorbeeld

Bij onderstaande voorbeeldsessie gaan we ervan uit dat het tekstbestand zes-letter-woorden.txt zich in de huidige directory bevindt.

>>> geldigeSleutel('jfbqpwcvuamozhilgrxtkndesy')
True
>>> geldigeSleutel('jfbqpwcxvuamozhilgrxtkndesy')
False
>>> geldigeSleutel('jfbqpwvuamozhilgrxtkndesy')
False
>>> geldigeSleutel('jfbqpwxvuamozhilgrxtkndesy')
False
>>> geldigeSleutel(123456789)
False

>>> codeer('bakker', 'jfbqpwcvuamozhilgrxtkndesy')
'fjmmpr'
>>> codeer('slager', 'jfbqpwcvuamozhilgrxtkndesy')
'xojcpr'
>>> codeer('bullet', 'jfbqpwcvuamozhilgrxtkndesy')
'fkoopt'
>>> codeer('bakker', 'jfbqpwcvuamozhilgrxakndesy')
Traceback (most recent call last):
AssertionError: ongeldige sleutel

>>> alfabetisch('bakker')
False
>>> alfabetisch('fjmmpr')
True
>>> alfabetisch('bullet')
False
>>> alfabetisch('fkoopt')
True

>>> score('jfbqpwcvuamozhilgrxtkndesy', 'zes-letter-woorden.txt')
44
>>> score('idsxvaqtobuefpgcjwzrkmhnyl', 'zes-letter-woorden.txt')
172
Submit solution!
Added by:Peter Dawyndt
Date:2013-08-31
Time limit:20s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:PY_NBC
Resource:None
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.