Le problème

Partie 1

Notre exploration en sous-marin continue, et nous devons désormais faire face à des cheminées hydrothermales (c’est l’une des choses que j’ai apprises aujourd’hui en faisant l’exercice). Pour pouvoir naviguer sereinement (et probablement pour ne pas cuire sur place), on nous dit qu’il serait judicieux de les éviter autant que possible.

On nous dit également que les cheminées forment des lignes, d’où le jeu de données fourni en exemple, de la forme : x_start,y_start -> x_end,y_end

0,9 -> 5,9
8,0 -> 0,8
9,4 -> 3,4
2,2 -> 2,1
7,0 -> 7,4
6,4 -> 2,0
0,9 -> 2,9
3,4 -> 1,4
0,0 -> 8,8
5,5 -> 8,2

Pour comprendre ce jeu de données, il faut comprendre comment ces cheminées sont indiquées sur notre plan. Ainsi, dans le jeu de données fourni en exemple, on nous explique que l’on peut représenter notre entourage par le schéma suivant, où le point en haut à gauche est de coordonnées (0, 0) et le point en bas à droite est de coordonnées (9, 9). Les . correspondent aux endroits où il n’y a aucune cheminée hydrothermale, les 1 correspondent aux positions où l’on trouve une ligne de cheminées hydrothermales, les 2 correspondent aux positions où deux lignes hydrothermales se croisent, et ainsi de suite.

.......1..
..1....1..
..1....1..
.......1..
.112111211
..........
..........
..........
..........
222111....

Dans la partie 1, on nous dit de nous intéresser uniquement aux lignes verticales et horizontales (cela exclue par exemple la deuxième ligne du jeu de données fourni plus haut). Il faut ensuite que l’on calcule le nombre de croisements présents dans le jeu de données.

Algorithme utilisé

Pour cet exercice, une première approche assez naïve serait de représenter le plan sous forme de tableau 2D ou de matrice. Mais sur l’exemple que l’on nous donne, et aussi sur le vrai jeu de données, on s’aperçoit assez vite que la matrice contiendrait pas mal de zéros. Je me suis alors posé la question de comment optimiser ma structure de données pour ne pas avoir à gérer autant de données inutiles.

Puisque l’on travaille avec des coordonnées (x, y), on peut se dire qu’il serait possible de les représenter sous la forme d’un tuple, immuable donc. Et cette immuabilité des tuples est intéressante puisque cela permet d’en faire des clés pour un dictionnaire !

J’ai donc décidé de construire un dictionnaire, où toutes les clés seront les coordonnées des points représentés dans le jeu de données. En parcourant les points du jeu de données, je peux donc soit mettre à jour une valeur dans un dictionnaire, soit ajouter une nouvelle clé dans ce dictionnaire.

Le problème suivant est alors de créer la liste de toutes les coordonnées représentées par chaque ligne du jeu de données. Pour cela, un petit peu d’algorithmique pour :

• Déterminer si l’on a une ligne horizontale ou verticale (valeurs de x identiques entre le début et la fin, ou valeur de y identiques entre le début et la fin)
• Déterminer les valeurs minimales et maximales pour pouvoir ensuite itérer entre ces deux valeurs pour récupérer toutes les coordonnées de la ligne en cours.

Solution

J’ai donc créé trois fonctions utilitaires :

• parse_input_data() qui permet de lire les données en entrée et de filtrer uniquement les lignes verticales et horizontales si l’on cherche à résoudre la partie 1.
• create_coordinates_dict(lines) qui va donc créer le dictionnaire mentionné dans la section précédente, et dont les clés sont les coordonnées des cheminées et les valeurs le nombre de lignes de cheminées qui se croisent en ce point.
• create_coordinates_for_line(line) qui, pour une ligne de cheminée donnée, va générer toutes les coordonnées comprises entre start et end.

Une fois que cela est implémenté, il suffit de compter le nombre de clés pour lesquelles les valeurs sont strictement supérieures à 1.

def parse_input_data():
    """
    Reads the input data, and produces a list of tuples
    :return: `filtered_lines` is a list of tuples
            [((x_start, y_start), (x_end, y_end)),
             ...]
    """
    with open('input-large', 'r') as data:
        lines = data.read().splitlines()
        filtered_lines = []
        for line in lines:
            start, end = line.split(' -> ')
            start = tuple([int(x) for x in start.split(',')])
            end = tuple([int(x) for x in end.split(',')])
            if start[0] == end[0] or start[1] == end[1]:
                filtered_lines.append((start, end))
        return filtered_lines


def create_coordinates_dict(lines):
    """
    Creates a dictionary where keys are coordinates (as tuples) and values
    are the number of times this position is covered by a line.
    :param lines: The list of coordinates as tuples
    :return: A dictionary {(x_pos, y_pos): value}
    """
    dict_coordinates = dict()
    for line in lines:
        coordinates = create_coordinates_for_line(line[0], line[1])
        for coordinate in coordinates:
            if coordinate in dict_coordinates.keys():
                dict_coordinates[coordinate] += 1
            else:
                dict_coordinates[coordinate] = 1
    return dict_coordinates


