Advent of code

◂ 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…
  1. code_part1.py
  2. code_part2.py
  3. diff_part2.diffy
with open("input.txt", 'r', encoding='utf-8') as f:
    lines = [line[:-1] for line in f.readlines()]

GAIN_MIN = 100
H = len(lines)
W = len(lines[0])

def find_pos(lines, symbol):
    y = next(y for y,line in enumerate(lines) if symbol in line)
    x = lines[y].index(symbol)
    return x, y
start = start_x, start_y = find_pos(lines, 'S')
end = end_x, end_y = find_pos(lines, 'E')

obstacles = [[ c == '#' for c in line] for line in lines]

DIRECTIONS = ((1,0), (0,1), (0,-1), (-1,0))
def get_distances(obstacles, start):
    grid = [[ (None if is_obst else -1) for is_obst in line] for line in obstacles]
    todo = set([start])
    grid[start[1]][start[0]] = 0
    while todo:
        todo_new = set()
        for x,y in todo:
            for dx, dy in DIRECTIONS:
                nx, ny = x+dx, y+dy
                if grid[ny][nx] == -1:
                    grid[ny][nx] = grid[y][x] + 1
                    todo_new.add((nx,ny))
        todo = todo_new
    return grid

grid_start = get_distances(obstacles, start)
grid_end = get_distances(obstacles, end)

print("Temps course normal:", grid_end[start_y][start_x])
temps_course = grid_end[start_y][start_x]

nb1 = 0
for y in range(1, H - 1):
    for x in range(1, W - 1):
        if obstacles[y][x]:
            for dx1, dy1 in DIRECTIONS:
                nx1, ny1 = x+dx1, y+dy1
                if obstacles[ny1][nx1]:
                    continue
                for dx2, dy2 in DIRECTIONS:
                    nx2, ny2 = x+dx2, y+dy2
                    if obstacles[ny2][nx2] or (nx1,ny1) == (nx2,ny2):
                        continue
                    new_d = grid_start[ny1][nx1] + grid_end[ny2][nx2] + 2
                    if new_d <= temps_course - GAIN_MIN:
                        nb1 += 1
print("Réponse partie 1:", nb1)