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.
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.
Bij onderstaande voorbeeldsessie gaan we ervan uit dat het tekstbestand zes-letter-woorden.txt1 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