def create_coordinates_for_line(start, end):
    """
    This method generates the list of all coordinates covered by a line defined
    by its `start` and `end` coordinates.
    :param start: A tuple (x_start, y_start)
    :param end:  A tuple (x_end, y_end)
    :return: A list of all coordinates (x_pos, y_pos) covered by the line
             represented by (start, end)
    """
    coordinates = []
    if start[0] == end[0]:
        low, high = min(start[1], end[1]), max(start[1], end[1])
        coordinates = [(start[0], y_pos) for y_pos in range(low, high+1)]
    else:
        low, high = min(start[0], end[0]), max(start[0], end[0])
        coordinates = [(x_pos, start[1]) for x_pos in range(low, high+1)]
    return coordinates


def solve_part_one():
    lines = parse_input_data(True)
    coordinates_dict = create_coordinates_dict(lines)
    overlaps = sum([1 for value in coordinates_dict.values() if value > 1])
    print(overlaps)

Partie 2

Dans la partie 2, le problème est identique à ce détail près : on va désormais également prendre en compte les diagonales. Pour simplifier la tâche, on nous dit que ces diagonales ont forcément des pentes de 45 degrés. Cela signifie qu’en incrémentant ou décrémentant de 1 les coordonnées en abscisse ou en ordonnée, on est capable de représenter l’ensemble des coordonnées pour une telle diagonale.

Cela a pour conséquence que :

• Il faut modifier parse_input_data() pour y ajouter un paramètre booléen indiquant si l’on résout la partie 1 ou 2 de l’exercice.
• Il faut modifier create_coordinates_for_line(start, end) pour également chercher à générer les coordonnées pour les diagonales.

Le reste du programme est à l’identique.

def parse_input_data(is_part_one):
    """
    Reads the input data, and produces a list of tuples
    :param is_part_one: Boolean value to filter lines according to Part 1
    :return: `filtered_lines` is a list of tuples
            [((x_start, y_start), (x_end, y_end)),
             ...]
    """
    with open('input-large', 'r') as data:
        lines = data.read().splitlines()
        filtered_lines = []
        for line in lines:
            start, end = line.split(' -> ')
            start = tuple([int(x) for x in start.split(',')])
            end = tuple([int(x) for x in end.split(',')])
            # We are asked to filter only horizontal or vertical lines in
            # Part 1.So we check if either coordinate is found in both ends.
            if is_part_one:
                if start[0] == end[0] or start[1] == end[1]:
                    filtered_lines.append((start, end))
            else:
                filtered_lines.append((start, end))
        return filtered_lines


def create_coordinates_for_line(start, end):
    """
    This method generates the list of all coordinates covered by a line defined
    by its `start` and `end` coordinates.
    :param start: A tuple (x_start, y_start)
    :param end:  A tuple (x_end, y_end)
    :return: A list of all coordinates (x_pos, y_pos) covered by the line
             represented by (start, end)
    """
    coordinates = []
    if start[0] == end[0]:
        low, high = min(start[1], end[1]), max(start[1], end[1])
        coordinates = [(start[0], y_pos) for y_pos in range(low, high+1)]
    elif start[1] == end[1]:
        low, high = min(start[0], end[0]), max(start[0], end[0])
        coordinates = [(x_pos, start[1]) for x_pos in range(low, high+1)]
    else:
        # We identify whether we need to increase or decrease the x and y positions
        x_inc = 1 if start[0] < end[0] else -1
        y_inc = 1 if start[1] < end[1] else -1
        x_pos, y_pos = start
        while x_pos != end[0] and y_pos != end[1]:
            coordinates.append((x_pos, y_pos))
            x_pos += x_inc
            y_pos += y_inc
        coordinates.append((end[0], end[1]))
    return coordinates
    
    
def solve_part_two():
    lines = parse_input_data(False)
    coordinates_dict = create_coordinates_dict(lines)
    overlaps = sum([1 for value in coordinates_dict.values() if value > 1])
    print(overlaps)

Les difficultés

Le problème d’aujourd’hui semble traiter d’un tableau 2D (ou d’une matrice) comme nous avions pu le faire pour le problème en jour 4. Mais comme indiqué plus haut, on risque d’avoir énormément de zéros dans cette matrice, ce qui rendrait notre programme pas très optimisé en mémoire.

Je me suis donc tourné vers les dictionnaires pour modéliser le problème d’aujourd’hui (ce qui permet d’introduire cette structure de données pour cette année), en me basant sur l’immuabilité des tuples pour en faire mes clés.

Pour la suite, il y a quelques parcours de lignes horizontales, verticales, ou diagonales qui sont des exercices classiques mais où il faut toujours faire un peu attention. Par exemple, il faut bien boucler jusqu’à la dernière position (et donc faire attention aux bornes de nos boucles), ou il faut faire attention à bien gérer les diagonales.

Une fois que cela est géré avec attention, le résultat se calcule assez rapidement grâce aux dictionnaires puisque l’on n’a plus qu’à identifier les clés pour lesquelles les valeurs sont strictement supérieures à 1.