Jour 4 - Première grille

On a aujourd’hui droit à un type de problème qu’on a souvent eu l’an dernier, et que j’aime beaucoup: une grille. Dans ce type de problème, les données en entrée sont à deux dimensions, représentant une sorte de “carte” avec différents types d’éléments (ici, les . représentant une case vide, et les @ représentant des cases remplies):

On demande dans un premier temps de compter le nombre de cases remplies dont moins de quatre cases voisines sont aussi remplies. Dans l’exemple ci-dessus, ça correspond aux 13 cases marquées par un x ici:

Préparatifs

Dans ce genre de problèmes, le “piège” habituel est de vouloir le traiter directement comme une grille, c’est-à-dire en parcourant systématiquement toutes les cases pour répondre à la question. Souvent, on peut reformuler le problème avantageusement sous forme d’un graphe. Ici, on peut prendre comme noeuds les “cases remplies”, et chaque noeud aura des liens vers ses voisins. Chaque noeud sera également responsable de retenir sa “position” sur la grille.

Habituellement, je stocke cette position comme un tuple (x, y), mais j’avais envie de tester cette fois-ci le fait d’utiliser un nombre complexe à la place. Un nombre complexe est une représentation très naturelle d’un vecteur, qui a l’avantage de permettre directement toutes les opérations vectorielles (addition, scaling…). Préparons donc une classe Node:

class Node:
    def __init__(self, pos: complex):
        self.pos = pos
        self.neighbours: set[Node] = set()

    def add_neighbour(self, node: Node) -> None:
        self.neighbours.add(node)
    
    def count_neighbours(self) -> int:
        return len(self.neighbours)

Les voisins seront conservés dans un set, ce qui me permet de ne pas devoir me préoccuper du risque de compter deux fois le même voisin si je me plante en les ajoutant!

Partie 1: compter les noeuds

L’essentiel du travail, maintenant, consiste à “parser” ce qu’on a en entrée. C’est ici le seul moment où on devra effectivement parcourir la grille. On utilise enumerate pour savoir où on en est dans les positions, et dès qu’on trouve un @ on l’ajoute à un dictionnaire dont la clé est la position (donc un nombre complexe).

Pour la gestion des voisins, on utilise le fait qu’on parcoure la grille de haut en bas et de gauche à droite: chaque fois qu’on trouve un noeud, on vérifie, sur la case directement à gauche et les trois cases voisines au-dessus s’il y a un noeud présent. Si c’est le cas, on s’ajoute aux voisins de ce noeud, et on ajoute ce noeud à ses voisins.

Les positions sont encodées avec des nombres complexes, et j’utilise ici la convention que l’axe réel correspond à l’axe vertical (c’est-à-dire les lignes) et que l’axe imaginaire correspond à l’axe horizontal (les colonnes). Donc pour avoir la case “à gauche” de la position p, je dois chercher la position p-1j (Python utilise j pour marquer la partie imaginaire). La case en haut à droite sera p-1+1j. Tous les candidats voisins sont donc obtenus en ajoutant à la position courante [-1, -1-j, -1+1j, -1j].

def prepare_data(data: str) -> dict[complex, Node]:
    rows = data.split('\n')
    nodes: dict[complex, Node] = {}
    for a, row in enumerate(rows):
        for b, v in enumerate(row):
            if v == '@':
                pos = complex(real=a, imag=b)
                n = Node(pos)
                nodes[pos] = n
                for delta in [-1, -1-1j, -1+1j, -1j]:
                    neighbour_candidate = nodes.get(pos+delta, None)
                    if neighbour_candidate is not None:
                        neighbour_candidate.add_neighbour(n)
                        n.add_neighbour(neighbour_candidate)
    return nodes

Ces préparatifs nous donnent presque directement la réponse: il suffit de passer sur tous les noeuds, et de compter ceux qui ont moins de quatre voisins:

def main():
    data = load_input(4, '', prepare_data)
    
    print(f"Part 1: {sum(n.count_neighbours() < 4 for _, n in data.items())}")

Deuxième partie: on prend les mêmes et on recommence

La deuxième partie est une extension assez logique de la première, et je vois là que je vais être bien aidé par le choix de représentation que j’ai fait sur la première partie.

Ce qu’on demande maintenant, c’est d’itérativement retirer les noeuds ayant moins de quatre voisins. Donc, après le premier passage calculé ci-dessus, on retire ces noeuds, et on relance le processus, jusqu’à ce qu’il ne reste plus aucun noeud avec moins de quatre voisins.

Pour pouvoir faire ça, il nous faut un moyen facile pour un noeud de signifier à ses voisins qu’il a été retiré. On va donc rajouter deux méthodes à la classe Node:

class Node:
    # ...
    def remove_neighbour(self, other: Node) -> None:
        self.neighbours.remove(other)

    def remove(self) -> None:
        for n in self.neighbours:
            n.remove_neighbour(self)

Si on appelle remove sur un noeud, il va se retirer de tous les noeuds voisins. On peut maintenant coder la logique qui se déroule à chaque itération: récupérer le set des éléments à retirer, puis appeler pour chacun leur méthode remove. La méthode renvoie le nombre d’éléments retirés lors de ce “round”.

def remove_nodes(data: dict[complex, Node]) -> int:
    """Returns the number of removed nodes in one loop
    """
    to_remove: set[Node] = set()

    # prepare
    for _, n in data.items():
        if n.count_neighbours() < 4:
            to_remove.add(n)
    removed = len(to_remove)

    # actually remove them
    for n in to_remove:
        del data[n.pos]
        n.remove()
    
    return removed

Reste à coder l’itération. La réponse finale doit être le total des éléments retirés. On va donc stocker ça dans une variable. À chaque itération, j’utilise le “walrus operator” := pour en même temps récupérer le nombre de noeuds retirés, et tester si ce nombre est supérieur à 0.

def main():
    # ...
    total_rem = 0
    while( (rem := remove_nodes(data)) > 0 ):
        total_rem += rem
    
    print(f"Part 2: {total_rem}")