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 1014 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 Befehlssegmenten1) für den mir vorliegenden und auf dieser Seite zur Verfügung gestellten Input :

Variante A Variante B
1 inp w inp w
2 mul x 0 mul x 0
3 add x z add x z
4 mod x 26 mod x 26
5 div z 1 div z 26
6 add x 11 add x -5
7 eql x w eql x w
8 eql x 0 eql x 0
9 mul y 0 mul y 0
10 add y 25 add y 25
11 mul y x mul y x
12 add y 1 add y 1
13 mul z y mul z y
14 mul y 0 mul y 0
15 add y w add y w
16 add y 6 add y 12
17 mul y x mul y x
18 add z y add z y

Unterschiede:

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 <WERT> ein Wert zu x addiert. Hier gibt es zwei Fälle:

(1) <WERT> ist positiv und größer oder gleich 9: Dann ist in Zeile 7 x + <WERT> 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.