Advent of Code 2021 Day 15
Le problème
Partie 1
Le jour 15 marquera le jour où j’aurai passé 3 heures à debug mon programme pour trouver une erreur d’indice mal mis à jour… alors qu’il y avait pleins d’autres sources d’erreurs potentielles.
Bref, on découvre aujourd’hui encore une nouvelle créature sous-marine : le chiton, qui est franchement moins mignon que le poulpe Dumbo, donc pas d’image pour lui ! Le problème d’aujourd’hui consiste à sortir de notre cavité en navigant grâce à une carte qui donne la densité de chitons en chaque point. Cette carte est de la forme suivante :
1163751742
1381373672
2136511328
3694931569
7463417111
1319128137
1359912421
3125421639
1293138521
2311944581
Notre objectif est alors de partir du point en haut à gauche (0, 0) et
d’arriver dans le coin inférieur droit en réduisant au maximum le niveau de
risque pris pour traverser la cavité. On nous dit également qu’il est impossible
de se déplacer en diagonale.
La façon de présenter le problème fait tout de suite penser à des algorithmes de recherche de chemin tels que les algorithmes A* ou de Dijkstra. L’idée ici est de comprendre que les entiers en chaque point peuvent également représenter la distance telle qu’on pourrait la présenter dans l’algorithme de plus court chemin de Dijkstra.
L’algorithme de Dijkstra va chercher à déterminer, pour chaque point, le chemin
parcouru (ou la distance) minimal par rapport à l’origine. Cette construction va
faire que l’on va éventuellement trouver la distance minimale entre le point (0, 0) et le point (n, n). Puisque c’est un algorithme étudié de façon
relativement classique en informatique, je ne vais pas m’étendre plus et
présenter la solution pour cette première partie :
from queue import PriorityQueue
def parse_input_data():
with open('input-large.txt', 'r') as data:
grid = [[int(i) for i in line] for line in data.read().splitlines()]
return grid
def find_neighbours(current, size):
x, y = current[0], current[1]
neighbours = [(x - 1, y),
(x, y - 1), (x, y + 1),
(x + 1, y)]
final_neighbours = []
for (x_n, y_n) in neighbours:
if x_n in range(size) and y_n in range(size):
final_neighbours.append((x_n, y_n))
return final_neighbours
def dijkstra(grid, start, end, size):
queue = PriorityQueue()
queue.put((0, start))
distance = {(x, y): size * size * 10
for x in range(size)
for y in range(size)}
while queue.queue:
current_distance, node = queue.get()
if node == end:
return distance[end]
for neighbour in find_neighbours(node, size):
x, y = neighbour
new_distance = current_distance + grid[x][y]
if new_distance < distance[neighbour]:
distance[neighbour] = new_distance
queue.put((new_distance, neighbour))
def solve_part_one():
grid = parse_input_data()
size = len(grid)
score = dijkstra(grid, (0, 0), (size - 1, size - 1), size)
print(score)
Partie 2
Dans la partie 2, on augmente la taille de la carte en utilisant l’algorithme suivant : on duplique la grille pour que celle-ci soit 5 fois plus grande que la grille initiale. Et lors des duplications, on va augmenter les chiffres comme indiqué dans la figure ci-dessous. Si on augmente la valeur d’un 9, on obtient un 1 à la place.
+----------+----------+----------+----------+----------+
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| Grille | +1 | +2 | +3 | +4 |
| initiale | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
+----------+----------+----------+----------+----------+
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| +1 | +2 | +3 | +4 | +5 |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
+----------+----------+----------+----------+----------+
...
L’algorithme nous demande encore une fois de parcourir la carte et de déterminer le niveau de risque minimum (ou le chemin le plus court en terminologie algorithme de Dijkstra). On peut donc reprendre le programme écrit en partie 1, et simplement le compléter avec une fonction pour étendre cette carte.
def expand_grid(grid):
rows = []
for i in range(5):
for row in grid:
rows.append([elt + i
if elt + i < 10 else (elt + i + 1) % 10
for elt in row])
grid = rows
for row in grid:
expand_row = []
for i in range(1, 5):
expand_row += [elt + i
if elt + i < 10 else (elt + i + 1) % 10
for elt in row]
row += expand_row
return grid
def dijkstra(grid, start, end, size):
queue = PriorityQueue()
queue.put((0, start))
distance = {(x, y): size * size * 10
for x in range(size)
for y in range(size)}
while queue.queue:
current_distance, node = queue.get()
if node == end:
return distance[end]
for neighbour in find_neighbours(node, size):
x, y = neighbour
new_distance = current_distance + grid[x][y]
if new_distance < distance[neighbour]:
distance[neighbour] = new_distance
queue.put((new_distance, neighbour))
def solve_part_two():
grid = parse_input_data()
grid = expand_grid(grid)
size = len(grid)
score = dijkstra(grid, (0, 0), (size - 1, size - 1), size)
print(score)
Les difficultés
Après avoir passé plus de 3h à chercher une erreur au mauvais endroit, je ne sais pas trop quoi dire dans cette section…
Si l’on fait abstraction de cela, la difficulté principale reste l’implémentation de l’algorithme de Dijkstra, qu’il aura fallu adapter un peu à nos besoin d’aujourd’hui. En parcourant un peu l’article Wikipédia sur cet algorithme, j’y ai vu une optimisation possible avec les priority queues, qui sont donc des files qui vont s’ordonner naturellement pour que le prochain élément à sortir respecte un critère de minimum pour une grandeur. Ici, ce minimum correspond à la distance depuis l’origine jusqu’au point courant.
Une autre difficulté pourrait être la transformation de la grille en une grille 5 fois plus grande. Mais avec un peu d’attention, on peut y arriver assez naïvement en procédant d’abord sur les lignes, puis sur les colonnes (ou inversement).