Zählzyklen in einem Falt- und Quetschprozess

8

In der Chaostheorie ist die Hufeisenkarte ein Beispiel dafür, wie Chaos in einem einfachen Prozess des Faltens und Quetschens entsteht. Es geht so: Nehmen Sie ein imaginäres Stück Teig, falten Sie es und zerdrücken Sie es schließlich auf seine ursprüngliche Größe. Chaos entsteht in dem Muster, wie die Teigstücke nach n Iterationen in der endgültigen Anordnung enden.

Beispiel eines invarianten Maßes

In unserem Fall schauen wir uns an, wie sich ein einfaches binäres Muster verhält, wenn wir es falten und quetschen . Hier sind die Schritte mit einem 8-Bit-Beispiel (die binäre Darstellung von 201 oder 11001001).

  1. Schneiden Sie die Bits in zwei gleich lange Stücke (fügen Sie am Anfang eine '0' hinzu, wenn eine ungerade Anzahl von Bits vorhanden ist).

    1100 | 1001

  2. Falten Sie die erste Hälfte über die zweite Hälfte. Beachten Sie, dass die Reihenfolge der ersten Hälfte umgekehrt ist, da wir sie beim Falten drehen.

    0011
    1001

  3. Squash in seine ursprüngliche Form. Während des Quetschens werden die oberen Bits unter ihrer ursprünglichen Position nach links zu den Bits verschoben.

    01001011

Wenn wir dies für dieses Beispiel wiederholen, können wir sehen, dass wir nach 4 Iterationen wieder zur ursprünglichen Bitfolge zurückkehren:

Start  bits: 11001001
Iteration 1: 01001011
Iteration 2: 01001101
Iteration 3: 01011001
Iteration 4: 11001001

Für den Dezimalwert von 201 beträgt die Anzahl der Zyklen also 4.

Die Herausforderung

  • Schreiben Sie ein vollständiges Programm, das eine Dezimalzahl als Eingabe verwendet und die Anzahl der Zyklen ausgibt, die zum Wiederholen im oben beschriebenen binären Squash-and-Fold-Prozess erforderlich sind.
  • Die (Dezimal-) Eingabe muss von stdin stammen (Bereich: von 1 bis Googol oder 10 ^ 100).
  • Die (Dezimal-) Ausgabe muss in stdout geschrieben werden.
  • Ihre Punktzahl ist die Anzahl der Bytes Ihres Codes.
  • Ihre Antwort muss mit [Programmiersprache] - [Punktzahl in Bytes] beginnen.
  • Standardlücken sind nicht erlaubt.

Beispiele

7 --> 3
43 --> 5
178 --> 4
255 --> 1
65534 --> 1
65537 --> 12
1915195950546866338219593388801304344938837974777392666909760090332935537657862595345445466245217915 --> 329

Schlussbemerkung

Interessant ist, dass die Anzahl der Zyklen mit der Länge der Binärdarstellung zusammenhängt, mit Ausnahme einiger Ausnahmen, bei denen die Anzahl der Zyklen aufgrund des Musters in der Bitfolge kürzer ist (z. B. 111110Zyklen nach 1 Iteration). Dies bietet eine interessante Möglichkeit, die Codelänge mithilfe des zugrunde liegenden Musters zu optimieren, anstatt die Anzahl der Zyklen zu berechnen.

agtoever
quelle
Wenn sich die Bitlänge der Zahl während der Iteration verkürzt, schneiden und falten wir dann mit der ursprünglichen oder der aktuellen Bitlänge?
xnor
2
@xnor Ich würde das Original annehmen, sonst würdest du den Zyklus nie abschließen, oder?
Martin Ender
Siehe auch
Digital Trauma

Antworten:

4

CJam, 34 Bytes

q~2b_,2%,\+{__,2//~\W%.\_W$=!}g;],

Nichts Besonderes, es wendet nur die Karte an, bis wir zur Eingabe zurückkehren und die Anzahl der Iterationen drucken, die benötigt wurden.

Testen Sie es hier.

Martin Ender
quelle
Erster! Schau dich an und schieße schneller als dein Schatten!
Agtoever
3

Python 2, 175 154 149 Bytes

i=bin(input())[2:]
i=o='0'+i if len(i)%2 else i
c=0
j=len(i)/2
while i!=o or c==0:
 a=''
 for x,y in zip(i[:j][::-1],i[j:]):a+=x+y
 i,c=a,c+1
print c

Ideone Link

Vielen Dank an agtoever für 27 Bytes!

Celeo
quelle
1
Keine Notwendigkeit für das Lambda. Sobald die Länge gerade ist, bleibt sie gerade.
Immer
Hervorragender Punkt, danke!
Celeo
Ändern Sie `while 1` mit while i!=o|c==0und lassen Sie das fallen if i==o:break. Speichert 5. Vielleicht (beachten Sie sicher) brauchen Sie auch nicht a. Einfach benutzen i. Speichert eine Zuordnung (4 Bytes). Auch die Zuordnung von j kann außerhalb der Schleife erfolgen.
Bis zum
Vielen Dank für die zusätzlichen Speicherungen, @agtoever. Ich habe beim Versuch, den while i!=c|c==0Ersatz zu implementieren , einen TypeError erhalten , konnte aber dennoch einige Bytes mit einem Standard- `oder` speichern.
Celeo