◂ 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: with open("input.txt", 'r', encoding='utf-8') as f:
lines = [line[:-1] for line in f.readlines()] lines = [line[:-1] for line in f.readlines()]
W = len(lines[0]) W = len(lines[0])
H = len(lines) H = len(lines)
RANGE_W = range(W) RANGE_W = range(W)
RANGE_H = range(H) RANGE_H = range(H)
# Convert to list of booleans | obstacles = set()
obstacles = [ [ ((c == "#") if (c != '^') else '^') for c in <
# Find starting point <
for y, line in enumerate(lines): for y, line in enumerate(lines):
if '^' in line: | for x, c in enumerate(line):
x = line.index('^') | if c == '^':
obstacles[y][x] = False | start_point = (x, y)
start_point = (x, y) | elif c == '#':
break | obstacles.add((x, y))
def next_direction(direction): def next_direction(direction):
return (-direction[1], direction[0]) return (-direction[1], direction[0])
def is_next_out(x, y, direction): def is_next_out(x, y, direction):
x += direction[0] x += direction[0]
y += direction[1] y += direction[1]
return x < 0 or x >= W or y < 0 or y >= H return x < 0 or x >= W or y < 0 or y >= H
def route_to_leave(obstacles, x, y): def route_to_leave(obstacles, x, y):
direction = (0, -1) direction = (0, -1)
route = set() route = set()
while (x,y,direction) not in route: while (x,y,direction) not in route:
route.add((x,y,direction)) route.add((x,y,direction))
if is_next_out(x, y, direction): if is_next_out(x, y, direction):
return route return route
while obstacles[y+direction[1]][x+direction[0]]: | while (x+direction[0],y+direction[1]) in obstacle
direction = next_direction(direction) direction = next_direction(direction)
x += direction[0] x += direction[0]
y += direction[1] y += direction[1]
return False # loop, no finite route to leave return False # loop, no finite route to leave
places_visited = set((x,y) for x,y,dir in route_to_leave(obst places_visited = set((x,y) for x,y,dir in route_to_leave(obst
print("Réponse partie 1:", len(places_visited)) print("Réponse partie 1:", len(places_visited))
##### PART 2 ##### ##### PART 2 #####
nb_loops = 0 nb_loops = 0
for obst_y in RANGE_H: for obst_y in RANGE_H:
print(f"{str(obst_y).rjust(3)}/{H}", end=' ') print(f"{str(obst_y).rjust(3)}/{H}", end=' ')
for obst_x in RANGE_W: for obst_x in RANGE_W:
if obstacles[obst_y][obst_x] or ((obst_x, obst_y) == | if (obst_x, obst_y) in obstacles or ((obst_x, obst_y)
print('#', end='') print('#', end='')
continue continue
obstacles_new = [line[:] for line in obstacles] | obstacles_new = set(obstacles)
obstacles_new[obst_y][obst_x] = True | obstacles_new.add((obst_x, obst_y))
if not route_to_leave(obstacles_new, *start_point): if not route_to_leave(obstacles_new, *start_point):
nb_loops += 1 nb_loops += 1
print('o', end='') print('o', end='')
else: else:
print('.', end='') print('.', end='')
print() print()
print() print()
print("Réponse partie 2:", nb_loops) print("Réponse partie 2:", nb_loops)