So verfolgen Sie Schritte in einer Karte, Advent of Code, 6

Zurück zu meiner Advent of Code-Herausforderung: Aufgrund einiger unvorhersehbarer Probleme kann ich die Herausforderungen nicht rechtzeitig abschließen und bin derzeit etwa 5–6 Tage im Rückstand. Ich bin jedoch immer noch fest entschlossen, die Rätsel dieses Jahr zu lösen. Lassen Sie uns heute das 6. Rätsel besprechen.

Copilot-generiertes Bild, das einigermaßen zum Thema passt

Die Suche nach Dingen in einer 2D-Ebene scheint dieses Jahr ein wiederkehrendes Thema zu sein. Heute begeben wir uns auf die Spuren eines Wächters, der über eine klare, definierte Bewegungslogik verfügt. Der Wächter bewegt sich in einer geraden Linie und biegt nach rechts ab, wenn er behindert wird.

Angenommen, wir stellen jeden Schritt, den der Wächter macht, als Punkt in einer 2D-Ebene dar, dann können wir jeden Schritt in eine andere Richtung als Vektoren darstellen:

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

Indem wir einige Berechnungen wie unten gezeigt durchführen, erhalten wir eine Matrix, die die richtige Drehung darstellt

Ableitung der Rotationsmatrix

Ursprünglich wurde dies als Wörterbuch dargestellt, da wir uns bei zahlreichen Berechnungen stark darauf verlassen werden. Ich wollte jedoch die richtigen Typanmerkungen sicherstellen, daher diese Implementierung vorerst.

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

Wir benötigen außerdem ein Mittel zur Darstellung von Position und Bewegung sowie Methoden zur Manipulation der Position und zur Ausführung von Rotationen:

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,
        )

Durch die Definition der Dunder/Magic-Methoden __add__ und __mul__ können sowohl Point- als auch Direction-Objekte manipuliert werden, als wären sie standardmäßige arithmetische Operationen im Code. Das Snippet zeigt auch, wie man die Rotationsklasse effektiv mit Typannotationen versehen kann.

Zuletzt definieren wir die Modelle für unsere Eingabe:

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 ist eine Standard-Enumeration, die die Bedeutung verschiedener Symbole innerhalb der Eingabe kapselt. „Leerzeichen“, „Schutz“ und „Hindernis“ haben selbsterklärende Bedeutungen. Die Tafel ist eine Darstellung der Karte. Mein ursprünglicher Ansatz beinhaltete einen eher objektorientierten Entwurf, aber ich habe mich letztendlich für diese Implementierung entschieden, bei der jede Klasse einfach einen Zustand beibehält, der leicht überprüft werden kann.

Beginnen wir mit dem Parsen der Eingabe:

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)),
    )

Der Wächter wird durch ein Point-Objekt dargestellt. Die Finder-Funktion ist dafür verantwortlich, die Eingabe zu scannen und die Positionen des gewünschten Symbols zu identifizieren. Ähnliche Lösungen für das Parsen von 2D-Karten werden in nachfolgenden Beiträgen weiter untersucht.

Meine Lösung für Teil 1 ist relativ einfach. So berechnen Sie den nächsten Schritt des Wächters:

1. Bestimmen Sie anhand des aktuellen Richtungsvektors das gewünschte Ziel direkt vor der Wache.
2. Überprüfen Sie, ob das gewünschte Ziel blockiert ist.
3. Wenn das gewünschte Ziel blockiert ist: Wir geben das gewünschte Ziel und den aktuellen Richtungsvektor zurück.
4. Wenn das gewünschte Ziel nicht versperrt ist: Wir geben die aktuelle Position und den gedrehten Richtungsvektor zurück.

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

Abschließend befassen wir uns mit Teil 1 der Herausforderung, bei dem es darum geht, die Anzahl der einzigartigen Kacheln zu bestimmen, die der Wächter besucht.

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

Teil 2 wirft einen Curveball auf uns! Wir haben die Aufgabe, den perfekten Ort für die Platzierung eines neuen Objekts auf der Karte zu finden, damit unser Roboter für immer in einer Schleife patrouillieren kann.

Die gute Nachricht ist, dass es kein Hexenwerk ist, den richtigen Ort zu finden. Wir kennen den ursprünglichen Weg des Roboters aus Teil 1, also müssen wir das Objekt nur irgendwo entlang dieser Route platzieren.

Jetzt der knifflige Teil: Woher wissen wir, ob wir erfolgreich eine Schleife erstellt haben?

Hier ist mein Ansatz:

1. Verfolgen Sie die Bewegungen des Roboters:Anstatt seine genaue Position zu verfolgen, habe ich mich darauf konzentriert, jeden „Schritt“ aufzuzeichnen, den er macht. Jeder Schritt ist im Grunde ein Übergang von einer Kachel zur nächsten.
2. Suchen Sie nach sich wiederholenden Mustern:Wenn der Roboter anfängt, dieselbe Schrittfolge zu wiederholen, haben wir eine Schleife!
3. Stellen Sie sicher, dass er auf der Karte bleibt: Entscheidend ist, dass wir sicherstellen müssen, dass der Roboter nicht von der Karte abweicht.

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,
        )

Der Grund, warum ich mich dafür entschieden habe, die Schritte in einem Wörterbuch zu speichern, ist, dass die Reihenfolge der Schritte für diesen Teil des Problems keine Rolle spielt (was auf ein ähnliches Konzept in einem späteren Rätsel hinweist).

Da ich häufig überprüfen musste, ob ein bestimmter Schritt bereits ausgeführt wurde, verbesserte das Speichern der Schritte in einem Wörterbuch die Leistung erheblich. Wörterbücher in Python sind beim Nachschlagen unglaublich schnell, wodurch diese Prüfungen im Vergleich zur Verwendung einer Liste oder eines Tupels viel schneller erfolgen.

Bei meinem ersten Versuch, der eine andere Datenstruktur verwendete, dauerte es etwa 70 Sekunden, bis er auf allen 8 Kernen meines Rechners lief. Durch den Umstieg auf ein Wörterbuch konnte ich die Laufzeit deutlich auf wenige Sekunden reduzieren. Dies zeigt, wie wirkungsvoll es ist, die richtige Datenstruktur für die jeweilige Aufgabe auszuwählen!

Das war’s für heute. Angesichts der Laufzeitverbesserung von 70 Sekunden auf allen Kernen auf nur wenige Sekunden auf einem einzelnen Kern bin ich mit der Optimierung recht zufrieden, obwohl ich weiß, dass weitere Verbesserungen möglich sind (idealerweise mit dem Ziel einer Ausführung in weniger als einer Sekunde).

Mein vorheriger Versuch, einen Job zu bekommen, endete nicht gut (ja, immer noch #OpenToWork, ping mich an!), da ich eine Anfrage für eine zusätzliche Aufgabe/einen zusätzlichen Test ohne Entschädigung abgelehnt habe. Hoffentlich wird es nächstes Jahr deutlich besser, und ich werde nächste Woche wieder schreiben.

Das obige ist der detaillierte Inhalt vonSo verfolgen Sie Schritte in einer Karte, Advent of Code, 6. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!