Comment tracer des étapes dans une carte, Advent of Code par 6

Retour à mon défi Advent of Code, en raison de problèmes imprévisibles, je ne suis pas en mesure de terminer les défis à temps et j'ai actuellement environ 5 à 6 jours de retard. Cependant, je suis toujours déterminé à terminer les énigmes cette année. Aujourd'hui, parlons du 6ème casse-tête.

Image générée par Copilot qui convient quelque peu au thème

Rechercher des objets dans un avion 2D semble être un thème récurrent cette année. Aujourd'hui, nous retraçons les pas d'un gardien qui a une logique de mouvement claire et définie. Le garde se déplace en ligne droite et tourne à droite lorsqu'il est obstrué.

En supposant que nous représentons chaque pas effectué par le garde comme un point dans un plan 2D, nous pouvons alors représenter chaque pas dans une direction différente sous forme de vecteurs :

LEFT = (1, 0)
RIGHT = (-1, 0)
UP = (0, -1)
DOWN = (0, 1)

En effectuant quelques calculs comme indiqué ci-dessous, nous obtenons une matrice qui représente la bonne rotation

Dérivation de la matrice de rotation

À l'origine, cela était représenté comme un dictionnaire, puisque nous nous y appuierons fortement pour de nombreux calculs. Cependant, je voulais garantir des annotations de type appropriées, d'où cette implémentation pour l'instant.

class Rotation:
    c0r0: int
    c1r0: int
    c0r1: int
    c1r1: int

@dataclass(frozen=True)
class RotateRight(Rotation):
    c0r0: int = 0
    c1r0: int = 1
    c0r1: int = -1
    c1r1: int = 0

Nous avons également besoin d'un moyen pour représenter la position et le mouvement, ainsi que de méthodes pour manipuler la position et exécuter des rotations :

from __future__ import annotations

@dataclass(frozen=True)
class Point:
    x: int
    y: int

    def __add__ (self, direction: Direction) -> Point:
        return Point(self.x + direction.x, self.y + direction.y)

@dataclass
class Direction:
    x: int
    y: int

    def __mul__ (self, rotation: Rotation) -> Direction:
        return Direction(
            self.x * rotation.c0r0 + self.y * rotation.c0r1,
            self.x * rotation.c1r0 + self.y * rotation.c1r1,
        )

La définition des méthodes dunder/magic __add__ et __mul__ permet de manipuler les objets Point et Direction comme s'il s'agissait d'opérations arithmétiques standard dans le code. L'extrait montre également comment annoter efficacement la classe Rotation.

Enfin, nous définissons les modèles pour notre entrée :

class Symbol(Enum):
    Guard = "^"
    Obstruction = "#"

@dataclass
class Space:
    pass

@dataclass
class Guard:
    pass

@dataclass
class Obstruction:
    pass

@dataclass
class Board:
    tiles: dict[Point, Space | Guard | Obstruction]
    width: int
    height: int

Symbol est un Enum standard qui encapsule la signification de divers symboles dans l'entrée. Espace, Garde et Obstruction ont des significations explicites. Le tableau est une représentation de la carte. Mon approche initiale impliquait une conception plus orientée objet, mais j'ai finalement opté pour cette implémentation où chaque classe maintient simplement un état qui peut être facilement inspecté.

Commençons par analyser l'entrée :

def finder(board: tuple[str, ...], symbol: Symbol) -> Generator[Point, None, None]:
    return (
        Point(x, y)
        for y, row in enumerate(board)
        for x, item in enumerate(tuple(row))
        if item == symbol.value
    )

def parse(input: str) -> tuple[Board, Point]:
    board = tuple(input.strip().splitlines())

    return (
        Board(
            {point: Obstruction() for point in finder(board, Symbol.Obstruction)},
            len(board[0]),
            len(board),
        ),
        next(finder(board, Symbol.Guard)),
    )

Le garde est représenté par un objet Point. La fonction de recherche est chargée de scanner l'entrée et d'identifier les positions du symbole souhaité. Des solutions similaires pour l’analyse de cartes 2D continueront d’être explorées dans les articles suivants.

