Das unendliche Fibonacci-Wort ist eine bestimmte, unendliche Folge von Binärziffern, die durch wiederholte Verkettung endlicher Binärwörter berechnet werden.
Nehmen wir definieren , dass eine Fibonacci-Typ Wortsequenz (oder FTW - Sequenz ) ist jede Sequenz ⟨W n ⟩ , die wie folgt gebildet wird.
Beginnen Sie mit zwei beliebigen Arrays von Binärziffern. Nennen wir diese Arrays W -1 und W 0 .
Für jedes n> 0 , lassen W n ≔ W n-1 ∥ W n-2 , wobei ∥ Bezeichnet Verkettung.
Eine Folge der rekursiven Definition ist, dass W n immer ein Präfix von W n + 1 und damit von allen W k ist, so dass k> n ist . In einem gewissen Sinne bedeutet dies die Sequenz ⟨W n ⟩ konvergiert zu einem unendlichen Wort.
Formal sei W ∞ das einzige unendliche Array, so dass W n ein Präfix von W ∞ für alle n ≥ 0 ist .
Wir bezeichnen jedes durch den obigen Prozess gebildete unendliche Wort als unendliches FTW .
Aufgabe
Schreiben Sie ein Programm oder eine Funktion, die zwei Binärwörter W -1 und W 0 als Eingabe akzeptiert und W ∞ ausgibt, wobei die folgenden zusätzlichen Regeln eingehalten werden:
Sie können die Wörter in beliebiger Reihenfolge akzeptieren. als zwei Arrays, ein Array von Arrays, zwei Strings, ein Array von Strings oder ein einzelner String mit einem Begrenzer Ihrer Wahl.
Sie können die Ziffern des unendlichen Wortes entweder ohne Begrenzer oder mit einem konsistenten Begrenzer zwischen jedem Paar benachbarter Ziffern drucken.
Gehen Sie in jedem Fall davon aus, dass Ihrem Code niemals der Speicher ausgeht und die Datentypen nicht überlaufen.
Dies bedeutet insbesondere, dass alle Ausgaben an STDOUT oder STDERR, die das Ergebnis eines Absturzes sind, ignoriert werden.
Wenn ich Ihren Code auf meinem Computer (Intel i7-3770, 16 GiB RAM, Fedora 21) eine Minute lang laufen lasse und die Ausgabe an weiterleite,
wc -c
muss er mindestens eine Million Stellen W ∞ für (W -1 , W 0 ) ausgeben. = (1, 0) .Es gelten die Standardregeln für Code-Golf .
Beispiel
Sei W -1 = 1 und W 0 = 0 .
Dann ist W 1 = 01 , W 2 = 010 , W 3 = 01001 , W 4 = 01001010 … und W ∞ = 010010100100101001010… .
Dies ist das unendliche Fibonacci-Wort.
Testfälle
Alle Testfälle enthalten die ersten 1000 Stellen des unendlichen FTW.
Input: 1 0
Output: 0100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001
Input: 0 01
Output: 0100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001
Input: 11 000
Output: 0001100000011000110000001100000011000110000001100011000000110000001100011000000110000001100011000000110001100000011000000110001100000011000110000001100000011000110000001100000011000110000001100011000000110000001100011000000110000001100011000000110001100000011000000110001100000011000110000001100000011000110000001100000011000110000001100011000000110000001100011000000110001100000011000000110001100000011000000110001100000011000110000001100000011000110000001100000011000110000001100011000000110000001100011000000110001100000011000000110001100000011000000110001100000011000110000001100000011000110000001100000011000110000001100011000000110000001100011000000110001100000011000000110001100000011000000110001100000011000110000001100000011000110000001100011000000110000001100011000000110000001100011000000110001100000011000000110001100000011000000110001100000011000110000001100000011000110000001100011000000110000001100011000000110000001100011000000110001100000011000000110001100000011000110000001100000011
Input: 10 010
Output: 0101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010
Input: 101 110
Output: 1101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101
Antworten:
Pyth, 8 Bytes
Eingabe in das Formular
"W-1", "W0"
.Nachweis der Fertigstellung:
Beweis der Richtigkeit:
Hier ist die Serie als intern generiert. Es wird vom Programm in Verkettung gedruckt.
Vergleichen Sie mit den folgenden Angaben, die in Verkettung gedruckt werden. Dabei handelt es sich einfach um die Zeichenfolge, die bei jedem Schritt zur vorherigen Zeichenfolge hinzugefügt wird:
Wir wollen beweisen, dass diese gleichwertig sind.
Offensichtlich sind sie in den ersten Schritten gleich. Vergleichen wir sie nach einer Weile:
Wir sehen, dass die Saitenpaare abwechselnd folgende Formen haben:
Wobei a und b beliebige Folgen von 0en und 1en sind. Lassen Sie uns die Sequenz ein wenig fortsetzen, um zu beweisen, dass sie durch Induktion für immer fortgesetzt wird:
2 Schritte später hat es die richtige Form.
2 Schritte später hat es die richtige Form.
Durch Induktion stimmen die Zeichenfolgen immer überein, sobald sie verkettet sind.
quelle
W0
aber statt gedruckt zu werdenW1
, wird gedrucktW-1 || W0
, was die "falsche" Verkettungsreihenfolge ist. Ich denke, dass dies äquivalent ist, aber ich habe keinen Beweis gefunden ...Haskell, 15 Bytes
Die Infix-Funktion
%
erzeugt eine unendliche Zeichenkette, die Haskell für immer druckt, weil Haskell so cool ist.Die rekursive Idee ähnelt der Lösung von Zgarb . Das Schreiben
f
für die Funktion%
und+
für die Verkettung von Zeichenfolgen implementiert Folgendes:Die unendliche Ausgabezeichenfolge beginnt mit
w
und der Rest davon ist das Ergebnis für die Fibonacci-verschobenen Zeichenfolgenw
undv+w
.Dies hat kein Problem damit, in einer Minute eine Million Zeichen zu generieren.
quelle
Haskell, 31 Bytes
Dies definiert eine Infix-Funktion
#
, die zwei Zeichenfolgen akzeptiert und eine unendliche Zeichenfolge zurückgibt. Verwendung:Wenn ich das millionste Element der durch "1" und "0" definierten Sequenz abfrage, gibt selbst der Online-Interpreter das Ergebnis in weniger als einer Sekunde aus:
Erläuterung
Grundsätzlich wissen wir das
w#v == v#(v++w)
undw#v
beginnen mitv
diesen Fakten und definieren das Ergebnis. Da Haskell faul ist, funktioniert dies "magisch".quelle
Pip, 8 Bytes
Hey, mit Pyth gefesselt!
Einfache rekursive Definition aus der Haskell-Antwort von xnor . Mit Leerzeichen zur Verdeutlichung hinzugefügt:
Jedes Programm in Pip ist eine implizite Funktion, die die Befehlszeilenargumente als Argumente verwendet (den Variablen
a
durch zugewiesene
) und ihren Rückgabewert ausgibt.O
Ist ein Operator, der seinen Operanden ausgibt und dann zurückgibt. Das erste, was hier passiert, ist, dass das zweite Argument angezeigt wird (ohne Zeilenumbruch).Jetzt ist die von Lisp inspirierte Syntax
(f x y)
in Pip ein Funktionsaufruf, derf(x,y)
C-ähnlichen Sprachen entspricht. Dief
Variable bezieht sich auf die aktuelle Funktion - in diesem Fall das übergeordnete Programm. Das Programm ruft sich also rekursiv mitb
unda.b
als neuen Argumenten auf.Ich war angenehm überrascht, dass dieser Ansatz schnell genug ist:
Auf meinem Ubuntu-Computer dauert es ungefähr 30 Sekunden, bis das Programm die maximale Rekursionstiefe erreicht hat. Ab diesem Zeitpunkt wurden mehr als eine Milliarde Stellen gedruckt.
Diese iterative Lösung ist etwas schneller und beansprucht weniger Speicher auf Kosten eines Bytes:
quelle
CJam,
1211 BytesDies nimmt die beiden Wörter in getrennten Zeilen, in umgekehrter Reihenfolge, z
gibt
Erläuterung
Die Idee ist, das Wort naiv aufzubauen (indem wir uns an das aktuelle Wort erinnern und das vorherige anhängen). Dabei drucken wir alles, was wir gerade angehängt haben (um das bereits gedruckte Präfix nicht zu wiederholen). . Um zu vermeiden, dass der Startpunkt separat behandelt werden muss, beginnen wir mit einem leeren Wort, sodass W 0 das erste ist, das wir anhängen (und drucken).
quelle
PowerShell,
9776 BytesEdit - Ähm, schreiben,
$e.substring($b.length)
nachdem wir gerade verkettet$a
und$b
zusammen sind, ist gleichbedeutend mit schreiben, nur$a
... derp.Wow, wortreich. PowerShell gibt standardmäßig jedes Mal eine neue Zeile aus, wenn Sie etwas ausgeben. Wirklich die einzige Möglichkeit, das zu umgehen, ist mit
write-host -n
(kurz für-NoNewLine
), und das bringt hier absolut die Länge um.Im Wesentlichen durchläuft dies die Sequenz und bildet dabei
$e
das "aktuelle" W n . Da wir jedoch das unendliche Wort anstelle der Sequenz erstellen möchten, verwenden wir unsere vorherigen Variablen, um das Suffix auszudrucken, das$a
in unserer vorherigen Schleife ausgefüllt wurde. Dann richten wir unsere Variablen für den nächsten Durchgang ein und wiederholen die Schleife. Beachten Sie, dass dies erwartet, dass die Eingabe explizit als Zeichenfolgen abgegrenzt wird, ansonsten als+
Operator für die Arithmetik anstelle der Verkettung verwendet wird.Beispiel:
quelle
APL,
2418Die Verwendung von xnors Formulierung erlaubte es, nur wenige Zeichen zu entfernen .
Auf einer unendliche Maschine in unendlicher Zeit wäre es tatsächlich drucken W ∞ dreimal erste inkrementell während der Schleife ausgeführt wird , und dann zweimal als Ergebnis des gesamten Ausdrucks , wenn der
⍣≡
Fixpoint Operator schließlich zurückkehrt.Es ist nicht sehr schnell, aber schnell genug. In GNU APL:
quelle
⍣≡
. es klingt sehr nützlich.Pure Bash, 58
Ich habe vor 1 Minute keinen Speicher mehr, aber bis dahin habe ich viele Ziffern - nach 10 Sekunden habe ich 100 Millionen Ziffern:
quelle
Mathematica, 56 Bytes
quelle
C 76 (gcc)
Dies ist ein ziemlich einfacher rekursiver Drucker, der als verschachtelte Funktion implementiert ist (eine GNU C-Erweiterung, die von clang nicht unterstützt wird), um nicht herumreichen zu müssen
v
.p(n)
druckt W n-2 , wobei W -1 und W 0 inv[1]
und angegeben werden müssenv[2]
. Dies ruft zunächstp(4)
zum Drucken von W 2 auf . Dann wird eine Schleife ausgeführt: Es wird aufgerufenp(3)
, W 1 zu drucken , wodurch die vollständige Ausgabe W 2 W 1 erzeugt wird , die W 3 ist . Es wird dann aufgerufenp(4)
, W 2 zu drucken , wodurch die vollständige Ausgabe W erfolgt4 usw. Die Leistung ist etwas besser als bei meiner früheren Antwort: In einer Minute werden 1875034112 Werte angezeigt.C, 81 (erklingen)
Dies ist eine völlig andere Herangehensweise als die oben genannte, die meines Erachtens es wert ist, beibehalten zu werden, auch wenn sie schlechter abschneidet.
Dies hat alle Arten von undefiniertem Verhalten, hauptsächlich zum Spaß. Es funktioniert mit clang 3.6.2 unter Linux und mit clang 3.5.2 unter Cygwin für die in Frage kommenden Testfälle mit oder ohne spezielle Befehlszeilenoptionen. Es wird nicht unterbrochen, wenn Optimierungen aktiviert sind.
Es funktioniert nicht mit anderen Compilern.
Ich akzeptiere die Wörter als Befehlszeilenargumente im Zeichenfolgenformat.
Ich benutze newline als konsistenten Begrenzer.
Ich greife
s
außerhalb der Grenzen zu. Dies muss sicherlich irgendwann mit einem Segfault oder einer Zugriffsverletzung enden.s
wird zufällig am Ende des Datensegments platziert, sodass andere Variablen nicht überlastet werden und vor diesem Segfault eine falsche Ausgabe erfolgen sollte. Hoffnungsvoll.Beim Testen mit
{ ./program 1 0 | tr -d '\n' & sleep 60; kill $!; } | wc -c
erhalte ich in einer Minute 1816784896 Ziffern auf meinem Computer, als das Programm kompiliert wurde-O3
, und 1596678144, als es mit aktivierten Optimierungen kompiliert wurde.Ungolfed, kein UB, mit Begründung:
quelle
s[]
Trick funktioniert gut mit Clang (einfach installiert). Ich bin ziemlich überrascht, dass dies tatsächlich funktioniert. Gehen Sie in jedem Fall davon aus, dass Ihrem Code niemals der Speicher ausgeht und die Datentypen nicht überlaufen. Leider bedeutet dies, dass das einfache Drucken von W97 nicht als gültig angesehen wird. Könnten Siep
rekursiv anrufen ? Das würde die Notwendigkeit für a beseitigenmain
.p
in sichp
selbst umsetzen kann, ohne weiteren Code hinzuzufügen, aber wenn ich einen Weg finde, werde ich ihn erneut bearbeiten.Javascript (53 Bytes)
Die Eingabe sollte eine Zeichenfolge und keine Zahl sein (
'0'
und nicht nur0
).quelle
Perl 5,
455549 Bytes44 Bytes plus 1 für
-E
statt-e
Verwenden Sie als zB
Dadurch werden aufeinanderfolgende Näherungen an W ∞ ausgegeben, und wenn Sie lange genug warten, wird W ∞ in der letzten Ausgabezeile je nach Bedarf auf eine beliebige Länge gedruckt . Die Ziffern des Wortes werden ohne Trennzeichen verkettet.
Da ich unter Windows bin, testete ich es für die „mindestens eine Million Stellen von W ∞ “ Anforderung , indem sie es mit Ausgabe in eine Datei umgeleitet ausgeführt wird und es nach etwa 59 Sekunden zu töten, dann GnuWin32 läuft
wc -L
, die 701.408.733 gedruckt.Aktualisieren:
Das OP hat in einem Kommentar zu dieser Antwort klargestellt (und ich hätte es wahrscheinlich sowieso wissen müssen), dass die zusätzliche Ausgabe vor W ∞ das Obige disqualifiziert. Hier ist also stattdessen eine 55-Byte-Lösung, die nur W ∞ ausgibt :
Wird auf die gleiche Weise verwendet, jedoch mit den Argumenten in umgekehrter Reihenfolge . Erfordert nicht
-E
:Zweifellos kann man weiter Golf spielen, aber ich verstehe momentan nicht, wie das geht.
Weiteres Update:
Dennis hat fünf Bytes rasiert, indem er den am Ende des Befehls übergebenen Parameter verwendet
-a
(also gelesen<>
, um ihn zu entfernensub
) und neu zugewiesen hatprint
redo
Blocks übergebenen :Mit
-ane
und Lesen von<>
(beide Eingänge in einer Zeile, getrennt durch Leerzeichen, in umgekehrter Reihenfolge); 48 + 2 Bytes:Und basierend darauf habe ich ein weiteres Byte rasiert (wie oben, aber jetzt sind die Eingaben in der richtigen Reihenfolge); 47 + 2 Bytes:
quelle
REXX , 48
ftw.rex
exec ftw.rex 0 1
Derzeit kann die Leistung nicht getestet werden, da ich einen Online-Compiler zum Schreiben verwendet habe. Das "für immer" kann durch eine beliebige Zahl ersetzt werden, wobei die aufgedruckten ftw-Nummern (Nummer + 2) sind.
Ich habe auch eine kleine (chaotische) Lösung in Prolog geschrieben. Ich habe nicht herausgefunden, wie ich die Leistung mit diesem testen soll, aber es ist wahrscheinlich trotzdem schrecklich.
quelle
Python 2, 67 Bytes
Akzeptiert Eingaben als durch Kommas getrenntes Zeichenfolgenpaar:
"1","0"
für das Beispiel in der Frage.Kein Online-Interpreter, da Endlosschleifen schlecht sind.
Durch die gepufferte Ausgabe habe ich viele Bytes gewonnen. :(Danke Dennis für den Hinweis, dass 1 Ziffer pro Zeile gültig ist.Timing auf meinem (deutlich schwächeren) Rechner:
quelle
Dyalog APL, 9
Hiermit wird
∇
eine rekursive Funktion definiert. Dies ist eine direkte Übersetzung der Python 3-Antwort von xnor . Es nimmt W 0 als rechtes und W -1 als linkes Argument, beide sollten Zeichenvektoren sein.quelle
Minkolang 0,11 , 62 Bytes
Probieren Sie es hier aus. Erwartet Eingaben in der Reihenfolge W 0 , W -1 mit einem Leerzeichen dazwischen.
Erläuterung
Die Meta-Erklärung für das Folgende ist, dass wir zu diesem Zeitpunkt zwei Zahlen haben, gefolgt von einer Folge von "0" und "1" ohne Trennung. Wenn die Längen W 0 und W -1 sind
a
undb
jeweils dann die beiden Zahlen an der Vorderseite des Stapels sind<a+b>
und<a>
, in dieser Reihenfolge. Das Wort, das durch Verketten von W i + 1 und W i , dh W i + 1 + W i , gebildet wird, ist gleich 2 · W i + 1 - W i . Der folgende Code dupliziert also den Stapel (2 * W i + 1 ) und springt oben heraus<a>
Elemente (- Wi ) und ersetzt dann<a+b>
und<a>
mit ihren Nachfolgern<a+2b>
und<b>
.quelle
Python 3, 32
Dieselbe rekursive Idee wie meine Haskell-Antwort , außer dass das Präfix gedruckt wird, weil Python nicht mit unendlichen Zeichenfolgen umgehen kann.
Verwenden Sie einen Trick von Sp3000, um ohne Leerzeichen zu drucken, indem Sie den String als
end
Argument in Python 3 einfügenquelle
Perl, 32 Bytes
Wenn der Shebang als zwei gezählt wird, erfolgt die Eingabe aus stdin, wobei der Abstand als W 0 , W –1 angegeben wird . Ausgabe für 1 MB-Zeiten bei ~ 15 ms, die meisten davon sind auf den Start des Interpreters zurückzuführen.
Beispielnutzung
quelle
Prolog, 69 Bytes
Eingabebeispiel: p ('1', '0') Es wurde
keine Möglichkeit gefunden, das zusätzliche Schreiben zu entfernen.
Sollte in der Lage sein, dies zu verbessern, wenn ich herausfinde, wie das geht.
quelle