Extra: algoritmen¶
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