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
CHEAT_TIMES = {'partie 1' : 2, 'partie 2' : 20}

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]

for partie, CHEAT_TIME in CHEAT_TIMES.items():
    nb = 0
    for y1 in range(1, H - 1):
        for x1 in range(1, W - 1):
            if not obstacles[y1][x1]:
                for y2 in range(max(1, y1 - CHEAT_TIME), min(H - 1, y1 + CHEAT_TIME + 1)):
                    for x2 in range(max(1, x1 - CHEAT_TIME), min(W - 1, x1 + CHEAT_TIME + 1)):
                        if obstacles[y2][x2]:
                            continue
                        length = abs(y2 - y1) + abs(x2 - x1)
                        if length > CHEAT_TIME or length < 2:
                            continue
                        new_d = grid_start[y1][x1] + grid_end[y2][x2] + length
                        if new_d <= temps_course - GAIN_MIN:
                            nb += 1
    print(f"Réponse {partie}:", nb)