◂ 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
def route_to_leave(obstacles, x, y, direction):
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]
route = route_to_leave(obstacles, *start_point, (0,-1))
print("Réponse partie 1:", len(set(route)))
##### PART 2 #####
nb_loops = 0
places_done = set()
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.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, *route[i-1], dir):
nb_loops += 1
print("Réponse partie 2:", nb_loops)