◂ 17 décembre 2023 ▸
Clumsy Crucible : Parcours le moins coûteux avec contraintes sur la longueur des segments entre les virages
3133311111322 …
2231132323114 …
2113232122132 …
2111331311234 …
⋮
Essayé avec un Dijkstra puis un A* naïf, mais ça ne marche pas si l'endroit d'où l'on vient peut influencer le droit de prendre une arête ou non.
J'ai tenté un depth-first car un breadth-first me paraissait avoir le même problème, mais depth-first = trop long.
J'ai tenté un breadth-first en prenant en compte l'historique de parcours (et avec le fait que le graphe est pondéré, donc il faut ralentir la progression…).
Beaucoup trop lent aussi, mais avec 15 minutes de moulinage, ça passait et j'ai pu soumettre mes réponses.
Finalement, récrit le code avec Dijkstra, avec sommets = position+porte d'entrée, et en reliant des sommets voisins que si on tourne.
Et du coup, les voisins possibles calculés ne sont pas seulement les voisins immédiats, mais tous les voisins à bonne distance (entre 4 et 10 pour la partie 2).
Le code met moins de 30 secondes pour les deux parties.
Reste à faire :
· rendre plus joli le code Dijkstra ;
· essayer de modifier le Dijkstra en A* ;
· rendre lisible le code avec Breadth-first et le mettre en ligne.
- code_avec_dijkstra.py
- dijkstra.py
from heapq import heapify, heappop, heappush
from typing import Hashable, Callable
Sommet = Hashable
Deplacement = tuple[float, Sommet] | list[float|Sommet]
def dijkstra(aretes: dict[Sommet,list[Deplacement]] | Callable[Sommet,list[Deplacement]],
start: Sommet,
end: Sommet | Callable[[Sommet],bool] ) -> tuple[ float, list[Sommet] ] | None :
""" Les arêtes doivent etres des tuples (ok si list) avec la distance en premier et le sommet ensuite ! """
""" La liste des arêtes peut être donnée par un dictionnaire ou une fonction """
""" Si le graphe n'est pas orienté, les arêtes doivent êtres enregistrées dans les deux sens """
""" Le sommet de fin peut aussi être une fonction qui indique si le sommet est une fin possible """
if isinstance(aretes, dict):
_aretes = aretes
aretes = lambda sommet: _aretes.get(sommet,[])
if not isinstance(end, Callable):
_end = end
end = lambda sommet: sommet == _end
distances: dict[Sommet,Deplacement] = dict() # distance depuis start et sommet dont on vient
distances[start] = (0, None)
heap_a_faire: list[Deplacement] = [[0,start]]
while heap_a_faire:
dist,sommet = heappop(heap_a_faire)
if end(sommet):
_end = sommet
break
for poids,arrivee in aretes(sommet):
if dist_arr := distances.get(arrivee):
if dist_arr[0] > dist + poids:
to_heap = [dist_arr[0], arrivee]
if to_heap in heap_a_faire:
heap_a_faire[heap_a_faire.index(to_heap)][0] = dist+poids
heapify(heap_a_faire)
distances[arrivee] = (dist + poids, sommet)
else:
distances[arrivee] = (dist + poids, sommet)
heappush(heap_a_faire, [dist + poids, arrivee])
if not distances.get(_end):
return None
r = []
pos = _end
while pos is not None:
r.append(pos)
pos = distances[pos][1]
r.reverse()
return distances[_end][0], r
### Code pour tester l'algo ###
if __name__ == '__main__':
import random
sommets = [ chr(ord('A') + i) for i in range(26) ]
aretes = {}
for _ in range(len(sommets)**2//10):
f,t = random.choice(sommets), random.choice(sommets)
if (f == sommets[0] and t == sommets[-1]) or f == t or t in [arr for _,arr in aretes.get(f,[])]:
continue
aretes.setdefault(f,[]).append((random.randint(12,24), t))
print(sommets)
for a,b in aretes.items():
print(a,b)
print(dijkstra(aretes, 'A', sommets[-1]))
RANGE = range(5)
def get_aretes(s: Sommet) -> list[Deplacement]:
if s is None:
return []
r,c = s
return ((grid[r+d1][c+d2], (r+d1,c+d2)) for d1,d2 in ((0,1),(0,-1),(1,0),(-1,0)) if r+d1 in RANGE and c+d2 in RANGE)
grid = [[random.randint(1,9) for _ in RANGE] for _ in RANGE]
print(grid)
print(dijkstra(get_aretes, (0,0), (len(grid)-1, len(grid[0])-1)))