Caesar op orde

In deze opgave ga je een aantal functies schrijven met behulp van functioneel programmeren, dat wil zeggen, conditionele statements, recursie en/of list comprehensions. Je herhaalt er de stof van week 3 en 4: recursie, use it or lose it en key=.

Zorg bij elke opdracht dat je de naam precies zo schrijft zoals dit wordt opgegeven, inclusief hoofd-en kleine letters. Voeg verder aan elke functie een docstring toe waar je kort uitlegt wat de argumenten van de functie zijn en wat de functie doet.

De functie encipher(s, n)

Schrijf een functie encipher(s, n) die als argumenten een string s en een (niet negatieve) integer n met een waarde tussen 0 en 25 verwacht. De functie encipher moet een nieuwe string teruggeven waarin de letters in s met n letters voorwaarts zijn “geroteerd” in het alfabet, en terug naar het begin van het alfabet als dat nodig is.

Bij dit probleem mag je ervan uitgaan dat hoofdletters “geroteerd” worden naar hoofdletters, kleine letters naar kleine letters en dat alle andere tekens niet veranderd worden. Als we bijvoorbeeld de letter 'y' 3 posities willen verschuiven, krijgen we de 'b' en als we de letter 'Y' 3 posities willen verschuiven krijgen we 'B'.

Karakters in het alfabet

In Python kan je de test if "a" <= c <= "z": gebruiken om te controleren of een karakter c tussen de 'a' en 'z' in het alfabet zit.

Je mag encipher schrijven hoe je wilt, mits je functioneel programmeren gebruikt. Je mag dus elke combinatie van conditionele statements, recursie en list comprehensions gebruiken.

We raden je aan een hulpfunctie te schrijven die een enkel karakter n plaatsen roteert, terug naar het begin als dat nodig is. Deze hulpfunctie zou je kunnen gebruiken om de karakters in de string één voor één te versleutelen. Je moet zelf bepalen hoe je dat doet!

Een hulpfunctie rot(c, n)

Schrijf een functie rot(c, n) die een enkel karakter c n plaatsen voorwaarts roteert in het alfabet.

Bedenk dat je soms terug naar het begin van het alfabet moet en dat tekens die geen letter zijn niet veranderen. Controleer vervolgens met assert statements of de functie rot(c, n) werkt:

assert rot("a", 2) == "c"
assert rot("y", 2) == "a"
assert rot("A", 3) == "D"
assert rot("Y", 3) == "B"
assert rot(" ", 4) == " "

Bedenk verder dat je de ingebouwde functies ord en chr die een string met één karakter omzetten naar een integer en omgekeerd kan gebruiken bij het roteren:

• ord('a') geeft bijvoorbeeld 97 terug

• … en chr(97) geeft 'a' terug.

Als je de tip volgt en een hulpfunctie rot(c, n) schrijft, dan heb je twee mogelijkheden:

• je kan met behulp van rot(c, n) een string letter voor letter recursief doorlopen, met de lege string als basisgeval.

• je kan ook list comprehensions gebruiken om rot(c, n) meerdere keren toe te passen.

  [rot(c, n) for c in ...]
  

• als je een list comprehension gebruikt, kan je onderstaande functie list_to_str gebruiken om er weer een string van te maken!

  def list_to_str(L):
      """Geeft de tekens uit de lijst L aan elkaar geplakt als één string."""
      if len(L) == 0:
          return ""
      return L[0] + list_to_str(L[1:])
  
  
  assert list_to_str(["h", "a", "n", "z", "e"]) == "hanze"
  

Hoe je encipher ook schrijft, zorg dat je de functie test! Hier is een begin:

assert encipher("xyza", 1) == "yzab"
assert encipher("Z A", 1) == "A B"

Hier zijn wat meer voorbeelden, we raden je aan deze om te zetten in assert statements en aan jouw tests toe te voegen:

In [1]: encipher('xyza', 1)
Out[1]: 'yzab'

