[Human Resource Machine] Hallo Welt

[Torin]

Vielleicht spare ich Schritte wenn ich zuerst prüfe, ob eine der beiden Zahlen Null beträgt und dann erst das Produkt initialisiere.

Gesagt, getan. Doch das macht es nur schlimmer.







Ein neuer Ansatz muss her, doch da wurden ja gerade Tipps geschrieben.

[Torin]

Tipps

Achtung Spoiler:

Zwei Ideen könnten dich weiter bringen: Entweder du nutzt eine Idee ähnlich dem Verachtfacher-Raum oder
führst ein sog. Loop Unrolling durch. Dabei werden beispielsweise zwei Schritte (Addieren) zusammen ausgeführt.

Danke, das bringt schon auf eine Idee. Später kommt ein neuer Befehl hinzu, der bei meiner Überlegung Schritte einsparen würde, doch nun muss ich ohne auskommen.

[Torin]

Ich lasse die größenoptimierte Version durchlaufen und sehe, dass keine Zahl größer als 9 ist.



Also speicher ich beide Zahlen, prüfe sie auf Null und bereite alles vor, um vielfache Werte der zweiten Zahl zu erstellen. Die zehn Kacheln bieten gerade so Platz bis zum Neunfachen.



Die Vielfachen der zweiten Zahl werden erzeugt und gespeichert.



Nun verringern wir die erste Zahl. Sollte sie jetzt schon Null erreichen, wird das Einfache der zweiten Zahl ausgegeben.



Diese Schritte wiederholen wir bis zum Neunfachen.







Ich überprüfe nochmal, ob alle JUMPs auch richtig gesetzt sind und dann kann unser Angestellter loslegen.





Am Ende haben wir zwei Schritte gut gemacht, fehlen noch weitere zehn.



Okay, jetzt bin ich für Leserlösungen offen!

[Ramkhamhaeng]

Dann probiere ich das mal. Am besten gleich zu Versuch zwei springen. Den ersten hab ich nur nicht gelöscht weil das die Lösung war, die mir bei meinen Tipps vorschwebte

Ich habe das Spiel mal in Python nachgebaut, daher kommt die komische Syntax im folgendem Code,
der hoffentlich trotzdem lesbar ist Bei den Tupeln steht vorne die Operation und dann ein Registername (oder None). Ein dritter Parameter steht für das Label dieser Zeile.

1. Versuch: Statt y*x wird (2y)*(x/2) berechnet. Dazu wird von x immer zweimal Eins abgezogen und y vor dem Start der Schleife verdoppelt. Falls x ungerade war muss dann am Ende noch einmal y abgezogen werden.

Da x und y unsymmetrisch behandelt werden ist aber nicht zu erwarten, dass das die Schrittzahl sehr gering wird (rund 118 Schritte).

Achtung Spoiler:

t.program = [
    (t.inbox, None, "anfang"),
    (t.copyto, "y"),
    (t.add, "y"),
    (t.copyto, "yy"),
    (t.copyto, "mul"),  # Jetzt 2y, spaeter 4y, ...
    (t.jumpz, "ende3"),

    (t.inbox, None),
    (t.jumpz, "ende4"),

    # Hier gilt x, y>0
    (t.copyto, "x"),

    # Scheife
        (t.bump_dec, "x", "loop_start"),
        (t.bump_dec, "x"),
        (t.jumpn, "ende2"),  # x war unerade und daher mul=(x+1)*y
        (t.jumpz, "ende1"),  # x war gerade und mul=x*y

        # Hier ist x>0, Berechne mul += 2*y
        (t.copyfrom, "mul"),
        (t.add, "yy"),
        (t.copyto, "mul"),
        (t.jump, "loop_start"),

    (t.inbox, None, "ende3"),       # Zweite Eingabe verbrauchen
    (t.copyfrom, "zero", "ende4"),  # Null auf Hand kopieren
    (t.outbox, None),
    (t.jump, "anfang"),

    (t.copyfrom, "mul", "ende2"),   # Ein y zu viel
    (t.sub, "y"),
    (t.outbox, None),
    (t.jump, "anfang"),

    (t.copyfrom, "mul", "ende1"),
    (t.outbox, None),
    (t.jump, "anfang"),
] 

2. Versuch: Wir nutzen (x*y) = (x-1)*(y-1) +x+(y-1) aus. Die letzten zwei Summanden (x, y-1) kann man aufaddieren und
den vordersten Summanden immer weiter absenken. Wir brechen ab sobald einer der beiden Faktoren Null erreicht. Das sind bei mir bei identischen Eingaben 102 Schritte, was aber nicht mit der Ausgabe im Programm übereinstimmen muss

