Tomb Raider - Rätsel



  • Hey,

    kurze Zusammenfassung: Man steht vor sieben Statuen. Bei einem Knopfdruck an einer Statue i wird diese aktiviert(ON). Jedoch werden auch die Stauten i+3 und i+4, jeweils mod7, aktiviert. D.h. wird eine Statue i aktiviert, dann lässt man die nächsten zwie auf OFF, aber die zwei dann danach auf ON.

    Bsp: 0010000 --> 0010011 oder 0000001 --> 0011001

    Der Status der Statuen werden in ein Array(Statue 0 bis 7) gespeichert, also je ein Feld belegt eine Binärzahl. Und wenn alle Statuen auf ON sind, ist das Rätsel gelöst.

    Jedoch bin ich mir nicht ganz sicher, was folgendes Zitat zu dieser Aufgabe meint:

    First of all, a little thinking shows that the final states of the statues after pressing some buttons does not depend on the dequence in which the buttons have been pressed, and pressing a button twice euqals to not pressing it at all. Consequently, we can restrict the search for solutions to such solutions where each button is pressed either exactly once or never.

    Aufgabe ist es nun alle 128 Möglichkeiten durchzuprobieren und die Möglichkeiten zu zeigen, sodass alle Statuen am Ende auf ON, also das Array mit
    Einsen befüllt ist.

    Mein Bedenken ist folgendes:
    Ich dachte mir, dass ich jede Möglichkeit einzeln überprüfe. D.h. von 0000000 bis 1111111. Also dazwischen auch z.B. 1111000 oder 0010101 etc.

    Nehmen wir als Beispiel 1110000 her. In dem obigen Zitat steht doch, dass das zweimalige Drücken einer Statue keinmal drücken meint. Und es steht auch, dass die Reihenfolge des aktivieren keine Rolle spielt.

    Also drücke ich als erstes de ganz linke Statue im array[0], was mir dann 1001100 liefert. Dann array[1] und ich bin bei 1101010. Dann mit array[2] bei 1111001, nachdem ich also Statue 0, Statue 1 und Statue 2 hintereinander aktiviert habe.

    Ich denke so ist gemeint? Und das wäre auch am logischten. Nur ist noch nicht ganz klar, was mit dem zweimaligen Drücken einer Statue gemeint wird? Wenn eine Statue auf 1 geht, geht sie wieder auf Null natürlich, wenn eben i+3 ider i+4 genau diese Staute ist.

    Was meint ihr dazu?

    LG


  • Mod

    Ja.

    Du musst alle Möglichkeiten einzeln prüfen, von 0000000 bis 1111111.

    Mit der Erklärung bezieht sich darauf, dass obige Prüfung der 128 Möglichkeiten ausreichend ist. Denn du musst bei 1111111 eben nur prüfen, was heraus kommt, wenn alle Hebel gedrückt wurden. Du musst eben nicht prüfen, ob etwas anderes heraus kommt, wenn du zuerst Hebel 1 drückst, als wenn du zuerst Hebel 2 drückst, etc., denn das Ergebnis ist in allen Fällen das gleiche.

    Und ebenso musst du beispielsweise bei 0000000 nicht prüfen, ob nicht eventuell ein anderes Ergebnis heraus käme, wenn Hebel 1 erst umgelegt und dann wieder zurück gelegt wird, denn es wird stets das gleiche Gesamtergebnis heraus kommen.

    Wenn eine Statue auf 1 geht, geht sie wieder auf Null natürlich, wenn eben i+3 ider i+4 genau diese Staute ist.

    Das geht eben nicht nur mit dem Nullzustand, sondern mit jedem Zustand, dass dieser wieder hergestellt wird, wenn der Hebel zweimal getätigt wird.

    Beispiel:
    Sei der Zustand 0101010.
    Drücke nun Hebel 1. Heraus kommt: 1100110
    Betätige Hebel 1 noch einmal, heraus kommt: 0101010.
    Tadaa!

    Und das funktioniert genauso, selbst wenn man zwischendurch beliebig viele andere Hebel tätigen sollte, denn es ist eine Eigenschaft von XOR (welches hier effektiv benutzt wird), dass
    (A XOR 😎 XOR B = A XOR (B XOR 😎 = A XOR 0 = A
    und auch
    A XOR B XOR C XOR B = A XOR B XOR B XOR C = A XOR 0 XOR C = A XOR C



  • Ahh ok, danke. Anfangs wollte ich nämlich das ohne XOR programmieren, indem ich vorher gucke an welchen Stellen sich meine 1er befinden und dann mit der von mir anfangs genannten Methode fortfahren, jedoch mit XOR vereinfacht sich das ganze bzw. geht auch schneller.

    D.h. also, wenn man so ähnlich Sachen hat mit 'zweimal dasselbe machen ändert nichts' etc., dann ist das immer ein gutes Stickwort für XOR? Also unabhängig von der Wirkung die ich jetzt vom Drücken eines Hebels bekomme. Z.B. könnte man auch beim Drücken des Hebels auch die Statuen i+1 und i+3 oder was auch immer ändern und es wäre dasselbe Prinzip.

    Mit XOR kann ich nämlich jeden Schritt A,B,C einzeln betrachten und alle einzelnen Ergebnisse A,B,C dann mit XOR verknüpfen und fertig.

    Auf das will man hinaus?

    edit: Also ich nehme an, dass man für solche Probleme einfach logische Verknüpfungen nimmt, ob jetzt XOR, AND, OR etc. hängt dann halt von dem Problem ab.


  • Mod

    C_Boy schrieb:

    D.h. also, wenn man so ähnlich Sachen hat mit 'zweimal dasselbe machen ändert nichts' etc., dann ist das immer ein gutes Stickwort für XOR?

    Umgekehrt. Dies ist eine wichtige Eigenschaft von XOR, aber natürlich gibt es auch andere Dinge, die diese Eigenschaft haben. Aber wenn du irgendwo siehst, dass XOR benutzt wird, dann hat es fast immer etwas damit zu tun, dass XOR diese Eigenschaft hat.



  • Verstehe.

    Ich habs nun fertig programmiert und sehe, dass nur Einsen überbleiben können, wenn ich 1111111 reinschicke, also alle Statuen in willkürlicher Reihenfolge aktiviere.

    Um 1111111 müsste ich folgendes ver-XOR-en:

    1001100
    0100110
    0010011
    1001001
    1100100
    0110010
    0011001

    Das ist genau das, wenn ich 111111 reinschicke und wenn ich jetzt eine oder mehrer Zeilen durch ne Null ersetze komme ich immer wieder irgendwo auf eine gerade Anzahl von Einsen und das Ergibt ja mit XOR eine Null.

    Stimmt das so bzw. ist das eben die Eigenschaft von XOR, dass hier eben nur auf 1111111 komme, wenn ich auch 1111111 reinschicke?


Log in to reply