Ma solution pour la partie 1 est relativement simple. Pour calculer la prochaine étape du garde :

1. Déterminez la destination souhaitée directement devant le garde, en fonction du vecteur de direction actuel.
2. Vérifiez si la destination souhaitée est obstruée.
3. Si la destination souhaitée est obstruée : Nous renvoyons la destination souhaitée, et le vecteur de direction actuel.
4. Si la destination souhaitée n'est pas obstruée : Nous renvoyons la position actuelle et le vecteur de direction de rotation.

LEFT = (1, 0)
RIGHT = (-1, 0)
UP = (0, -1)
DOWN = (0, 1)

Enfin, nous abordons la partie 1 du défi, qui nécessite de déterminer le nombre de tuiles uniques visitées par le garde.

class Rotation:
    c0r0: int
    c1r0: int
    c0r1: int
    c1r1: int

@dataclass(frozen=True)
class RotateRight(Rotation):
    c0r0: int = 0
    c1r0: int = 1
    c0r1: int = -1
    c1r1: int = 0

La deuxième partie nous lance une balle courbe ! Nous avons pour tâche de trouver l'endroit idéal pour placer un nouvel objet sur la carte afin que notre robot patrouille en boucle pour toujours.

La bonne nouvelle est que trouver le bon endroit n’est pas compliqué. Nous connaissons le chemin initial du robot depuis la première partie, il nous suffit donc de placer l'objet quelque part le long de cet itinéraire.

Maintenant, la partie la plus délicate : comment savoir si nous avons réussi à créer une boucle ?

Voici mon approche :

1. Suivez les mouvements du robot : Au lieu de suivre sa position exacte, je me suis concentré sur l'enregistrement de chaque « pas » qu'il fait. Chaque étape est essentiellement un passage d'une tuile à la suivante.
2. Recherchez les modèles répétitifs : Si le robot commence à répéter la même séquence d'étapes, nous avons une boucle !
3. Assurez-vous qu'il reste sur la carte : Il est essentiel de nous assurer que le robot ne s'éloigne pas de la carte.

from __future__ import annotations

@dataclass(frozen=True)
class Point:
    x: int
    y: int

    def __add__ (self, direction: Direction) -> Point:
        return Point(self.x + direction.x, self.y + direction.y)

@dataclass
class Direction:
    x: int
    y: int

    def __mul__ (self, rotation: Rotation) -> Direction:
        return Direction(
            self.x * rotation.c0r0 + self.y * rotation.c0r1,
            self.x * rotation.c1r0 + self.y * rotation.c1r1,
        )

La raison pour laquelle j'ai choisi de stocker les étapes dans un dictionnaire est que l'ordre des étapes n'a pas d'importance pour cette partie du problème (ce qui fait allusion à un concept similaire dans un puzzle ultérieur).

Comme je devais vérifier fréquemment si une étape particulière s'était déjà produite, le stockage des étapes dans un dictionnaire a considérablement amélioré les performances. Les dictionnaires en Python sont incroyablement rapides pour les recherches, ce qui rend ces vérifications beaucoup plus rapides que l'utilisation d'une liste ou d'un tuple.

Ma première tentative, qui utilisait une structure de données différente, a pris environ 70 secondes pour s'exécuter sur les 8 cœurs de ma machine. En passant à un dictionnaire, j'ai pu réduire considérablement le temps d'exécution à quelques secondes seulement. Cela démontre le pouvoir de choisir la bonne structure de données pour la tâche à accomplir !

C'est tout pour aujourd'hui. Compte tenu de l’amélioration du temps d’exécution de 70 secondes sur tous les cœurs à quelques secondes seulement sur un seul cœur, je suis assez satisfait de l’optimisation, même si je sais que d’autres améliorations sont possibles (en visant idéalement une exécution en moins d’une seconde).

Ma précédente tentative pour décrocher un emploi ne s'est pas bien terminée (oui, toujours #OpenToWork, envoyez-moi un ping !), car j'ai refusé une demande de devoir/test supplémentaire sans compensation. J'espère que les choses s'amélioreront considérablement l'année prochaine et j'écrirai à nouveau la semaine prochaine.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!