Extra: algoritmen¶
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 werkcollege van
vorige week. Nieuw is dat een keuze kan
mislukken, en dat de functie dan verder zoekt.
(Informatica Olympiade 2021)