Advent of Code – Day-Claw-Apparat

Tag 13: Klauenapparat (Mathe, Mathematik und noch mehr Mathematik).

Link zur Lösung

Die heutige Challenge wurde zur Abwechslung in Python durchgeführt. Diese Auswahl wurde getroffen, um:
a) Teste mein Python / lerne mehr Python
b) Es sah heute wie ein sehr schweres mathematisches Rätsel aus, also hatte ich das Gefühl, dass Python perfekt wäre, und ich habe mich NICHT geirrt – es war blitzschnell.

Willkommen zum heutigen Rätsel, einer Lektion in Mathematik trauriges Gesicht, ich hatte keine Ahnung, wie ich dieses Problem lösen sollte (Teil 2), zuerst habe ich es brutal erzwungen und eine Schleife über ( (maximal 100 Mal), bis die richtige „Route“ gefunden wurde.

Was für Teil 1 wie erwartet gut funktioniert hat. Für Teil 2 wusste ich jedoch, dass dies nicht der Fall sein würde, also ging ich zurück und suchte nach einem mathematischen Ansatz. Ich hatte eine Ahnung, dass dies das sein musste, wohin uns das Team drängte. Beim Googeln bin ich nach langem Suchen auf Cramers Rule gestoßen (das ist übrigens das erste Mal, dass ich davon gehört habe).

Die Aufgabe bestand darin:

Berechnen Sie die Mindestkosten, um den Preis per Knopfdruck zu erreichen.

Bestimmen Sie für Teil 1, ob es möglich ist, das Ziel durch Drücken von Tasten zu erreichen, und ob dies die größte Menge an Preisen ist, die Sie innerhalb von 100 Tastendrücken erfolgreich gewinnen können, sowie die Kosten dafür.

Optimieren Sie für Teil 2 die Leistung, indem Sie große Koordinatenversätze handhaben, indem Sie im Wesentlichen die 100-Tastendruck-Grenze aufheben und den Preisstandort in den Abgrund treiben.

Lösung

Die Cramer-Regel scheint ein hervorragender Ansatz zur Lösung dieses Problems zu sein, da sie es Ihnen ermöglicht, lineare Gleichungen effizient zu lösen, die beschreiben, wie die Klaue bewegt werden muss, um den Preis in jeder Maschine zu erreichen. Lassen Sie uns zusammenfassen, warum und wie die Cramer-Regel gilt:

Problemaufschlüsselung

Für jede Klauenmaschine haben wir zwei Gleichungen:

Gleichung 1 (von Schaltfläche A):
a1 * A b1 * B = c1

Gleichung 2 (von Schaltfläche B):
a2 * A b2 * B = c2

Wobei a1 und b1 die Bewegungen entlang der X- und Y-Achse für Knopf A sind, A die Häufigkeit ist, mit der der Knopf A gedrückt wird, und c1 die Zielposition ist auf der X-Achse (Preisposition).

wobei a2 und b2 die Bewegungen entlang der

Für jede Klauenmaschine möchten wir nach der Anzahl der Tastendrücke A und B (wie oft die Tasten A und B gedrückt werden müssen) suchen, die die Klaue an den Koordinaten (c1, c2) mit dem Preis ausrichten. auf der X- und Y-Achse.

Warum Cramers Regel nützlich ist

Die Cramer-Regel wurde speziell zur Lösung linearer Gleichungssysteme entwickelt. Ein System linearer Gleichungen ist einfach ein Satz von zwei oder mehr Gleichungen, die gemeinsame Variablen haben, und das Ziel besteht darin, Werte für diese Variablen zu finden, die alle Gleichungen gleichzeitig erfüllen.

Einfacher ausgedrückt:

Stellen Sie sich vor, Sie haben mehrere Gleichungen, die beschreiben, wie Dinge zusammenhängen.

Jede Gleichung verwendet dieselben Variablen (z. B. x und y), und Sie versuchen, Werte für diese Variablen zu finden, die alle Gleichungen gleichzeitig wahr machen.

In diesem Fall kann die Tastenkonfiguration jeder Maschine als 2x2-System linearer Gleichungen dargestellt werden, in dem wir nach zwei Unbekannten suchen, A (Taste A drückt) und B (Taste B drückt).

Woher soll ein Entwickler wissen, dass er in Zukunft die Cramer-Regel verwenden soll?

Gleichungssystem: Das erste, was ein Entwickler tut, ist zu erkennen, dass das Problem die Lösung eines linearen Gleichungssystems erfordert.

Mustererkennung: Entwickler erkennen, dass es sich um ein 2x2-System handelt und dass die Cramer-Regel eine einfache Möglichkeit zur Lösung ist.

*Determinanten und Matrizen: * Sie erinnern daran, dass Determinanten zur Lösung der Unbekannten in linearen Gleichungen verwendet werden können, und wenn die Determinante Null ist, deutet dies auf ein Problem hin (keine oder unendliche Lösungen).

Einfachheit und Klarheit: Die Cramer-Regel bietet eine einfache, direkte Methode, um die Werte von A und B zu ermitteln, ohne dass iterative Methoden oder komplexe Algebra erforderlich sind.

Beispiel: Erste Klauenmaschine

Die Tastenbewegungen und Preispositionen sind wie folgt:

Button A moves the claw X+94, Y+34.
Button B moves the claw X+22, Y+67.
Prize location is at X=8400, Y=5400.

Wir haben das Gleichungssystem:

94 * A + 22 * B = 8400   (Equation for X-axis)
34 * A + 67 * B = 5400   (Equation for Y-axis)

Schritt 1: Determinanten berechnen
Hauptdeterminante D:
Die Determinante D wird nach folgender Formel berechnet:

D = a1 * b2 - a2 * b1

Ersetzen der Werte:

D = (94 * 67) - (34 * 22)
D = 6298 - 748
D = 5550

Determinante für A, D_x:
Als nächstes berechnen wir die Determinante D_x mit der Formel:

D_x = c1 * b2 - c2 * b1

Ersetzen der Werte:

D_x = (8400 * 67) - (5400 * 22)
D_x = 562800 - 118800
D_x = 444000

Determinante für B, D_y:
Berechnen Sie nun die Determinante D_y mit der Formel:

D_y = a1 * c2 - a2 * c1

Ersetzen der Werte:

D_y = (94 * 5400) - (34 * 8400)
D_y = 507600 - 285600
D_y = 222000

Schritt 2: Lösen Sie nach A und B auf
Mithilfe der Cramer-Regel lösen wir nun A und B:

A = D_x / D
B = D_y / D

Lösen Sie nach A:

A = 444000 / 5550
A = 80

Lösen Sie nach B:

B = 222000 / 5550
B = 40

Schritt 3: Auf gültige Ganzzahlen prüfen
Sowohl A als auch B sind ganze Zahlen, was bedeutet, dass es möglich ist, den Preis für diese Klauenmaschine zu gewinnen.

Schritt 4: Gesamtkosten berechnen
Die Kosten für das Drücken von Knopf A betragen 3 Token, und die Kosten für das Drücken von Knopf B betragen 1 Token. Die Gesamtkosten für den Gewinn des Preises betragen also:

Button A moves the claw X+94, Y+34.
Button B moves the claw X+22, Y+67.
Prize location is at X=8400, Y=5400.

Teil2 – verwendet die gleiche Logik, der einzige Unterschied besteht darin, dass wir den 10^13-Versatz sowohl zur X- als auch zur Y-Achse der Preiskoordinaten hinzufügen.

Ich weiß, dass das eine Menge ist, und ich glaube, es hat mich auch sehr viel gekostet, es zu verstehen/zu begreifen. Ich freue mich über ein Gespräch, Sie können mich über Twitter erreichen.

Das obige ist der detaillierte Inhalt vonAdvent of Code – Day-Claw-Apparat. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!