Solve day16

[abavoil]

Have :

• a singleton array store the minimum distance currently found
• a list of paths that gets :
  • reset when we hit the goal with a lower minimum distance than the one stored
  • pushed when we hit the goal the the same distance as the minimum distance

Memoization :

• (i, j, dir) -> (smallest distance, path)

Stop condition :

• if current_dist > minimum_distance return [infty, copy(path)]
• if (i, j) == goal return [0, copy(path)]
• if (i, j, dir) in mem return mem[(i, j, dir)]

Fonction :

push!(copy(path), (i, j, dir))
...
for neighb in en face, droite, gauche
...
end

Construire un subtree, mais il n'est pas binaire = compliqué

Toujours commencer par aller tout droit plutôt qu'essayer de tourner

Au lieu de push à une copy, ajouter à un subtree, puis enlever si nouveau minimum

[abavoil]

blablabla Dijktra.

Pour être plus rapide :

• avoir une liste triée lt(x, y) = dist[x] < dist[y] pour toujours prendre le premier élément (pas besoin de trouver celui qui a la distance la plus petite) ?
• utiliser une priority queue (est-ce plus efficace qu'une liste triée ?)