Extra¶
Dit zijn de uitwerkingen van de drie delen van de extra: Pijlenpad, Periodiek T-shirt en Caesar op orde. Elk deel staat op zichzelf: de code van een ander deel heb je niet nodig.
Pijlenpad¶
Opdracht: Pijlenpad
De gegeven code uit de opgave:
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, ""]],
]
Stap 1: targets(board, row, col)¶
def targets(board, row, col):
"""Geeft de plekken die vanaf [row, col] in de richting van de pijl liggen."""
arrow = board[row][col][1]
if arrow == "":
return []
step = DIRECTIONS[arrow]
size = len(board)
cells = []
r = row + step[0]
c = col + step[1]
while 0 <= r < size and 0 <= c < size:
cells = cells + [[r, c]]
r = r + step[0]
c = c + step[1]
return cells
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)¶
def next_cells(board, path):
"""Geeft de plekken waar het volgende getal van path kan staan."""
number = len(path) + 1
last = path[-1]
given = [cell[0] for row in board for cell in row if cell[0] != 0]
if number in given:
return [
cell
for cell in targets(board, last[0], last[1])
if board[cell[0]][cell[1]][0] == number
]
else:
return [
cell
for cell in targets(board, last[0], last[1])
if board[cell[0]][cell[1]][0] == 0 and cell not in path
]
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)¶
De lus probeert de keuzes een voor een. Zodra een recursieve aanroep een compleet pad teruggeeft, stopt de functie. Pas als geen enkele keuze werkt, komt ze aan bij de laatste regel.
def extend_path(board, path):
"""Geeft path afgemaakt tot een pad langs alle vakjes, of [] als dat niet kan."""
if len(path) == len(board) * len(board): # basisgeval: het pad is af
return path
for cell in next_cells(board, path):
result = extend_path(board, path + [cell])
if result != []:
return result
return []
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)¶
def fill(board, path):
"""Geeft een nieuwe puzzel met de getallen uit path en de pijlen uit board."""
size = len(board)
return [
[[path.index([row, col]) + 1, board[row][col][1]] for col in range(size)]
for row in range(size)
]
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)¶
def arrow_path(board):
"""Geeft de opgeloste pijlenpadpuzzel board."""
return fill(board, extend_path(board, [[0, 0]]))
assert arrow_path(PUZZLE_1) == SOLUTION_1
assert arrow_path(PUZZLE_2) == SOLUTION_2
Periodiek T-shirt¶
Opdracht: Periodiek T-shirt
De gegeven code uit de opgave:
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()
Stap 6: is_element(s)¶
def is_element(s):
"""Geeft True als s, zonder op hoofdletters te letten, een elementsymbool is."""
return s in [symbol.lower() for symbol in ELEMENTS]
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)¶
De tweede keuze controleert eerst of het woord minstens twee letters heeft.
Anders zou word[:2] het hele woord van één letter zijn, en die keuze is dan al
de eerste.
def can_spell(word):
"""Geeft True als word te maken is met symbolen van elementen."""
if word == "": # basisgeval
return True
one = is_element(word[:1]) and can_spell(word[1:])
two = len(word) >= 2 and is_element(word[:2]) and can_spell(word[2:])
return one or two
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)¶
def count_spellings(word):
"""Geeft het aantal manieren om word te maken met symbolen van elementen."""
if word == "": # basisgeval
return 1
one = 0
if is_element(word[:1]):
one = count_spellings(word[1:])
two = 0
if len(word) >= 2 and is_element(word[:2]):
two = count_spellings(word[2:])
return one + two
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
Caesar op orde¶
Opdracht: Caesar op orde. Voer de opdrachten in volgorde uit: opdracht 2 gebruikt de hulpfuncties van opdracht 1. De overige opdrachten bevatten hun eigen benodigde hulpfuncties.
Opdracht 1: encipher(s, n)¶
Roteer elk teken met rot en voeg de tekens met list_to_str weer samen.
def rot(c, n):
"""Roteert ASCII-letter c over n plaatsen; andere tekens blijven gelijk."""
if "a" <= c <= "z":
return chr(ord("a") + (ord(c) - ord("a") + n) % 26)
if "A" <= c <= "Z":
return chr(ord("A") + (ord(c) - ord("A") + n) % 26)
return c
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"
def encipher(s, n):
"""Geeft string s met alle letters n plaatsen voorwaarts geroteerd."""
return list_to_str([rot(c, n) for c in s])
assert rot("a", 2) == "c"
assert rot("y", 2) == "a"
assert rot("A", 3) == "D"
assert rot("Y", 3) == "B"
assert rot(" ", 4) == " "
assert list_to_str([]) == ""
assert encipher("", 0) == encipher("", 25) == ""
assert encipher("aZ!? 09", 0) == "aZ!? 09"
assert encipher("xyza", 1) == "yzab"
assert encipher("Z A", 1) == "A B"
assert encipher("*ab?", 1) == "*bc?"
assert encipher("aAzZ", 25) == "zZyY"
assert encipher("Dit is een string!", 1) == "Eju jt ffo tusjoh!"
assert encipher("Caesarcijfer? Ik heb liever Caesarsalade.", 25) == "Bzdrzqbhiedq? Hj gda khdudq Bzdrzqrzkzcd."
Opdracht 2: decipher(s)¶
Deze score is een vuistregel. Hij werkt op de twee lange voorbeelden; bij korte tekst kan een andere rotatie winnen.
# 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
# Kies de rotatie met de hoogste som van Nederlandse letterfrequenties.
# Niet-letters zijn bij alle rotaties gelijk en veranderen de keuze niet.
def decipher(s):
"""Geeft de rotatie van s met de hoogste letterfrequentiescore."""
return max([encipher(s, n) for n in range(26)], key=lambda t: sum([letter_prob(c) for c in t]))
assert letter_prob("e") == letter_prob("E") == 0.1909
assert letter_prob("!") == 1.0
assert decipher("Bzdrzqbhiedq? Hj gda khdudq Bzdrzqrzkzcd.") == "Caesarcijfer? Ik heb liever Caesarsalade."
assert decipher("Aadxas ue exqotfe pq haadflqffuzs hmz baxufuqw yqf mzpqdq yuppqxqz.") == "Oorlog is slechts de voortzetting van politiek met andere middelen."
assert decipher("") == ""
assert decipher("!? 12") == "!? 12"
assert decipher("Lvkeg lvyon") in [encipher("Lvkeg lvyon", n) for n in range(26)]
Opdracht 3: blsort(L)¶
Tel de nullen en enen. Zet eerst alle nullen neer, daarna alle enen.
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
def blsort(L):
"""Geeft de binaire lijst L oplopend terug."""
return [0] * count(0, L) + [1] * count(1, L)
assert count(1, []) == 0
assert blsort([]) == []
assert blsort([1]) == [1]
assert blsort([0, 0]) == [0, 0]
assert blsort([1, 1]) == [1, 1]
assert blsort([1, 0, 1]) == [0, 1, 1]
assert blsort([1, 0, 1, 0, 1, 0, 1]) == [0, 0, 0, 1, 1, 1, 1]
Opdracht 4: gensort(L)¶
Neem de kleinste waarde, verwijder één voorkomen en sorteer de rest recursief.
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]
def gensort(L):
"""Geeft lijst L recursief in oplopende volgorde terug."""
if L == []:
return []
smallest = min(L)
return [smallest] + gensort(rem_one(smallest, L))
assert rem_one(2, []) == []
assert rem_one(2, [2, 2]) == [2]
assert gensort([]) == []
assert gensort([4]) == [4]
assert gensort([2, 1, 2, -1]) == [-1, 1, 2, 2]
assert gensort([42, 1, 3.14]) == [1, 3.14, 42]
assert gensort([7, 9, 4, 3, 0, 5, 2, 6, 1, 8]) == list(range(10))
Opdracht 5: lingo(s, t)¶
Een gevonden teken telt één keer. Verwijder dat voorkomen uit de andere string voordat je verder telt.
def remove_char(c, t):
"""Geeft string t zonder het eerste voorkomen van teken c."""
if t == "":
return ""
if t[0] == c:
return t[1:]
return t[0] + remove_char(c, t[1:])
def lingo(s, t):
"""Telt gedeelde tekens in s en t, met hun beschikbare multipliciteit."""
if s == "" or t == "":
return 0
if s[0] in t:
return 1 + lingo(s[1:], remove_char(s[0], t))
return lingo(s[1:], t)
assert remove_char("a", "") == ""
assert remove_char("a", "bb") == "bb"
assert remove_char("a", "aba") == "ba"
assert lingo("diner", "proza") == 1
assert lingo("beeft", "euvel") == 2
assert lingo("gattaca", "aggtccaggcgc") == 5
assert lingo("gattaca", "") == 0
assert lingo("", "abc") == 0
assert lingo("aaa", "a") == 1
assert lingo("ab", "ba") == 2
assert lingo("abc", "xyz") == 0
Opdracht 6: lcs(s, t)¶
Gelijke beginletters gebruik je. Anders vergelijk je de twee mogelijkheden om een beginletter weg te laten. Bij gelijke lengte is elk maximaal antwoord geldig.
def lcs(s, t):
"""Geeft een langste gemeenschappelijke deelrij van strings s en t."""
if s == "" or t == "":
return ""
if s[0] == t[0]:
return s[0] + lcs(s[1:], t[1:])
return max(lcs(s[1:], t), lcs(s, t[1:]), key=len)
def is_subsequence(part, text):
"""Controleert of part in dezelfde volgorde in text voorkomt."""
if part == "":
return True
if text == "":
return False
if part[0] == text[0]:
return is_subsequence(part[1:], text[1:])
return is_subsequence(part, text[1:])
assert lcs("", "wauw") == lcs("wauw", "") == ""
assert lcs("abc", "abc") == "abc"
assert lcs("abc", "xyz") == ""
assert lcs("wow", "wauw") == "ww"
assert lcs("mens", "chimpansee") == "mns"
for s, t, length in [("gattaca", "tacgaacta", 5), ("abcdefgh", "efghabcd", 4)]:
result = lcs(s, t)
assert is_subsequence(result, s) and is_subsequence(result, t)
assert len(result) == length
Opdracht 7: make_change(amount, coins)¶
Probeer de eerste munt te gebruiken. Alleen False betekent mislukking: de lege lijst is een geldige betaling van nul. Elke recursieve aanroep verbruikt of verwerpt één beschikbare munt.
def make_change(amount, coins):
"""Geeft munten uit voorraad coins met som amount, of False als dat niet kan."""
if amount == 0:
return []
if amount < 0 or coins == []:
return False
used = make_change(amount - coins[0], coins[1:])
if used != False:
return [coins[0]] + used
return make_change(amount, coins[1:])
for amount, coins, possible in [
(42, [25, 1, 25, 10, 5, 1], True),
(42, [25, 1, 25, 10, 5], False),
(42, [23, 1, 23, 100], False),
(42, [23, 17, 2, 100], True),
(42, [25, 16, 2, 15], True),
(0, [4, 5, 6], True), (-47, [4, 5, 6], False),
(0, [], True), (42, [], False),
(4, [2], False), (4, [2, 2], True), (2, [1, 1, 2], True),
]:
result = make_change(amount, coins)
if possible:
assert result != False
assert sum(result) == amount
assert [c for c in result if result.count(c) > coins.count(c)] == []
else:
assert result == False
assert make_change(0, []) == []
assert make_change(0, [4, 5, 6]) == []