◂ 6 décembre 2024 ▸
Guard Gallivant : Déplacer un garde dans un environnement avec obstacles et voir s'il boucle ou s'il sort.
........#.. …
........... …
....#...... …
⋮
diff_optim_saveTurnplacesOnly.diffy : Optimisation toute bête d'une ligne qui permet de diviser par 7 le temps d'exécution…
diff_optim_saveTurnplacesOnly.diffy : Optimiser la détection de cycle en ne gardant en mémoire que les endroits où l'on tourne devant un obstacle. Aide un peu.
diff_obstaclesInSet.diffy : Utiliser un set pour lister les obstacles au lieu d'utiliser un tableau de lignes (de str '..#....#.…' ou de list de booléens), mais ne change pas grand chose au temps d'exécution.
code_optim.py Code qui intègre les trois changements ci-dessus.
diff_optim_startAtNewObstacle.diffy et code_reallyOptim.py : On repart à chaque fois juste devant l'obstacle qu'on vient de poser, ce qui économise tout le début du trajet. On divise par quatre le temps d'exécution.
Futures tentatives TODO: tester les cycles par ① dépassement de 130×130×4 pas ; ② implémentation de l'algo lièvre et tortue.
- code_noOptim.py
- code_optim.py
- diff_optim_addOnPathOnly.diff
- diff_optim_saveTurnplacesOnly.diffy
- diff_obstaclesInSet.diffy
- code_reallyOptim.py
- diff_optim_startAtNewObstacle.diffy
def route_to_leave(obstacles, x, y): | def route_to_leave(obstacles, x, y, direction):
direction = (0, -1) <
route = [] route = []
obstacles_seen = set() obstacles_seen = set()
while True: while True:
route.append((x,y)) route.append((x,y))
if is_next_out(x, y, direction): if is_next_out(x, y, direction):
return route return route
while (x+direction[0],y+direction[1]) in obstacle while (x+direction[0],y+direction[1]) in obstacle
if (x,y,direction) in obstacles_seen: if (x,y,direction) in obstacles_seen:
return False return False
obstacles_seen.add((x,y,direction)) obstacles_seen.add((x,y,direction))
direction = next_direction(direction) direction = next_direction(direction)
x += direction[0] x += direction[0]
y += direction[1] y += direction[1]
places_visited = set(route_to_leave(obstacles, *start_point)) | route = route_to_leave(obstacles, *start_point, (0,-1))
print("Réponse partie 1:", len(places_visited)) | print("Réponse partie 1:", len(set(route)))
##### PART 2 ##### ##### PART 2 #####
nb_loops = 0 nb_loops = 0
places_visited.remove(start_point) <
> places_done = set()
for place in places_visited: | for i in range(1, len(route)):
> place = route[i]
> if place in places_done:
> continue
> places_done.add(place)
obstacles_new = set(obstacles) obstacles_new = set(obstacles)
obstacles_new.add(place) obstacles_new.add(place)
> dir = [place[k] - route[i-1][k] for k in range(2)]
> dir = next_direction(dir)
if not route_to_leave(obstacles_new, *start_point): | if not route_to_leave(obstacles_new, *route[i-1], dir):
nb_loops += 1 nb_loops += 1
print("Réponse partie 2:", nb_loops) print("Réponse partie 2:", nb_loops)