In [2]: encipher('Z A', 1)
Out[2]: 'A B'

In [3]: encipher('*ab?', 1)
Out[3]: '*bc?'

In [4]: encipher('Dit is een string!', 1)
Out[4]: 'Eju jt ffo tusjoh!'

In [5]: encipher('Caesarcijfer? Ik heb liever Caesarsalade.', 25)
Out[5]: 'Bzdrzqbhiedq? Hj gda khdudq Bzdrzqrzkzcd.'

Tot slot, onthoud dat:

• Hoofdletters altijd hoofdletters blijven.

• Kleine letters altijd kleine letters blijven.

• Andere tekens helemaal niet veranderen!

De functie decipher(s)

Omgekeerd krijgt decipher(s) een string s met een (Nederlandstalige) tekst die al versleuteld is. De functie decipher moet, voorzover mogelijk, de originele tekst teruggeven, dit zal een rotatie (mogelijk ook 0) zijn van het argument s.

Wees bewust dat sommige strings meer dan één “ontsleuteling” kunnen hebben. Bovendien is het moeilijk of soms zelfs onmogelijk om hele korte strings goed te ontsleutelen. De functie decipher hoeft dus ook niet perfect te zijn, maar moet wel vrijwel altijd werken met langere stukken Nederlandse tekst, bijvoorbeeld zinnen van 8 of meer woorden. Het is dus geen probleem als een enkel woord of een korte zin niet goed worden ontsleuteld.

Alle rotaties, en dan de beste

Het is handig om te beginnen met het genereren van alle mogelijke ontsleutelingen, bijvoorbeeld via:

L = [... for n in range(26)]

Geef daarna elke rotatie in L een score die zegt hoe Nederlands ze eruitziet, en kies de rotatie met de hoogste score. Dat kan in één regel met max en key=, zoals in het tweede college van deze week:

max(L, key=...)

Achter key= zet je een functie die bij een string zijn score teruggeeft. Dat lijkt op best_word uit de basisopgave van week 3, die het woord met de hoogste Scrabble-score zocht.

Een mogelijke aanpak is het gebruik van letterfrequenties, hieronder is een functie gegeven met de frequenties per letter en deze kan je gebruiken in de opgave. Je zou ook Scrabble scores kunnen proberen (want deze zijn ook gebaseerd op letterfrequenties). Je mag zelf extra heuristieken (“vuistregels”) bedenken en verder mag je ook kleine hulpfuncties toevoegen om te helpen met het schrijven van decipher.

Hoe je het ook aanpakt, onthoud dat je de strategie die je gebruikt bij het schrijven van de functie decipher moet documenteren in een kort stukje commentaar boven de functie decipher.

Enkele voorbeelden van decipher:

In [1]: decipher('Bzdrzqbhiedq? Hj gda khdudq Bzdrzqrzkzcd.')
Out[1]: 'Caesarcijfer? Ik heb liever Caesarsalade.'

In [2]: decipher('Aadxas ue exqotfe pq haadflqffuzs hmz baxufuqw yqf mzpqdq yuppqxqz.')
Out[2]: 'Oorlog is slechts de voortzetting van politiek met andere middelen.'

In [3]: decipher('Lvkeg lvyon')
Out[3]: 'Tdsmo tdgwv'  # Dit is fout! Maar is hier geen probleem...

Ook hier raden we jou aan om de eerste twee voorbeelden om te zetten naar assert statements. Het derde voorbeeld niet: welke foute uitkomst je bij zo’n korte zin krijgt, hangt af van hoe je de score berekent. Met een andere score kan daar iets anders uitkomen, en ook dat is geen probleem.

Merk verder op dat het laatste voorbeeld laat zien dat onze ontsleutelaar het niet goed doet bij sommige korte zinnen. Dit is geen probleem! Naarmate de zinnen langer worden, moet de ontsleutelaar er steeds meer goed hebben, maar hij hoeft enkele woorden of korte zinnen niet goed te hebben, want voor korte strings zijn er zeer waarschijnlijk rotaties met meer “Nederlandsige” letters dan het origineel!

