◂ 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
with open("input.txt", 'r', encoding='utf-8') as f:
lines = [line[:-1] for line in f.readlines()]
W = len(lines[0])
H = len(lines)
RANGE_W = range(W)
RANGE_H = range(H)
obstacles = set()
for y, line in enumerate(lines):
for x, c in enumerate(line):
if c == '^':
start_point = (x, y)
elif c == '#':
obstacles.add((x, y))
def next_direction(direction):
return (-direction[1], direction[0])
def is_next_out(x, y, direction):
x += direction[0]
y += direction[1]
return x < 0 or x >= W or y < 0 or y >= H
#return x not in RANGE_W or y not in RANGE_H # slower :-(
def route_to_leave(obstacles, x, y):
direction = (0, -1)
route = []
obstacles_seen = set()
while True:
route.append((x,y))
if is_next_out(x, y, direction):
return route
while (x+direction[0],y+direction[1]) in obstacles:
if (x,y,direction) in obstacles_seen:
return False
obstacles_seen.add((x,y,direction))
direction = next_direction(direction)
x += direction[0]
y += direction[1]
places_visited = set(route_to_leave(obstacles, *start_point))
print("Réponse partie 1:", len(places_visited))
print()
##### PART 2 #####
nb_loops = 0
for obst_y in RANGE_H:
print(f"{str(obst_y).rjust(3)}/{H}", end=' ')
for obst_x in RANGE_W:
if (obst_x, obst_y) in obstacles:
print('#', end='')
elif ((obst_x, obst_y) == start_point) or (obst_x, obst_y) not in places_visited:
print('.', end='')
else:
obstacles_new = set(obstacles)
obstacles_new.add((obst_x, obst_y))
if not route_to_leave(obstacles_new, *start_point):
nb_loops += 1
print('X', end='')
else:
print('o', end='')
print()
print()
print("Réponse partie 2:", nb_loops)
#========== Instead of adding a test for places_visited, we can just use them directly: no obstacle then. ====
#
# ##### PART 2 #####
# nb_loops = 0
#
# places_visited.remove(start_point)
#
# for place in places_visited:
# obstacles_new = set(obstacles)
# obstacles_new.add(place)
# if not route_to_leave(obstacles_new, *start_point):
# nb_loops += 1
#
# print("Réponse partie 2:", nb_loops)
#
#=========== No more visualization and no time gained, though. ===============================================