Extra¶
De extra heeft drie delen: Pijlenpad, Periodiek T-shirt en Caesar op orde. Elk deel staat op zichzelf: je hebt de code van een ander deel niet nodig.
Pijlenpad¶
Pijlenpad is een puzzel van Janko. Je krijgt een vierkant rooster van n bij n vakjes. In elk vakje behalve dat rechtsonder staat een pijl. Je vult de getallen 1 tot en met n² elk één keer in, zo dat je vanaf elk getal het volgende getal vindt door de pijl te volgen. Het volgende getal staat ergens in de richting van de pijl, niet per se in het vakje ernaast. Linksboven staat altijd 1 en rechtsonder n²; soms staan er al meer getallen.
In deze opgave laat je de computer de puzzel oplossen. Bij elk getal zijn er soms meer vakjes waar het volgende getal kan staan, en vooraf weet je niet welk vakje goed is. Je probeert dus elke keuze, en geeft het op zodra je vastloopt.
De puzzel als lijst van lijsten¶
Een puzzel is een lijst van rijen. Elke rij is een lijst van vakjes, en elk vakje
is een lijst met twee elementen: het getal en de pijl. Een getal dat nog niet
bekend is, is 0. De pijl is een windrichting: "N" is omhoog, "O" naar
rechts, "ZW" schuin naar linksonder, enzovoort. Het vakje rechtsonder heeft
geen pijl: "".
Een plek in het rooster schrijf je als [row, col], met de rij en de kolom, en
beide tellen vanaf 0. [0, 0] is linksboven. Een pad is een lijst van plekken
in de volgorde van de getallen: op de eerste plek staat 1, op de tweede 2,
enzovoort.
Dit is de eerste puzzel, met zijn oplossing:
Vanaf de 1 linksboven wijst de pijl schuin naar rechtsonder ("ZO"). Daar staan
twee vakjes: het middelste en dat rechtsonder. Rechtsonder staat al 9, dus de 2
moet in het middelste vakje. Zo gaat het verder, tot de 8 rechtsboven: die wijst
omlaag, naar de 9.
De tweede puzzel is groter:
De cel hieronder zet de windrichtingen, de twee puzzels en hun oplossingen klaar.
Bij elke windrichting geeft DIRECTIONS hoeveel rijen en kolommen je per stap
opschuift. Voer de cel eerst uit.
DIRECTIONS = {
"N": [-1, 0],
"NO": [-1, 1],
"O": [0, 1],
"ZO": [1, 1],
"Z": [1, 0],
"ZW": [1, -1],
"W": [0, -1],
"NW": [-1, -1],
}
PUZZLE_1 = [
[[1, "ZO"], [0, "ZW"], [0, "Z"]],
[[0, "Z"], [0, "N"], [0, "N"]],
[[0, "O"], [0, "NO"], [9, ""]],
]
SOLUTION_1 = [
[[1, "ZO"], [3, "ZW"], [8, "Z"]],
[[4, "Z"], [2, "N"], [7, "N"]],
[[5, "O"], [6, "NO"], [9, ""]],
]
PUZZLE_2 = [
[[1, "Z"], [0, "O"], [0, "ZO"], [0, "W"], [0, "W"]],
[[0, "NO"], [0, "ZO"], [0, "O"], [0, "Z"], [0, "ZW"]],
[[0, "ZO"], [0, "ZW"], [0, "N"], [0, "ZW"], [0, "ZW"]],
[[17, "N"], [0, "NO"], [0, "NW"], [0, "NW"], [0, "N"]],
[[0, "O"], [0, "W"], [0, "W"], [0, "NO"], [25, ""]],
]
SOLUTION_2 = [
[[1, "Z"], [3, "O"], [6, "ZO"], [5, "W"], [4, "W"]],
[[2, "NO"], [24, "ZO"], [21, "O"], [22, "Z"], [13, "ZW"]],
[[18, "ZO"], [16, "ZW"], [20, "N"], [14, "ZW"], [7, "ZW"]],
[[17, "N"], [19, "NO"], [15, "NW"], [23, "NW"], [12, "N"]],
[[10, "O"], [9, "W"], [8, "W"], [11, "NO"], [25, ""]],
]
Wat je gaat maken¶
Stap |
Functie |
Doet |
Wat je oefent |
|---|---|---|---|
1 |
|
alle plekken in de richting van de pijl |
een |
2 |
|
de plekken waar het volgende getal kan staan |
een list comprehension |
3 |
|
maak een pad af, of geef het op |
een recursieve aanroep in een lus over de keuzes |
4 |
|
zet de getallen van een pad in de puzzel |
een geneste list comprehension |
5 |
|
los de puzzel op |
stap 3 en 4 samen |
Stap 1: targets(board, row, col)¶
Geeft een lijst met alle plekken die vanaf [row, col] in de richting van de pijl
liggen, van dichtbij naar ver weg, tot de rand van het rooster. Heeft het vakje
geen pijl, dan is de lijst leeg.
Aanroep |
Resultaat |
|---|---|
|
|
|
|
|
|
Hint
De pijl is board[row][col][1], en DIRECTIONS geeft de stap in rijen en
kolommen. Tel die stap in een while-lus steeds op bij de rij en de kolom,
zolang je binnen het rooster blijft: een rij of kolom van 0 tot en met
len(board) - 1.
# jouw oplossing
assert targets(PUZZLE_1, 0, 0) == [[1, 1], [2, 2]]
assert targets(PUZZLE_1, 0, 2) == [[1, 2], [2, 2]]
assert targets(PUZZLE_2, 3, 0) == [[2, 0], [1, 0], [0, 0]]
assert targets(PUZZLE_1, 2, 2) == []
Stap 2: next_cells(board, path)¶
path is een pad dat tot nu toe klopt. Geeft een lijst met de plekken waar het
volgende getal kan staan. Het volgende getal is len(path) + 1. Een plek komt in
de lijst als ze in de richting van de pijl op de laatste plek van path ligt, en
als ze past bij de getallen die al in de puzzel staan:
Staat het volgende getal al in de puzzel, dan komt alleen de plek in aanmerking waar het staat.
Anders komen alleen lege vakjes in aanmerking, die nog niet in
pathstaan.
Aanroep |
Resultaat |
|---|---|
|
|
|
|
In de tweede puzzel valt [3, 0] af: daar staat 17 en niet 2. En staat de 3 op
[4, 1], dan wijst de pijl daar naar [4, 0], waar de 2 al staat: dan is de
lijst leeg.
Hint
Maak eerst een lijst met alle getallen die al in de puzzel staan, met een
geneste list comprehension over de rijen en de vakjes. Filter daarna de
plekken uit targets met een list comprehension. Het getal op plek
[row, col] is board[row][col][0].
# jouw oplossing
assert next_cells(PUZZLE_1, [[0, 0]]) == [[1, 1]]
assert next_cells(PUZZLE_1, [[0, 0], [1, 1]]) == [[0, 1]]
assert next_cells(PUZZLE_2, [[0, 0]]) == [[1, 0], [2, 0], [4, 0]]
assert next_cells(PUZZLE_2, [[0, 0], [4, 0], [4, 1]]) == []
Stap 3: extend_path(board, path)¶
Maakt het pad path af tot een pad langs alle n² vakjes, en geeft dat pad
terug. Kan het pad niet worden afgemaakt, dan geeft de functie [] terug.
Aanroep |
Resultaat |
|---|---|
|
|
|
|
In het tweede voorbeeld staat de 2 op een plek waarmee de puzzel niet af te maken is.
Hint
Het basisgeval is een pad dat al alle vakjes heeft: len(path) is len(board)
in het kwadraat. Loop anders met een lus de plekken uit next_cells langs. Maak
voor elke plek het pad path + [cell] af met een recursieve aanroep. Geeft die
iets anders terug dan [], dan heb je de oplossing en geef je hem meteen terug.
Na de lus weet je dat geen enkele keuze werkt.
# jouw oplossing
path = [[0, 0], [1, 1], [0, 1], [1, 0], [2, 0], [2, 1], [1, 2], [0, 2], [2, 2]]
assert extend_path(PUZZLE_1, [[0, 0]]) == path
assert extend_path(PUZZLE_2, [[0, 0], [2, 0]]) == []
assert len(extend_path(PUZZLE_2, [[0, 0]])) == 25
Stap 4: fill(board, path)¶
path is een pad langs alle vakjes. Geeft een nieuwe puzzel terug, met op elke
plek het getal uit het pad en dezelfde pijl als in board. board zelf verandert
niet.
Hiervoor gebruik je de methode index van een lijst. L.index(x) geeft de index
waarop x voor het eerst in L staat: ["a", "b", "c"].index("c") is 2, en
[[0, 0], [1, 1]].index([1, 1]) is 1. Staat x niet in L, dan geeft Python
een foutmelding. In een pad langs alle vakjes staat elke plek precies één keer, dus
dat gebeurt hier niet.
Aanroep |
Resultaat |
|---|---|
|
|
Hint
Het getal op plek [row, col] is één meer dan de index van die plek in path:
path.index([row, col]) + 1. Bouw de nieuwe puzzel met een geneste list
comprehension, over range(len(board)) voor de rijen en voor de kolommen.
# jouw oplossing
path = [[0, 0], [1, 1], [0, 1], [1, 0], [2, 0], [2, 1], [1, 2], [0, 2], [2, 2]]
assert fill(PUZZLE_1, path) == SOLUTION_1
assert fill([[[1, ""]]], [[0, 0]]) == [[[1, ""]]]
Stap 5: arrow_path(board)¶
Geeft de opgeloste puzzel terug.
Aanroep |
Resultaat |
|---|---|
|
|
|
|
Hint
Elk pad begint linksboven, bij de 1: [[0, 0]].
# jouw oplossing
assert arrow_path(PUZZLE_1) == SOLUTION_1
assert arrow_path(PUZZLE_2) == SOLUTION_2
Tot slot¶
Beide puzzels hebben precies één oplossing, en arrow_path vindt die. Bij elk
getal probeerde extend_path de plekken uit next_cells een voor een. Liep een
keuze vast, dan kwam [] terug en was de volgende plek aan de beurt. Dat is de
recursieve aanroep in een lus over de keuzes, zoals in het practicum van
vorige week. Nieuw is dat een keuze kan
mislukken, en dat de functie dan verder zoekt.
(Informatica Olympiade 2021)
Periodiek T-shirt¶
Er bestaan T-shirts met woorden die zijn samengesteld uit de symbolen van elementen uit het periodiek systeem. In deze opgave zoek je uit welke woorden je zo kunt maken, en op hoeveel manieren.
Het gegeven¶
Een element heeft een symbool van één of twee letters: "K" is kalium, "Kr" is
krypton. Een woord maak je door symbolen achter elkaar te zetten. Hoofdletters
tellen daarbij niet mee: het woord kranten is K + Ra + N + Te + N.
Soms moet je kiezen. kranten begint met de K van kalium of met de Kr van krypton. Kies je Kr, dan loop je vast: er is geen element A en geen element An. Met K lukt het wel. Of je één letter of twee moet nemen, weet je vooraf niet. Je probeert dus beide.
De cel hieronder zet de symbolen van de eerste 118 elementen klaar in de lijst
ELEMENTS. De methode .split() knipt de lange string op bij de spaties. Voer
de cel eerst uit.
ELEMENTS = (
"H He Li Be B C N O F Ne Na Mg Al Si P S Cl Ar K Ca Sc Ti V Cr Mn Fe Co Ni "
"Cu Zn Ga Ge As Se Br Kr Rb Sr Y Zr Nb Mo Tc Ru Rh Pd Ag Cd In Sn Sb Te I "
"Xe Cs Ba La Ce Pr Nd Pm Sm Eu Gd Tb Dy Ho Er Tm Yb Lu Hf Ta W Re Os Ir Pt "
"Au Hg Tl Pb Bi Po At Rn Fr Ra Ac Th Pa U Np Pu Am Cm Bk Cf Es Fm Md No Lr "
"Rf Db Sg Bh Hs Mt Ds Rg Cn Nh Fl Mc Lv Ts Og"
).split()
Wat je gaat maken¶
Stap |
Functie |
Doet |
Hoe je combineert |
|---|---|---|---|
6 |
|
is een stukje tekst het symbool van een element? |
geen recursie |
7 |
|
kun je een woord maken met symbolen? |
één letter |
8 |
|
op hoeveel manieren kun je een woord maken? |
één letter |
Stap 6: is_element(s)¶
s is een string van kleine letters. Geeft True als s het symbool van een
element is, als je hoofdletters niet meetelt, en anders False.
Aanroep |
Resultaat |
|---|---|
|
|
|
|
|
|
Hint
De methode .lower() geeft een string in kleine letters: "Kr".lower() is
"kr". Maak met een list comprehension de lijst van alle symbolen in kleine
letters, en vraag met in of s daarin staat.
# jouw oplossing
assert is_element("k") == True
assert is_element("kr") == True
assert is_element("a") == False
assert is_element("an") == False
Stap 7: can_spell(word)¶
word is een string van kleine letters. Geeft True als je word kunt maken
door symbolen van elementen achter elkaar te zetten, en anders False. Een lege
string kun je altijd maken: met nul symbolen.
Aanroep |
Resultaat |
|---|---|
|
|
|
|
|
|
Hint
Er zijn twee keuzes, en elke keuze is een recursieve aanroep:
de eerste letter is een symbool:
is_element(word[:1]), en de rest,word[1:], kun je maken;de eerste twee letters zijn een symbool:
is_element(word[:2]), en de rest,word[2:], kun je maken.
Lukt een van de twee, dan kun je het woord maken. Een woord van één letter heeft
geen twee eerste letters; let op dat word[:2] dan het hele woord is.
# jouw oplossing
assert can_spell("kranten") == True
assert can_spell("spuwers") == True
assert can_spell("caesar") == True
assert can_spell("uitdaging") == False
assert can_spell("kaas") == False
assert can_spell("") == True
Stap 8: count_spellings(word)¶
Geeft terug op hoeveel manieren je word kunt maken met symbolen van elementen.
spuwers kan op twee manieren: S + P + U + W + Er + S, en S + Pu
W + Er + S.
Aanroep |
Resultaat |
|---|---|
|
|
|
|
|
|
|
|
Hint
De keuzes zijn dezelfde als in stap 7. Tel nu het aantal manieren van beide
keuzes op. Een keuze waarvan het begin geen symbool is, levert 0 manieren op.
Let weer op een woord van één letter: daar is maar één keuze, anders tel je
"k" twee keer.
# jouw oplossing
assert count_spellings("kranten") == 1
assert count_spellings("spuwers") == 2
assert count_spellings("basis") == 3
assert count_spellings("sinas") == 5
assert count_spellings("uitdaging") == 0
assert count_spellings("") == 1
Tot slot¶
caesar kan op één manier: Ca + Es + Ar. sinas kan zelfs op vijf
manieren. Bij elke letter probeerde je twee dingen: een symbool van één letter, of
een van twee. Net als bij use it or lose it in het
college zijn dat twee recursieve aanroepen, en
de manier van combineren hangt af van de vraag: or als je wilt weten of het
kan, + als je telt.
(Informatica Olympiade 2020-2021)
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.
Zet de voorbeelden om in assertions, zodat je je werk kunt controleren. Zegt een opdracht iets anders over een voorbeeld, dan volg je de opdracht. Bij lcs en make_change zijn meer antwoorden goed; controleer daar of je antwoord aan de eisen voldoet.
Opdracht 1: 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 bijvoorbeeld97terug… 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_strgebruiken 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"
Zet
list_to_str(L)in je notebook, dan kun je hem gebruiken inencipher.
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!
# jouw oplossing
Opdracht 2: decipher(s)¶
Omgekeerd krijgt decipher(s) een string s met een (Nederlandstalige) tekst die al versleuteld is. De functie decipher moet, voor zover mogelijk, de originele tekst teruggeven, dit zal een rotatie (mogelijk ook 0) zijn van het argument s.
Let erop 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 Scrabblescore 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 Scrabblescores kunnen proberen (want deze zijn ook gebaseerd op letterfrequenties). Letters die vaak voorkomen zijn in Scrabble weinig waard, dus dan zoek je de rotatie met de laagste score. 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
Zet letter_prob(c) in je notebook, dan kun je hem gebruiken in decipher.
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…
# jouw oplossing
Opdracht 3: 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 notebook, 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.
# jouw oplossing
Opdracht 4: 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]
Zet rem_one(e, L) in je notebook, dan kun je hem gebruiken in gensort.
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 sorteerfuncties 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.
# jouw oplossing
Opdracht 5: 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
# jouw oplossing
Opdracht 6: 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
sentgelijk zijn, duss[0]ent[0], gebruik ze dan!Als
s[0]ent[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.
# jouw oplossing
Opdracht 7: 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
Falsekan 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
# jouw oplossing