Hier is een functie om de kans per letter te bepalen:

# tabel met kansen per letter
def letter_prob(c):
    """Geeft de kans op letter c in Nederlandse tekst, of 1.0 als c geen letter is.

    Hoofdletters tellen als kleine letters. Bewerkt naar
    https://www.sttmedia.com/characterfrequency-nederlands
    """
    if c == "e" or c == "E":
        return 0.1909
    if c == "n" or c == "N":
        return 0.0991
    if c == "a" or c == "A":
        return 0.0769
    if c == "t" or c == "T":
        return 0.0642
    if c == "i" or c == "I":
        return 0.0630
    if c == "o" or c == "O":
        return 0.0581
    if c == "r" or c == "R":
        return 0.0562
    if c == "d" or c == "D":
        return 0.0541
    if c == "s" or c == "S":
        return 0.0384
    if c == "l" or c == "L":
        return 0.0380
    if c == "h" or c == "H":
        return 0.0312
    if c == "g" or c == "G":
        return 0.0312
    if c == "k" or c == "K":
        return 0.0279
    if c == "m" or c == "M":
        return 0.0256
    if c == "v" or c == "V":
        return 0.0224
    if c == "u" or c == "U":
        return 0.0212
    if c == "j" or c == "J":
        return 0.0182
    if c == "w" or c == "W":
        return 0.0172
    if c == "z" or c == "Z":
        return 0.0160
    if c == "p" or c == "P":
        return 0.0149
    if c == "b" or c == "B":
        return 0.0136
    if c == "c" or c == "C":
        return 0.0130
    if c == "f" or c == "F":
        return 0.0073
    if c == "y" or c == "Y":
        return 0.0006
    if c == "x" or c == "X":
        return 0.0005
    if c == "q" or c == "Q":
        return 0.0001
    return 1.0

Beslissingen

Voor decipher zal jouw programma alle 26 mogelijke rotaties van de string s die als argument is meegegeven moeten “bekijken” en dan beslissen welke de “beste” is…

De functie blsort(L)

Schrijf een functie blsort(L) die als argument een lijst L accepteert en een lijst teruggeeft met dezelfde elementen als L, maar in oplopende volgorde. (Let op: het tweede teken van de functienaam is een “el” voor “lijst”, niet een 1 (één) of een “i”!)

blsort hoeft alleen maar lijsten met binaire cijfers te sorteren, dat wil zeggen, deze functie mag en moet ervan uitgaan dat L altijd een lijst met alleen 0’en en 1’en is.

Je mag de ingebouwde sorteerfuncties sorted(L) en L.sort() niet gebruiken om dit probleem op te lossen! Je mag ook je zelfgeschreven sorteerfunctie (deze wordt later gevraagd) niet gebruiken.

Verder mag je elke andere functionele techniek gebruiken om blsort te implementeren. In het bijzonder is het handig te bedenken hoe je gebruik kan maken van de beperking dat het argument L een binaire lijst is, dit is een belangrijke beperking!

Een hulpfunctie die sommigen handig vinden is count(e, L). Die telt hoe vaak e voorkomt in L:

def count(e, L):
    """Geeft hoe vaak e voorkomt in L."""
    return sum([1 for x in L if x == e])


assert count(1, [1, 0, 1]) == 2

Zet count(e, L) in je bestand, dan kun je hem gebruiken in blsort.

Hier zijn een paar voorbeelden:

In [1]: blsort([1, 0, 1])
Out[1]: [0, 1, 1]

In [2]: L = [1, 0, 1, 0, 1, 0, 1]

In [3]: blsort(L)
Out[3]: [0, 0, 0, 1, 1, 1, 1]

Binaire eenvoud