Achtung Spoiler:

t.program = [
    (t.inbox, None, "anfang"),
    (t.jumpz, "ende3"),
    (t.copyto, "y"),
    (t.bump_dec, "y"),   # y-1
    (t.inbox, None),
    (t.jumpz, "ende2"),
    (t.copyto, "x"),
    (t.add, "y"),
    # Scheife
        (t.copyto, "sum", "loop_anfang"),   # x+(y-1)
        (t.bump_dec, "x"),   # x-1. Nun ist Schritt eins, zwei, ... abgeschlossen.

        (t.jumpz, "ende1"),  # Abbruch, da (x-1)*(y-1) Null

        (t.bump_dec, "y"),   # y-2
        (t.jumpn, "ende1"),  # Abbruch, da (x-1)*(y-1) Null

        (t.add, "x"),        #
        (t.add, "sum"),      # Nun x+(y-1) + (x-1)+(y-2)
        (t.jump, "loop_anfang"),

    # Enden

    (t.inbox, None, "ende3"),       # Zweite Eingabe verbrauchen
    (t.copyfrom, "zero", "ende2"),  # Null auf Hand kopieren
    (t.outbox, None),
    (t.jump, "anfang"),

    (t.copyfrom, "sum", "ende1"),
    (t.outbox, None),
    (t.jump, "anfang"),
] 

[Torin]

So ganz verstehe ich diese Berechnung in deinem zweiten Versuch nicht, aber ich übertrage einfach mal den Quellcode.





Sollte soweit richtig sein.





Dann haben wir immerhin einen Schritt gut gemacht, aber auf deine errechneten 102 kommen wir so nicht. Habe ich vielleicht einen Fehler gemacht?

Das Spiel ermöglicht übrigens auch die Ausgabe des erstellten Programms. Das sieht dann so aus:

-- HUMAN RESOURCE MACHINE PROGRAM --

a:
b:
    INBOX   
    JUMPZ    d
    COPYTO   0
    BUMPDN   0
    INBOX   
    JUMPZ    e
    COPYTO   1
    ADD      0
c:
    COPYTO   4
    BUMPDN   1
    JUMPZ    f
    BUMPDN   0
    JUMPN    g
    ADD      1
    ADD      4
    JUMP     c
d:
    INBOX   
e:
    COPYFROM 9
    OUTBOX  
    JUMP     a
f:
g:
    COPYFROM 4
    OUTBOX  
    JUMP     b


DEFINE LABEL 0
eJzjY2Bg4IoTlOOKm63amDjZVz8jov5Vpv1s+bzPkyIL1Dr1GvxlgUoY1LPtZ6dlT1+zOtP9/OrMzOcM
gwDcbI+oD+2MqO/pUWw70+M8r797/iaQ+Ly5WgZaMyWD1sx4Hp0/3SilaNq12qJpZlN1Z0xe+WLmkq0P
5hTuD19gdACkdsEWtc5D++eH7TnI41l01Nrm41F7e4Nja+I3Hd2S+vFoTNP6Y4/b1h/L3Pnx6N7jA+rZ
UTAKaAQAi9JMsA;

DEFINE LABEL 1
eJzjYWBg4Ip7pNVdKtmQ3BKzQbir7gRQiEG6PVO/oF7Qh72co2R2fmb319Suxedi9h5nGGBQvFZU8eua
R1rfV2sZ2KxicT6wIjfh8PItqYeXT65uXCHZcGDFj6l7V+6dabMqYHnZGtmNn9bO36S58d7GBVsCloP0
6x3fYHLvTIJm+HlZ9dOXZdWdri/W3nzns9nnOyzOX29HBNreLEwWvhjT9OY4y/yHpzkW9V8SXf33xuz1
b+/FbBhov4+CUUALAAALu1PY;

DEFINE LABEL 4
eJxzZGBgMAiYr3HEQ1RRzKlPJtm2TybPUlSx2DxGzcbkvbGdsbvrLxNR/7WWihHXHfUSj7v/ySr37a/4
6D+7MT8gtcMgILfPwvfgnIOe/cva3UNWXXeM2bDB4vGWOuMlWz31lbYAjWdIy07QLEx/FLEt9Vz519T3
/XkZbQvUs0NWJeZOXxNZMH0Nf0n/Mrfyprl7q973b62dXqfXkBr1poHHM7fhkdbypi2pc9p2TpNuj1gL
MuvZLNmNs+cZTepbLOjjvqzQ1HHFIy3HFRtM/q4861m8dkvq+3UhNWvXq21/tWH+pqWbQlbd32I29dY2
7zLJ7WbpV3bEhDjvl1V33q8Wvf/A0cJNR7sWvzu2YgfDKBgFIxgAAFhEd+Y;

