Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- faecher:informatik:oberstufe:java:aoc:aoc2021:day24:start [26.12.2021 16:31] – [Was passiert also?] sbel
+++ faecher:informatik:oberstufe:java:aoc:aoc2021:day24:start [Unbekanntes Datum] (aktuell) – gelöscht - Externe Bearbeitung (Unbekanntes Datum) 127.0.0.1
@@ Zeile 1: / Zeile 1: @@
-====== Tag 24: Arithmetic Logic Unit  ======
-===== Untersuchung des Problems =====
-Zunächst kann man einen Parser implementieren, der die Abläufe in der ALU simuliert. Diesen kann man probeweise anschließend mit dem als Puzzle Input gegebenen Programm und einigen 14 stelligen Modellnummern füttern, um die Funktionsweise zu testen.
-Man wird sehr wahrscheinlich erkennen, dass der Wert des z-Registers - scheinbar unabhängig von der eingegebenen Modellnummer - immer größer wird.
-Der Versuch, alle denkbaren Modellnummern in der so geschaffenen ALU durch das Programm prüfen zu lassen, schlägt (zumindest mit Java) fehl, da die Eingabemenge mit 10<sup>14</sup> potentiellen Kandidaten dafür  zu groß ist.
-===== Reverse Engeneering =====
-Man sollte sich also als nächstes den als Puzzle-Input gegebenen Code ansehen. Bei einer ersten Analyse fällt auf, dass die 14 Segmente, die jeweils von einem ''inp w'' Befehl eingeleitet werden, der die nächste Ziffer der Modellnummer einliest sich sehr ähnlich sind. Im wesentlichen gibt es zwei Arten von jeweils 18 Zeilen langen Befehlssegmenten((für den mir vorliegenden und auf dieser Seite zur Verfügung gestellten Input)):
-<code>
-  Variante A       Variante B
-  inp w            inp w
-  mul x 0          mul x 0
-  add x z          add x z
-  mod x 26         mod x 26
-  div z 1          div z 26
-  add x 11         add x -5  (ADD_TO_X)
-  eql x w          eql x w
-  eql x 0          eql x 0
-  mul y 0          mul y 0
-add y 25         add y 25
-mul y x          mul y x
-add y 1          add y 1
-mul z y          mul z y
-mul y 0          mul y 0
-add y w          add y w
-add y 6          add y 12  (ADD_TO_Y)  Hier ist immer y=w+ADD_TO_Y
-mul y x          mul y x
-add z y          add z y
-</code>
-==== Betrachtung der Unterschiede und Auswirkungen ====
-  * In Zeile 5 taucht wahlweise ''div z 1'' oder ''div z 26'' auf. Ersteres verändert den wert von ''z'' nicht, letzteres dividiert z durch 26.
-  * In Zeile 6 wird mit ''add x ADD_TO_X'' ein Wert zu x addiert. Hier gibt es zwei Fälle:
-    * (1) ''ADD_TO_X'' ist positiv und größer oder gleich 9: Dann ist in Zeile 7 ''x + ADD_TO_X'' niemals gleich ''w'', da ''w'' eine Ziffer zwischen  0 und 9 ist. Das hat zur Folge, dass in Zeile 7 ''x'' immer auf ''0'' und in Zeile 8 ''x'' auf ''1'' gesetzt wird.
-    * (2) ''ADD_TO_X'' ist negativ: Das tritt nur dann auf, wenn der Befehl in Zeile 5 ''div z 26'' lautet. Nun hängt es davon ab welcher Wert in ''x'' gespeichert ist, ob in Zeile 7 ''x + ADD_TO_X'' gleich ''w'' ist oder nicht - meist ist er das nicht, wenn doch ist ''x'' nach Zeile 8 ''0''.
-  * In Zeile 16 unterscheiden sich die Anweisungen in der Zahl, die hier mit dem Befehl ''add y ADD_TO_Y'' zum Register ''y'' addiert wird.
-  * Zum genaueren Verständnis ist außerdem die Bedeutung von Zeile 13 interessant:
-    * Wenn ''x=1'' ist, wird der Wert von ''z'' hier mit 26 multipliziert.
-    * Wenn in seltenen Fällen ''x=0''ist , bleibt ''z'' unverändert. da die Zeile 10, in der y auf 25 gesetzt wird durch Zeile 11 "annuliert" wird, so dass nach Zeile 12 ''y=1'' ist.
-Interessant sind also vor allem die Fälle, bei denen in Zeile 5 ''div z 26'' steht, im weiteren verlauf in Zeile 6 ''x'' verkleinert wird ''und'' in Zeile 7 der auf diese Weise berechnete x-Wert gleich der Eingabeziffer ''w'' ist. Nur dann wird nämlich der Wert im Register ''z'' kleiner als zuvor, und dieser soll ja am Ende 0 sein.
-==== Was passiert also? ====
-Das Register ''z'' implementiert einen [[ faecher:informatik:oberstufe:adt:stack:start|Stapel]], af dem in jedem Schritt die Summe aus der Ziffer der Modellnummer und ADD_TO_Y abgelegt wird.
-=== Standardfall ===
-(''div z 1'' und ''add x <WERT>'' mit ''<WERT> > 0'')
-<code>
-Ziffer(w)     y               z
-Start         0               0
-             3+ADD_TO_Y      3+ADD_TO_Y
-             2+ADD_TO_Y      (26*z1) + (2+ADD_TO_Y)
-             4+ADD_TO_Y      (26*z2) + (4+ADD_TO_Y)
-....
-</code>
-=== Variante B - 1 ===