◂ 10 décembre 2024 ▸
Hoof It : Chercher des chemins dans une grille.
432110231 …
567023110 …
478934010 …
⋮
Étonnant que la grille soit assez petite pour que le programme termine immédiatement sans même avoir besoin de memoization.
Avec memoization, le temps d'exécution est le même pour une telle grille ; on réduit pourtant d'un facteur 3 le nombre d'appels de la fonction récursive nb_trails_and_reachables_set (de 4799 à 1532 appels).
- code.py
- diff_memoization.diffy
with open("input.txt", 'r', encoding='utf-8') as f:
grid = [line[:-1] for line in f.readlines()]
W = len(grid[0])
H = len(grid)
for i,line in enumerate(grid):
grid[i] = [int(c) for c in line]
def nb_trails_and_reachables_set(x, y) -> tuple[int, set]:
if grid[y][x] == 9:
return 1, set([(x,y)])
nb = 0
reachables = set()
for dx,dy in [(1,0),(0,1),(-1,0),(0,-1)]:
if 0 <= x+dx < W and 0 <= y+dy < H:
if grid[y+dy][x+dx] == grid[y][x] + 1:
n, s = nb_trails_and_reachables_set(x+dx, y+dy)
nb += n
reachables.update(s)
return nb, reachables
nb_reachable = 0
nb_trails = 0
for y in range(H):
for x in range(W):
if grid[y][x] == 0:
n, s = nb_trails_and_reachables_set(x, y)
nb_trails += n
nb_reachable += len(s)
print("Réponse partie 1:", nb_reachable)
print("Réponse partie 2:", nb_trails)