Cellular automata, Rule 90, Reddit challenge



  • https://www.reddit.com/r/dailyprogrammer/comments/3jz8tt/20150907_challenge_213_easy_cellular_automata/

    Hallo,

    mein Verständnis ist folgendes:

    Sei dieses 3er Packet gegeben:

    000
    

    wird das zweite Element des Packets durch das Ergebnis einer XOR Operation auf das erste und dritte packet ersetzt. Sprich:

    000
    

    Weitere Beispiele:
    100 -> 110
    010 -> 000
    011 -> 011

    Habe ich hier schon etwas falsch verstanden? Es heißt in der Aufgabenstellung nämlich immer etwas wie "011 yields 1", wobei ich das automatisch als Ersatz für das zweite Element gesehen habe.

    Jetzt zu meiner eigentlichen Frage: Das erste und letzte Element im Input String

    1000001
    

    (hier die beiden 1er)
    hat ja nur einen Nachbarn. Ich verstehe leider nicht, welche Regel nun für diese gilt.

    1100011
    Die dick gedruckten Substitutionen würde ich verstehen, für die äußeren weiß ich es nicht.

    Ich wäre sehr dankbar, wenn wir jemand helfen könnte diese Aufgabenstellung korrekt zu verstehen.

    LG
    HarteWare



  • Ja, das fehlt in der Tat in der Beschreibung. Denk Dir einfach irgendwas sinnvolles aus, z.B. dass die Randelemente immer 0 sind.



  • Das Problem ist, dass am Ende ein schönes Muster rauskommen soll, daher wird "einfach irgendwas ausdenken" vermutlich nicht funktionieren. Vielleicht habe ich auch etwas übersehen, und es wird ganz anders gemacht, deshalb frage ich ja.

    Zur Not muss ich halt so lang rumprobieren bis es geht... Das ist aber eigentlich nicht meine bevorzugte vorgehensweise und hat auch nicht so viel mit programmieren zu tun :p



  • So lange kein 1er ganz an den Rand gewandert ist passt doch eh alles.
    Und sobald das passiert, gibt es keine Definition bei der das Ergebnis mit einer Simulation mit breiterem "Feld" übereinstimmen würde.

    Natürlich kannst du es auch so machen, dass du jeden Input der eine 1 ganz aussen enthält einfach mal um ein Element links bzw. rechts verbreiterst. Dann können nie 1er rauswandern, und das Ergebnis "stimmt" wieder.



  • @hustbaer
    Ich habe mal begonnen eine Lösung zu implementieren, welche immer davon ausgeht, dass ganz außen 0 steht, wie ja schon von SG1 vorgeschlagen wurde. Das funktioniert eigentlich ganz gut (die challenge konnte ich lösen).

    Und sobald das passiert, gibt es keine Definition bei der das Ergebnis mit einer Simulation mit breiterem "Feld" übereinstimmen würde.

    Diesen Satz habe ich zuerst garnicht verstanden (bin eben nicht der allerhellste).
    Jetzt ist mir aber aufgefallen, dass ab einer gewissen Anzahl Iterationen außen sozusagen "abgeschnitten" wird, da die Breite durch die größe der Eingabe festgelegt ist, das Muster aber theoretisch irgendwann darüber hinaus "wachsen" würde. So etwa war es doch gemeint, oder?

    Ich versuche nun einen "auto growth" Modus einzurichten, der dann für Szenarien, in denen 1er an den Rand kommen und das Bild sozusagen "abgeschnitten" wird, automatisch 0er angefügt werden.

    Ich werde das Programm wahrscheinlich posten wenn ich fertig bin, nur zum Spaß und vielleicht lern ich noch etwas dazu.



  • HarteWare schrieb:

    Und sobald das passiert, gibt es keine Definition bei der das Ergebnis mit einer Simulation mit breiterem "Feld" übereinstimmen würde.

    Diesen Satz habe ich zuerst garnicht verstanden (bin eben nicht der allerhellste).
    Jetzt ist mir aber aufgefallen, dass ab einer gewissen Anzahl Iterationen außen sozusagen "abgeschnitten" wird, da die Breite durch die größe der Eingabe festgelegt ist, das Muster aber theoretisch irgendwann darüber hinaus "wachsen" würde. So etwa war es doch gemeint, oder?

    Ja, so war das gemeint 🙂



  • Vielen Dank an alle die mir geantwortet haben 🙂

    Wen es interessiert kann eine mögliche Lösung hier anschauen:
    https://github.com/Raincode/Cellular-Automata-Rule-90 (15.09.2015)
    Kompilierte auf meinem System einwandfrei mit GCC 5.1.0 C++11 enabled.

    Screenshot: https://imgur.com/7uSNGC6(15.09.2015)

    Wer will darf mir auch gerne Feedback geben, ich würde mich sehr darüber freuen, da ich immer daran interessiert bin bessere Programme zu schreiben.

    P.S.
    Um das Bild aus der reddit challenge zu erhalten reicht es eine 1 einzugeben und "auto growth" zu verwenden.


Log in to reply