Dit probleem is veel makkelijker dan sorteren in het algemeen! Maak gebruik van het feit dat de lijst L alleen maar 0 of 1 kan bevatten.

De functie gensort(L)

Gebruik recursie om een algemene sorteerfunctie gensort(L) te schrijven die een lijst L accepteert en een lijst teruggeeft met dezelfde elementen als L, maar in oplopende volgorde. Je kan hiervoor de ingebouwde Python functie max (of min, als je deze liever hebt) gebruiken, en de functie rem_one hieronder. Recursie, dat wil zeggen het sorteren van de rest van de lijst, is hier handig.

rem_one(e, L) haalt e één keer uit de lijst L: de eerste keer dat hij voorkomt.

def rem_one(e, L):
    """Geeft L zonder de eerste e; staat e niet in L, dan L zelf."""
    if L == []:  # basisgeval
        return []
    elif L[0] == e:  # basisgeval: de eerste e gevonden
        return L[1:]
    else:  # recursief geval
        return [L[0]] + rem_one(e, L[1:])


assert rem_one(8, [7, 8, 9, 8]) == [7, 9, 8]
assert rem_one(5, [7, 8]) == [7, 8]

Je ziet hier een paar voorbeelden:

In [1]: gensort([42, 1, 3.14])
Out[1]: [1, 3.14, 42]

In [2]: L = [7, 9, 4, 3, 0, 5, 2, 6, 1, 8]

In [3]: gensort(L)
Out[3]: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Bij deze opgave mag je de in Python ingebouwde sorteer functies zoals sorted(L) en L.sort() niet gebruiken. Je moet zelf een aanpak bedenken en implementeren! Let verder op dat gensort(L) moet werken voor lijsten L, het hoeft niet te werken voor strings.

De functie lingo(s, t)

Schrijf een functie lingo(s, t) die twee strings s en t accepteert en een integer teruggeeft, de zogenaamde “Lingo-telling, of -score, waar s wordt vergeleken met t.

De Lingo-score is het aantal tekens in s dat ook voorkomt in t. Herhaalde letters tellen vaker, mits ze vaker voorkomen in beide strings, hoe dit werkt wordt duidelijker in de onderstaande voorbeelden. Je hoeft er bij deze functie geen rekening mee te houden of de letters op dezelfde plek staan. Merk op dat alhoewel Lingo traditioneel gespeeld wordt met woorden van 5 (of 6) letters, de lengte van de woorden in deze functie niet beperkt is!

Er zijn meerdere manieren om dit probleem op te lossen, een aantal daarvan gebruikt kleinere hulpfuncties. Het staat je vrij om zulke hulpfuncties toe te voegen als je dat handig vindt. Een versie van rem_one uit gensort die een teken uit een string haalt, kan hier bijvoorbeeld van pas komen.

Merk op dat als s of t een lege string is, de Lingo-score 0 moet zijn!

Wel of niet

Op enig moment zul je moeten testen of een karakter zich wel of niet in een string bevindt. De regel if s[0] in t: zou een handige test kunnen zijn!

Een paar voorbeelden:

In [1]: lingo('diner', 'proza')  # alleen de 'r'
Out[1]: 1

In [2]: lingo('beeft', 'euvel')  # twee 'e's zijn gedeeld
Out[2]: 2

In [3]: lingo('gattaca', 'aggtccaggcgc') # 2 'a's, 1 't', 1 'c', 1 'g'
Out[3]: 5

In [4]: lingo('gattaca', '') # geef 0 terug bij een lege string
Out[4]: 0

De functie lcs(s, t)

Deze algoritmische uitdaging heeft alles met DNA-matching te maken!

Schrijf een functie lcs(s, t) die twee strings s en t accepteert. De functie geeft een string terug die de langste gemeenschappelijke deelrij (LCS, longest common subsequence) is die s en t met elkaar delen.

