Advent of Code 2021 Day 9
Le problème
Partie 1
Dans le problème d’aujourd’hui, on reprend là où on s’était arrêté avec une cave creusée pour échapper à la baleine géante. Pour naviguer dans cette cave, notre sous-marin nous donne une matrice contenant des nombres compris entre 1 et 9 (voir le jeu de données initial).
2199943210
3987894921
9856789892
8767896789
9899965678
Dans la première partie de cet exercice, on nous demande de trouver tous les minimums locaux, puis de sommer leurs valeurs pour avoir le résultat final. Pour trouver ces minimums locaux, on nous donne deux indices :
- On ne considère que les valeurs directement en haut, en bas, à gauche, et à droite. Les valeurs en diagonales ne sont donc pas considérées.
- On a un minimum local si la valeur en ce point est strictement inférieure aux quatre autres valeurs (ou moins si on se trouve sur un bord ou dans un coin).
Le problème n’est pas trop compliqué : on va parcourir tous les points de la matrice, récupérer tous les voisins de ces points, et vérifier s’il s’agit d’un minimum local ou pas.
def parse_input_data():
""" On retourne une liste de listes d'entiers (donc à une matrice) """
with open('input-large', 'r') as data:
lines = data.read().splitlines()
return [[int(digit) for digit in line] for line in lines]
def get_neighbours(matrix, x, y):
# matrix[x-1]y]
# matrix[x][y-1] matrix[x][y] matrix[x][y+1]
# matrix[x-+]y]
height, width = len(matrix), len(matrix[0])
neighbours = []
if x-1 in range(height):
neighbours.append(matrix[x-1][y])
if x+1 in range(height):
neighbours.append(matrix[x+1][y])
if y-1 in range(width):
neighbours.append(matrix[x][y-1])
if y+1 in range(width):
neighbours.append(matrix[x][y+1])
return neighbours
def solve_part_one():
matrix = parse_input_data()
height, width = len(matrix), len(matrix[0])
output = 0
low_points = []
for x in range(height):
for y in range(width):
neighbours = get_neighbours(matrix, x, y)
if matrix[x][y] < min(neighbours):
low_points.append((x, y))
output += matrix[x][y] + 1
print(output)
Partie 2
Le travail de la Partie 1 va nous servir pour la Partie 2. En effet, il s’agit désormais de calculer la taille des bassins océaniques autour de ces minimums locaux. Pour déterminer si un point appartient au bassin ou pas, on va donc partir de ces minimums locaux en appliquant l’algorithme suivant :
bassins <- liste()
Pour chaque elt de la liste des minimums locaux:
bassin <- {elt}
visités <- {}
à_visiter <- {elt}
Tant que a_visiter n'est pas vide:
x, y <- premier élément de à_visiter
voisins <- récupérer la liste des coordonnées des voisins
Pour chaque voisin dans voisins:
x_voisin, y_voisin <- voisin
Si matrice[x_voisin][y_voisin] != 9
et matrice[x_voisin][y_voisin] > matrice[x][y]:
ajouter (x_voisin, y_voisin) à bassin
Si voisin n'est pas dans visités:
ajouter (x_voisin, y_voisin) à à_visiter
ajouter (x, y) à visités
ajouter taille(bassin) à bassins
trier bassins
afficher bassins[-1] * bassins[-2] * bassins[-3]
La solution en Python est très proche du pseudocode donné plus haut. À noter la
présence d’une fonction get_neighbours_coordinates() que je n’ai pas reprise
dans cette section, mais qui est en fait quasi-identique à celle utilisée dans
la Partie 1. La seule différence étant que, pour la Partie 2, je retourne les
coordonnées des points sous la forme de tuple plutôt que la valeur du point à
ces coordonnées.
def solve_part_two():
matrix = parse_input_data()
low_points = solve_part_one()
basins = []
for low_point in low_points:
basin, visited, to_visit = {low_point}, set(), {low_point}
while to_visit:
cur_x, cur_y = to_visit.pop()
neighbours = get_neighbours_coordinates(matrix, cur_x, cur_y)
for neighbour in neighbours:
x, y = neighbour
if matrix[x][y] > matrix[cur_x][cur_y] and matrix[x][y] != 9:
basin.add(neighbour)
if neighbour not in visited:
to_visit.add(neighbour)
visited.add((cur_x, cur_y))
basins.append(len(basin))
basins.sort()
print(basins[-1] * basins[-2] * basins[-3])
Les difficultés
Les deux problèmes d’aujourd’hui sont très bien en termes d’algorithmes et structures de données à utiliser.
La première partie reprend des algorithmes assez classiques de recherche et manipulation de voisins dans une matrice. Pour cela, je ne me suis pas vraiment cassé la tête et j’ai tout simplement défini une fonction qui renvoyait les voisins possibles pour un point passé en paramètre.
La seconde partie est aussi très intéressante. L’algorithme que j’ai utilisé est, dans la philosophie, assez semblable à un algorithme de parcours de graphe ou à l’algorithme A*. Une fois que l’on a vu ces algorithmes, ils aident grandement dans la résolution de ce type de problème où l’on cherche à couvrir une surface de plus en plus grande.