Le problème

Partie 1

Dans le problème d’aujourd’hui, nous sommes toujours dans une grotte sous-marine et notre sous-marin cherche à déterminer le chemin de sortie. Le système de navigation fonctionne avec des balises ouvrantes ((, [, {, <) et fermantes (), ], }, >).

Mais ce système de navigation est défectueux, et chaque ligne comporte des erreurs. En effet, elles sont soit incomplètes soit corrompues. Dans la première partie, on ne s’intéresse qu’aux lignes corrompues, c’est-à-dire les lignes où l’on peut trouver une balise fermante autre que celle attendue. En d’autres termes, une ligne est corrompue si, lorsqu’on la parcourt de gauche à droite, on trouve ne balise fermante qui ne correspond pas à la dernière balise ouvrante non-fermée.

J’ai donc construit l’algorithme suivant :

• On créé une variable qui va garder en mémoire toutes les balises ouvrantes pas encore fermées.
• Pour chaque balise b de la ligne :
  • Si b est une balise ouvrante, on l’ajoute à la liste ;
  • Sinon:
    • Si b ferme la dernière balise ajoutée à la liste, on retire ce dernier élément de la liste ;
    • Sinon, c’est que la ligne est corrompue par cette balise b.

Cet algorithme est repris dans la fonction check_line(), et permet donc de déterminer tous les caractères qui viennent corrompre les lignes du jeu de données. Une valeur de score est ensuite assigné à chaque type de balise fermante, et le résultat final correspond simplement à la somme des scores de ces balises responsables des lignes corrompues.

À noter la création de deux variables globales pour identifier les balises ouvrantes ou pour identifier la complémentaire d’une balise donnée.

OPENING_SIGNS = {'(', '{', '[', '<'}
OPPOSITE_SIGN = {')': '(',
                 ']': '[',
                 '}': '{',
                 '>': '<',
                 '(': ')',
                 '[': ']',
                 '{': '}',
                 '<': '>'}


def parse_input_data():
    with open('input-large', 'r') as data:
        return data.read().splitlines()


def check_line(line):
    queue = []
    for c in line:
        if c in OPENING_SIGNS:
            queue.append(c)
        else:
            if queue[-1] != OPPOSITE_SIGN[c]:
                return c
            else:
                queue.pop()
    return None


def compute_score(illegal_characters):
    score_map = {')': 3,
                 ']': 57,
                 '}': 1197,
                 '>': 25137}
    score = 0
    for c in illegal_characters:
        score += score_map[c]
    return score


def solve_part_one():
    lines = parse_input_data()
    illegal_characters = []
    illegal_lines = []
    for index, line in enumerate(lines):
        illegal_character = check_line(line)
        if illegal_character:
            illegal_characters.append(illegal_character)
            illegal_lines.append(index)
    print(compute_score(illegal_characters))
    return illegal_lines

Partie 2

Dans la seconde partie de cette journée, il faut dans un premier temps se débarrasser des lignes corrompues. On va donc légèrement modifier notre solution de la partie 1 pour retourner une liste des indices des lignes corrompues. On va ensuite se servir de ces indices pour retirer les lignes corrompues du jeu de données. Pour cela, on trie par ordre décroissant cette liste d’indice (c’est toujours dangereux de retirer des éléments d’une liste en les identifiant par leurs indices).

Ensuite, pour les lignes restantes, il faut :

1. Lister toutes les balises restées ouvertes ;
2. Fermer ces balises en commençant par les dernières pour s’assurer de ne pas corrompre la ligne ;
3. Calculer un score final dont l’algorithme de calcul nous est donné par l’énoncé.

Pour le premier point, j’ai donc défini une fonction get_incomplete_signs() qui retourne la liste des balises restées ouvertes. Celle-ci ressemble beaucoup à la fonction check_line() de la partie 1 au détail suivant : on est assuré d’avoir des lignes incomplètes (et pas corrompues). Pour le second point, j’ai défini une fonction get_complete_signs() qui va retourner la séquence de balises fermantes permettant de compléter la ligne incomplète. Pour le dernier point, j’ai défini la fonction compute_completion_score() qui reprend simplement l’algorithme donné en énoncé. Pour structurer un peu le tout, j’ai défini une fonction complete_line() qui est appelée pour chaque ligne incomplète.

def get_incomplete_signs(line):
    queue = []
    for c in line:
        if c in OPENING_SIGNS:
            queue.append(c)
        else:
            queue.pop()
    return queue


def get_complete_signs(queue):
    complete_signs = []
    while queue:
        complete_signs.append(OPPOSITE_SIGN[queue.pop()])
    return complete_signs


def compute_completion_score(completion_signs):
    score_map = {')': 1,
                 ']': 2,
                 '}': 3,
                 '>': 4}
    score = 0
    for sign in completion_signs:
        score *= 5
        score += score_map[sign]
    return score


def complete_line(line):
    queue = get_incomplete_signs(line)
    complete_signs = get_complete_signs(queue)
    return complete_signs


def solve_part_two():
    lines = parse_input_data()
    illegal_lines = solve_part_one()
    illegal_lines.sort(reverse=True)
    scores = []
    for illegal_line in illegal_lines:
        lines.pop(illegal_line)
    for line in lines:
        completion_sign = complete_line(line)
        score = compute_completion_score(completion_sign)
        scores.append(score)
    scores.sort()
    print(scores[len(scores) // 2])

Les difficultés

Bien que pas nécessairement très compliqué, il y a pas mal de points auxquels il faut faire attention dans cet exercice.

Le premier concerne le parsing des données, la représentation d’une ligne, et surtout la structure de données à utiliser pour détecter une balise corrompue. Pour cela, une pile est assez bien adaptée : on ajoute ou retire uniquement les éléments en haut de la pile (c’est-à-dire à la fin d’une liste).

Un second point d’attention concerne le retrait d’un élément d’une liste, ainsi que les implications que cela peut avoir sur les indices des éléments. Avec Python, on pourrait assez facilement faire ce travail avec une compréhension de liste du type :

# for illegal_line in illegal_lines:
#     lines.pop(illegal_line)
lines = [line for line in lines if line not in illegal_lines]

Et enfin, la dernière difficulté consiste à compléter les balises restées ouvertes en suivant bien le procédé de Last In First Out d’une pile.

Malgré tout, je trouve ces difficultés (et les exercices jusqu’à maintenant) assez simples comparées à celles des exercices de l’an passé pour le même jour. Espérons que cela reste ainsi encore suffisamment longtemps, sans quoi il sera de plus en plus difficile de concevoir et implémenter une solution tout en rédigeant des billets de blog en même temps.