De LCS is een string waarvan de letters een deelrij van s en een deelrij van t zijn (ze moeten in dezelfde volgorde, maar niet noodzakelijkerwijs na elkaar in de twee argumenten voorkomen).

Let op dat als s of t een lege string is, het resultaat ook een lege string is!

Een paar voorbeelden:

In [1]: lcs('mens', 'chimpansee')
Out[1]: 'mns'

In [2]: lcs('gattaca', 'tacgaacta')
Out[2]: 'gaaca'

In [3]: lcs('wow', 'wauw')
Out[3]: 'ww'

In [4]: lcs('', 'wauw')     # eerste argument is de lege string
Out[4]: ''

In [5]: lcs('abcdefgh', 'efghabcd')
Out[5]: 'abcd'

Als meerdere resultaten van gelijke lengte mogelijk zijn dan maakt het niet uit welke je teruggeeft, in het laatste voorbeeld hierboven zou 'efgh' ook een goed antwoord zijn geweest.

Use it or lose it or lose it

Gebruik de volgende strategie:

• Als de eerste karakters van s en t gelijk zijn, dus s[0] en t[0], gebruik ze dan!

• Als s[0] en t[0] niet gelijk zijn, pas dan twee keer recursie toe: je zou dit use it or lose it or lose it kunnen noemen!

• Gebruik voor de eerste “lose it” recursie om de eerste letter van het ene argument weg te gooien:

  result1 = lcs(s[1:], t)
  

• Gebruik voor de tweede “lose it” recursie om de eerste letter van het andere argument weg te gooien:

  result2 = lcs(..., ...)
  

  Hier moet je nog wat details invullen…

• Geef ten slotte de betere van de twee resultaten terug. Bedenk zelf wat “beter” in dit geval betekent. Met max(result1, result2, key=...) uit het tweede college van deze week kies je de betere in één regel.

De functie make_change(amount, coins)

De laatste functie bouwt voort op exact_change uit het eerste college van deze week, maar is moeilijker omdat:

• ze de gebruikte munten moet teruggeven;

• ze ook False kan teruggeven, en je een aantal gevallen moet afhandelen na de recursie.

Schrijf de functie make_change(amount, coins), met dezelfde argumenten als exact_change. De functie moet bepalen welke munten uit coins gebruikt kunnen worden om amount te betalen.

In plaats van True of False terug te geven zoals bij exact_change moet de functie make_change een lijst teruggeven van munten uit coins die samen optellen tot amount. Als geen lijst kan worden samengesteld zal de functie False teruggeven. Als meer dan één lijst met munten uit coins mogelijk is mag de functie elk geldig antwoord teruggeven.

De volgorde van de waarden in het antwoord maakt niet uit, maar het is logisch om dezelfde volgorde aan te houden als van de oorspronkelijke lijst.

Je hoeft exact_change niet als hulpfunctie te gebruiken, maar het mag wel!

De voorbeelden hieronder tonen hoe make_change moet werken. Let op dat je 0 altijd precies kan betalen, en dat je een negatief bedrag nooit precies kan betalen. Waar het resultaat een niet-lege lijst is, staat er sorted omheen, zodat het resultaat een duidelijke volgorde heeft:

In [1]: sorted(make_change(42, [25, 1, 25, 10, 5, 1]))
Out[1]: [1, 1, 5, 10, 25]

In [2]: make_change(42, [25, 1, 25, 10, 5])
Out[2]: False

In [3]: make_change(42, [23, 1, 23, 100])
Out[3]: False

In [4]: sorted(make_change(42, [23, 17, 2, 100]))
Out[4]: [2, 17, 23]

In [5]: sorted(make_change(42, [25, 16, 2, 15]))
Out[5]: [2, 15, 25]

In [6]: make_change(0, [4, 5, 6])
Out[6]: []

In [7]: make_change(-47, [4, 5, 6])
Out[7]: False

In [8]: make_change(0, [])
Out[8]: []

In [9]: make_change(42, [])
Out[9]: False