◂ 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
> import functools
>
with open("input.txt", 'r', encoding='utf-8') as f: with open("input.txt", 'r', encoding='utf-8') as f:
grid = [line[:-1] for line in f.readlines()] grid = [line[:-1] for line in f.readlines()]
W = len(grid[0]) W = len(grid[0])
H = len(grid) H = len(grid)
for i,line in enumerate(grid): for i,line in enumerate(grid):
grid[i] = [int(c) for c in line] grid[i] = [int(c) for c in line]
> @functools.cache
def nb_trails_and_reachables_set(x, y) -> tuple[int, set]: def nb_trails_and_reachables_set(x, y) -> tuple[int, set]:
... ...
... ...