Advent of code

◂ 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.
  1. code_noOptim.py
  2. code_optim.py
  3. diff_optim_addOnPathOnly.diff
  4. diff_optim_saveTurnplacesOnly.diffy
  5. diff_obstaclesInSet.diffy
  6. code_reallyOptim.py
  7. diff_optim_startAtNewObstacle.diffy
with open("input.txt", 'r', encoding='utf-8') as f:
    lines = [line[:-1] for line in f.readlines()]

# Convert to list of booleans
obstacles = [ [ ((c == "#") if (c != '^') else '^') for c in line] for line in lines ]

# Find starting point
for y, line in enumerate(lines):
    if '^' in line:
        x = line.index('^')
        obstacles[y][x] = False
        start_point = (x, y)
        break

W = len(obstacles[0])
H = len(obstacles)
RANGE_W = range(W)
RANGE_H = range(H)

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
    #return x not in RANGE_W  or y not in RANGE_H   # slower :-(

def route_to_leave(obstacles, x, y):
        direction = (0, -1)
        route = set()
        while (x,y,direction) not in route:
            route.add((x,y,direction))
            if is_next_out(x, y, direction):
                return route
            while obstacles[y+direction[1]][x+direction[0]]:
                direction = next_direction(direction)
            x += direction[0]
            y += direction[1]
        return False   # loop, no finite route to leave
               
places_visited = set((x,y) for x,y,dir in route_to_leave(obstacles, *start_point))
print("Réponse partie 1:", len(places_visited))
print()

##### PART 2 #####
nb_loops = 0

for obst_y in RANGE_H:
    print(f"{str(obst_y).rjust(3)}/{H}", end=' ')
    for obst_x in RANGE_W:
        if obstacles[obst_y][obst_x] or ((obst_x, obst_y) == start_point):
            print('#', end='')
            continue
        obstacles_new = [line[:] for line in obstacles]
        obstacles_new[obst_y][obst_x] = True
        if not route_to_leave(obstacles_new, *start_point):
            nb_loops += 1
            print('o', end='')
        else:
            print('.', end='')
    print()
    
print()
print("Réponse partie 2:", nb_loops)