Einführung des Code-Day-Tastatur-Rätsels

Tag 21: Rätsel um die Tastatur

GitHub Repo – Lösung

Die heutige Herausforderung war schwierig und ich habe zwei Tage gebraucht, um sie zu lösen und die Logik vollständig zu verstehen. Etwas, das ich dieses Jahr festgestellt habe, ist, dass ich Schwierigkeiten hatte, die Absichten der Anweisungen zu verstehen.

Ich hoffe, dass Sie wie ich etwas aus dieser Herausforderung und Lösung gelernt haben. Ich finde, dass ich jedes Jahr, wenn ich an Advent of Code teilnehme, viel lerne, weshalb ich gerne verschiedene Sprachen ausprobiere oder mich aus meiner Komfortzone heraustreibe. Ich halte Advent of Code eher für eine Lern-/Entwicklungsmöglichkeit, bei der Entwickler ihr Wissen und ihre Ideen teilen sollten, anstatt es nur als Wettbewerb zu betrachten.

Heute wieder ein Versuch mit Python und ich bin mit der Lösung zufrieden. Etwas, das ich heute gelernt habe, war; Unveränderliche Klassen, die die Annotation @dataclass(frozen=True) in einer Klassendeklaration verwenden.

Ich habe die Location-Klasse als Hilfsklasse zum Navigieren und Aktualisieren von Koordinaten erstellt (ähnlich wie ich es zuvor mit der Point-Klasse in einigen C#-Lösungen gemacht habe.

Da ich über einen stark typisierten C#-/.Net-Hintergrund verfüge, habe ich versucht, Typen zu meinem Code hinzuzufügen, um mir zu veranschaulichen, womit ich bei diesem komplexen Problem gearbeitet habe. Ich bin es auch gewohnt, das zu tun, während ich TypeScript schreibe, also fast eine Selbstverständlichkeit.

Das heutige Problem

**Teil Eins ** führt in das Problem der Navigation und Steuerung mehrerer Roboter ein, um Anweisungen an den nächsten Roboter weiterzugeben, der Codes auf einem Ziffernblock eingibt.

Teil Zwei baut auf dem Problem auf, indem es die Komplexität durch eine Kette von Robotern und Richtungstastaturen erhöht und die exponentielle Natur mehrstufiger Abhängigkeiten demonstriert.

Komplettlösung

Da wir das Layout der Wegbeschreibung und der Tastatur bereits kennen, können wir die Wörterbücher aller Standortzuordnungen und Wegbeschreibungen erstellen, in die sie sich bewegen können.

Caching (Cache und Moves_Cache)

Cache: Speichert zuvor berechnete kürzeste Sequenzen, um redundante Berechnungen zu vermeiden und die Leistung zu verbessern.

moves_cache: Speichert alle gültigen Bewegungssequenzen zwischen zwei beliebigen Tasten auf einer Tastatur, vorberechnet für eine schnelle Suche.

Berechnung der kürzesten Länge (shortest_length)

Berechnet rekursiv die kürzeste Folge von Tastendrücken zur Eingabe eines bestimmten Codes.

Verwaltet die mehrstufige Verkettung von Tastaturen durch Iteration durch die Ebenen (cur_ Depth) bis zum Limit ( Depth_Limit).

*Bewegt sich zwischen Positionen (moves_between_positions)
*

Berechnet alle gültigen Bewegungsabläufe zwischen zwei Tasten auf einer Tastatur und stellt sicher, dass Roboter nicht in Panik geraten, indem sie auf ungültige Positionen (die Lücken) zeigen.

Cache-Initialisierung (create_cache_moves)

Berechnet gültige Bewegungssequenzen für alle Tastenpaare sowohl auf dem Ziffernblock als auch auf der Richtungstastatur vor und spart so Laufzeitberechnungen.

Die Lösungsfunktionen durchlaufen dann die Eingabe, berechnen deren Komplexität, indem sie die Sequenzlänge mit dem numerischen Teil des Codes multiplizieren, und summieren dann einfach die Komplexitäten für alle Codes gemäß den Anforderungen des Puzzles.

Permutationen

Was bewirken Permutationen?

Die Permutationsfunktion in Python (aus dem itertools-Modul) generiert alle möglichen geordneten Anordnungen einer Sammlung von Elementen.

Zum Beispiel:

from itertools import permutations

items = ['a', 'b', 'c']
list(permutations(items))

Dies ergibt:

[('a', 'b', 'c'), ('a', 'c', 'b'), ('b', 'a', 'c'), ('b', 'c', 'a'), ('c', 'a', 'b'), ('c', 'b', 'a')]

Jede Permutation ist eine einzigartige Sequenz, die alle Elemente in der ursprünglichen Sammlung enthält, jedoch in einer anderen Reihenfolge.

Warum Permutationen und keine Kombinationen verwenden?

Permutationen:

Erzeugt alle möglichen geordneten Anordnungen einer Artikelsammlung.
Die Reihenfolge der Artikel ist wichtig.

wobei
Kombinationen:

Erzeugt alle möglichen ungeordneten Auswahlen einer Sammlung von Elementen.

Die Reihenfolge der Artikel spielt keine Rolle.

Warum ist Ordnung in diesem Szenario wichtig?

Tastaturnavigation: Die Position des Roboters auf der Tastatur ändert sich nach jeder Bewegung, sodass die Reihenfolge, in der Bewegungen ausgeführt werden, direkten Einfluss auf das Ergebnis hat.

Prüfung gültiger Bewegungen: Die Funktion prüft die Gültigkeit von Zwischenpositionen während der Navigation. Eine Änderung der Reihenfolge der Bewegungen kann zu einem ungültigen Pfad führen.

Wann wären stattdessen Kombinationen sinnvoll?

Kombinationen können in Szenarien nützlich sein, in denen die Reihenfolge der Züge keine Rolle spielt oder Sie eine Teilmenge von Zügen oder Schaltflächen auswählen, ohne sich um deren Reihenfolge zu kümmern.

Die derzeitige Verwendung von Permutationen ist notwendig, da die Reihenfolge der Züge für die Tastaturnavigation von Bedeutung ist. Das Ersetzen durch Kombinationen würde die Logik des Programms zerstören. Wenn die Aufgabe das Finden aller eindeutigen Gruppen von Bewegungen oder Tasten unabhängig von der Reihenfolge erfordern würde, wären Kombinationen besser geeignet.

Der schwierigste Teil des Rätsels bestand darin, eine schöne und saubere Möglichkeit zu finden, die Tiefe (Anfangsebene) von Roboteranweisungen zu verfolgen – es hat eine Weile gedauert, bis ich meine volle Aufmerksamkeit darauf richten konnte.

Das obige ist der detaillierte Inhalt vonEinführung des Code-Day-Tastatur-Rätsels. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!