Advent of Code

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.


def route_to_leave(obstacles, x, y):                            def route_to_leave(obstacles, x, y):
        direction = (0, -1)                                             direction = (0, -1)
        route = set()                                         |         route = []
                                                              |         obstacles_seen = set()
        while (x,y,direction) not in route:                   |         while True:
            route.add((x,y,direction))                        |             route.append((x,y))
            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 obstacles[y+direction[1]][x+direction[0]]:
                                                              >                 if (x,y,direction) in obstacles_seen:
                                                              >                     return False     # loop, no finite route
                                                              >                 obstacles_seen.add((x,y,direction))
                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       <
                                                                               
places_visited = set((x,y) for x,y,dir in route_to_leave(obst | places_visited = set(route_to_leave(obstacles, *start_point))
                                                              
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

places_visited.remove(start_point)                              places_visited.remove(start_point)

for obst_x, obst_y in places_visited:                           for obst_x, obst_y in places_visited:
    obstacles_new = [line[:] for line in obstacles]                 obstacles_new = [line[:] for line in obstacles]
    obstacles_new[obst_y][obst_x] = True                            obstacles_new[obst_y][obst_x] = True
    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("Réponse partie 2:", nb_loops)                            print("Réponse partie 2:", nb_loops)