DEFINE LABEL 9
eJyzZWBg+G8kq97rOl/D1vuR1ppALYP4MC2DB6GFpqohO6zeBTQ5HvFQjFhke6nqj3HXYjcDrV2PbPX2
7vfS26sc+nw7UDvDjxTJhhVZCa1z8+41hxUKVoUVOhfczdub/SrTLN0o/Xu6TbJ9bktCVylHfExTZ1xu
n0uC/Wzz1EsrMrNurZPPk904uUh249mSW+tAZmk27czQbJJseF+vtOVhS2a3WCdP+aSutqJz3UcLy6e0
FYHUlK3hKa9cfbKEdfnJEp8lAZWTFz5umz2PYc7seaKrry5I3XZi6fu9Nqs27Nuxes3uDesi1q5d7zwv
bz3QzHWitV/XXKpiGAWjYBTAAQC9Um+B;

[Torin]

[Torin]

[Torin]

[Torin]

Die Fibonacci-Folge ist in der Programmierausbildung sehr beliebt. So war es nur eine Frage der Zeit bis sie auch in diesem Spiel vorkommt.

Als erstes beschrifte ich die Kacheln, die ich benötige. Also die eingehende Zahl, die ausgehende Zahl mit ihren zwei Vorgängern. Die Null war bereits vorgegeben, aber ich gab ihr einen Namen.



Dann initialisieren wir erstmal das Programm. X-2 wird mit Null überschrieben und um Eins erhöht, dies wird dann in X-1 kopiert. Die Zahl vom Eingang wird in Y gespeichert. Danach wird in der grundlegenden Schleife die Summe X gebildet.



Im Nachhinein ist meine Beschriftung vielleicht etwas unpassend, da die beiden Vorgänger von X nicht zwingend um Eins und Zwei kleiner sind.

[Torin]

Nun vergleichen wir ob die Summe der beiden Vorgänger X größer als die eingehende Zahl Y ist. Ist dies der Fall, geht es mit der nächsten eingehenden Zahl weiter, ansonsten wird die aktuelle Summe dem Ausgang hinzugegeben.



Nach der Ausgabe von X, wird der Vorgänger von X der neue Vorvorgänger und X der neue Vorgänger.



Der Angestellte legt los und anfänglich sieht es gut aus.



Doch ich vergaß, dass ich zuerst zweimalig eine Eins ausgeben muss anstatt deren Summe.



Das korrigiere ich sofort und überprüfe außerdem ob die eingehende Zahl nicht Null ist, was die gesamte Rechnung hinfällig machen würde.

[Torin]

Jetzt sollte es aber funktionieren!



Das Programm läuft erfolgreich durch und wir haben die Laufzeitoptimierung sogar unterschritten.



Ich entferne die Überprüfung, ob die Zahl im Eingang Null ist und mache damit weitere zwei Schritte gut. In diesem Level kommen nur Zahlen größer Null.



Mir kommt eine weitere Optimierung durch den Sinn. Der Eingang wird zuerst gespeichert und dann werden die restlichen Werte initialisiert. Während der Angestellte bereits beim Setzen von X-2 und X-1 eine Eins in der Hand hat, gibt er diese auch gleich aus.



Nochmal sechs Schrite eingespart!

[Ramkhamhaeng]

Dann haben wir immerhin einen Schritt gut gemacht, aber auf deine errechneten 102 kommen wir so nicht. Habe ich vielleicht einen Fehler gemacht?

Verflixxt, dann fällt mir derzeit auch keine passende Lösung ein. Ich habe noch probiert eine Weiche einzubauen, die für x=y unterschiedliche Varianten ausführt, so dass nur min(x,y) mal addiert wird. Das hat die benötigten Schritte aber auch nicht weit genug gedrückt. Ich passe erst einmal

[Torin]

Dann belassen wir es erstmal dabei und schauen uns die nächsten Level an.

[Ramkhamhaeng]

Edit: Geklärt.

[Ramkhamhaeng]

Edit: Geklärt.