◂ 20 décembre 2024 ▸
Race condition : Trouver des chemins dans un labyrinthe sachant qu'on a une potion de passe-muraille qui dure 20 déplacements.
############# …
#.......#E..# …
#.#####.###.. …
#...#S#....## …
###.#.####.## …
⋮
code_part2.py donne la réponse pour les deux parties, mais code_part1.py est ici, car il utilise un algorithme un peu différent, même si le principe de base reste le même.
Principe de base : on calcule les distances de chaque endroit sans obstacle à partir du départ, mais aussi à partir de la fin, et on essaie de trouver des passages passe-muraille d'une certaine longueur entre ces endroits.
On n'a alors plus qu'à additionner la distance depuis le départ, la distance depuis la fin, et la longueur du passage.
Pour la partie 1 avec des passages de longueur 1, on regarde chaque bout de mur (obstacle) et on en fait un passage potentiel.
Pour la partie 2, ce n'est plus possible. On part donc de toute position sans obstacle et on regarde toute position sans obstacle qui n'excède pas la distance correspondant à la durée de la potion.
Edit : Puisque ce pseudo-labyrinthe n'est qu'un long couloir, pas besoin de calculer les distances depuis le point d'arrivée ; il s'agit à chaque fois de la longueur du couloir moins la distance depuis le départ…
- code_part1.py
- code_part2.py
- diff_part2.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()]
GAIN_MIN = 100 GAIN_MIN = 100
> CHEAT_TIMES = {'partie 1' : 2, 'partie 2' : 20}
H = len(lines) H = len(lines)
W = len(lines[0]) W = len(lines[0])
def find_pos(lines, symbol): def find_pos(lines, symbol):
y = next(y for y,line in enumerate(lines) if symbol in li y = next(y for y,line in enumerate(lines) if symbol in li
x = lines[y].index(symbol) x = lines[y].index(symbol)
return x, y return x, y
start = start_x, start_y = find_pos(lines, 'S') start = start_x, start_y = find_pos(lines, 'S')
end = end_x, end_y = find_pos(lines, 'E') end = end_x, end_y = find_pos(lines, 'E')
obstacles = [[ c == '#' for c in line] for line in lines] obstacles = [[ c == '#' for c in line] for line in lines]
DIRECTIONS = ((1,0), (0,1), (0,-1), (-1,0)) DIRECTIONS = ((1,0), (0,1), (0,-1), (-1,0))
def get_distances(obstacles, start): def get_distances(obstacles, start):
grid = [[ (None if is_obst else -1) for is_obst in line] grid = [[ (None if is_obst else -1) for is_obst in line]
todo = set([start]) todo = set([start])
grid[start[1]][start[0]] = 0 grid[start[1]][start[0]] = 0
while todo: while todo:
todo_new = set() todo_new = set()
for x,y in todo: for x,y in todo:
for dx, dy in DIRECTIONS: for dx, dy in DIRECTIONS:
nx, ny = x+dx, y+dy nx, ny = x+dx, y+dy
if grid[ny][nx] == -1: if grid[ny][nx] == -1:
grid[ny][nx] = grid[y][x] + 1 grid[ny][nx] = grid[y][x] + 1
todo_new.add((nx,ny)) todo_new.add((nx,ny))
todo = todo_new todo = todo_new
return grid return grid
grid_start = get_distances(obstacles, start) grid_start = get_distances(obstacles, start)
grid_end = get_distances(obstacles, end) grid_end = get_distances(obstacles, end)
print("Temps course normal:", grid_end[start_y][start_x]) print("Temps course normal:", grid_end[start_y][start_x])
temps_course = grid_end[start_y][start_x] temps_course = grid_end[start_y][start_x]
| for partie, CHEAT_TIME in CHEAT_TIMES.items():
nb = 0 nb = 0
for y in range(1, H - 1): | for y1 in range(1, H - 1):
for x in range(1, W - 1): | for x1 in range(1, W - 1):
if obstacles[y][x]: | if not obstacles[y1][x1]:
for dx1, dy1 in DIRECTIONS: | for y2 in range(max(1, y1 - CHEAT_TIME), min(H - 1, y1 + CHEAT_TIME + 1)):
nx1, ny1 = x+dx1, y+dy1 | for x2 in range(max(1, x1 - CHEAT_TIME), min(W - 1, x1 + CHEAT_TIME + 1)):
if obstacles[ny1][nx1]: | if obstacles[y2][x2]:
continue | continue
for dx2, dy2 in DIRECTIONS: | length = abs(y2 - y1) + abs(x2 - x1)
nx2, ny2 = x+dx2, y+dy2 | if length > CHEAT_TIME or length < 2:
if obstacles[ny2][nx2] or (nx1,ny1) = |
continue ] continue
new_d = grid_start[ny1][nx1] + grid_end[n | new_d = grid_start[y1][x1] + grid_end[y2][x2] + length
if new_d <= temps_course - GAIN_MIN: if new_d <= temps_course - GAIN_MIN:
nb += 1 nb += 1
print("Réponse partie 1:", nb) | print(f"Réponse {partie}:", nb)