Eine unendliche FTW

25

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 -cmuss er mindestens eine Million Stellen W für (W -1 , W 0 ) ausgeben. = (1, 0) .

  • Es gelten die Standardregeln für .

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
Dennis
quelle
10
Fibonacci-artige Wörter FTW!
Seadrus

Antworten:

14

Pyth, 8 Bytes

u,peGsGQ

Eingabe in das Formular "W-1", "W0".

Nachweis der Fertigstellung:

$ time pyth -cd 'u,peGsGQ' <<< '"1", "0"' 2>/dev/null | head -c1000000 > /dev/null

real    0m0.177s
user    0m0.140s
sys 0m0.038s

Beweis der Richtigkeit:

Hier ist die Serie als intern generiert. Es wird vom Programm in Verkettung gedruckt.

[0, 10, 010, 10010, 01010010, 1001001010010,...]

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:

[0, 1, 0, 01, 010, 01001, 01001010, 0100101001001, ...]

Wir wollen beweisen, dass diese gleichwertig sind.

Offensichtlich sind sie in den ersten Schritten gleich. Vergleichen wir sie nach einer Weile:

010
  010

10010
  01001

01010010
  01001010

1001001010010
  0100101001001

Wir sehen, dass die Saitenpaare abwechselnd folgende Formen haben:

01a 10b
a10 b01

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:

01a   10b   10b01a   10b01a10b
  a10   b01   a10b01   b01a10b01

2 Schritte später hat es die richtige Form.

10b   01a   01a10b   01a10b01a
  b01   a10   b01a10   a10b01a10

2 Schritte später hat es die richtige Form.

Durch Induktion stimmen die Zeichenfolgen immer überein, sobald sie verkettet sind.

isaacg
quelle
14
+1 für das Schreiben von Arbeitscode, den Sie nicht verstehen.
Celeo
2
Ich glaube, Ihre 8-Byte-Lösung funktioniert, weil sie ab druckt, W0aber statt gedruckt zu werden W1, wird gedruckt W-1 || W0, was die "falsche" Verkettungsreihenfolge ist. Ich denke, dass dies äquivalent ist, aber ich habe keinen Beweis gefunden ...
FryAmTheEggman
16

Haskell, 15 Bytes

v%w=w++w%(v++w)

Die Infix-Funktion %erzeugt eine unendliche Zeichenkette, die Haskell für immer druckt, weil Haskell so cool ist.

>> "1"%"0"
"010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101

Die rekursive Idee ähnelt der Lösung von Zgarb . Das Schreiben ffür die Funktion %und +für die Verkettung von Zeichenfolgen implementiert Folgendes:

f(v,w) = w + f(w,v+w)

Die unendliche Ausgabezeichenfolge beginnt mit wund der Rest davon ist das Ergebnis für die Fibonacci-verschobenen Zeichenfolgen wund v+w.

Dies hat kein Problem damit, in einer Minute eine Million Zeichen zu generieren.

xnor
quelle
9

Haskell, 31 Bytes

w#v=v++drop(length v)(v#(v++w))

Dies definiert eine Infix-Funktion #, die zwei Zeichenfolgen akzeptiert und eine unendliche Zeichenfolge zurückgibt. Verwendung:

> let w#v=v++drop(length v)(v#(v++w)) in "11"#"000"
"000110000001100011000000110000...

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:

> let w#v=v++drop(length v)(v#(v++w)) in ("1"#"0") !! 1000000
'0'

Erläuterung

w#v=                             -- The result of w#v is
    v++                          -- v concatenated to
                      v#(v++w)   -- the infinite word v#(v++w),
       drop(length v)            -- with the first v characters dropped.

Grundsätzlich wissen wir das w#v == v#(v++w)und w#vbeginnen mit vdiesen Fakten und definieren das Ergebnis. Da Haskell faul ist, funktioniert dies "magisch".

Zgarb
quelle
5

Pip, 8 Bytes

Hey, mit Pyth gefesselt!

(fOba.b)

Einfache rekursive Definition aus der Haskell-Antwort von xnor . Mit Leerzeichen zur Verdeutlichung hinzugefügt:

(f Ob a.b)

Jedes Programm in Pip ist eine implizite Funktion, die die Befehlszeilenargumente als Argumente verwendet (den Variablen adurch zugewiesen e) und ihren Rückgabewert ausgibt. OIst 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, der f(x,y)C-ähnlichen Sprachen entspricht. Die fVariable bezieht sich auf die aktuelle Funktion - in diesem Fall das übergeordnete Programm. Das Programm ruft sich also rekursiv mit bund a.bals neuen Argumenten auf.

Ich war angenehm überrascht, dass dieser Ansatz schnell genug ist:

dlosc@dlosc:~$ time pip -e '(fOba.b)' 1 0 2>/dev/null | head -c1000000 > /dev/null

real    0m0.217s
user    0m0.189s
sys     0m0.028s

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:

W1Sba.:Ob
DLosc
quelle
4

CJam, 12 11 Bytes

llL{@_o+_}h

Dies nimmt die beiden Wörter in getrennten Zeilen, in umgekehrter Reihenfolge, z

0
1

gibt

0100101001001010010100100101001...

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).

ll    e# Read the two lines separately.
L     e# Push an empty string.
{     e# Infinite loop...
  @   e#   Pull up the previous FTW.
  _o  e#   Print it.
  +_  e#   Append it to the current FTW and duplicate it.
}h
Martin Ender
quelle
3

PowerShell, 97 76 Bytes

param($a,$b)write-host -n $b;while(1){write-host -n $a;$e=$b+$a;$a=$b;$b=$e}

Edit - Ähm, schreiben, $e.substring($b.length)nachdem wir gerade verkettet $aund $bzusammen 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 $edas "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 $ain 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:

PS C:\Tools\Scripts\golfing> .\infinite-ftw.ps1 "111" "000"
0001110000001110001110000001110000001110001110000001110001110000001110000001110001110000001110000001110001110000001110001110000001110000001110001110000001110001110000001110000001110001110000001110000001110001110000001110001110000001110000001110001110000001110000 ...
AdmBorkBork
quelle
3

APL, 24 18

{(,/⌽⍵),⊂⍞←↑⍵}⍣≡⍞⍞

Die Verwendung von xnors Formulierung erlaubte es, nur wenige Zeichen zu entfernen .

                 ⍞  ⍝ Read W₋₁ as a character string.
                ⍞   ⍝ Read W₀.
{            }⍣≡    ⍝ Apply the following function repeatedly until fixpoint:
                    ⍝ It takes a pair of strings (A B),
         ⍞←↑⍵       ⍝ prints A
 (,/⌽⍵),⊂  ↑⍵       ⍝ and returns (BA A).

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:

$ printf '%s\n' '{(,/⌽⍵),⊂⍞←↑⍵}⍣≡⍞⍞' 1 0 | apl -s | head -c 100
0100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010$
$ time printf '%s\n' '{(,/⌽⍵),⊂⍞←↑⍵}⍣≡⍞⍞' 1 0 | apl -s | head -c 1000000 >/dev/null
    0m3.37s real     0m2.29s user     0m1.98s system
user46915
quelle
Zwei unendliche Zahlen. OO +1
Addison Crump
Ich wusste es nicht ⍣≡. es klingt sehr nützlich.
Lirtosiast
3

Pure Bash, 58

a=$1
b=$2
printf $b
for((;;)){
printf $a
t=$b
b+=$a
a=$t
}

Ich habe vor 1 Minute keinen Speicher mehr, aber bis dahin habe ich viele Ziffern - nach 10 Sekunden habe ich 100 Millionen Ziffern:

$ ./ftw.sh 1 0 | head -c100
0100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010ubuntu@ubuntu:~$ 
$ { ./ftw.sh 1 0 & sleep 10 ; kill $! ; } | wc -c
102334155
$ 
Digitales Trauma
quelle
2

Mathematica, 56 Bytes

$IterationLimit=∞;#0[$Output~WriteString~#2;#2,#<>#2]&
LegionMammal978
quelle
2

C 76 (gcc)

main(c,v)char**v;{int p(n){n>2?p(n-1),p(n-2):puts(v[n]);}for(p(4);;p(c++));}

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 in v[1]und angegeben werden müssen v[2]. Dies ruft zunächst p(4)zum Drucken von W 2 auf . Dann wird eine Schleife ausgeführt: Es wird aufgerufen p(3), W 1 zu drucken , wodurch die vollständige Ausgabe W 2 W 1 erzeugt wird , die W 3 ist . Es wird dann aufgerufen p(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.

s[],*p=s;main(c,v)char**v;{for(++v;;)for(puts(v[*++p=*++p!=1]);*p+1==*--p;++*p);}

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.

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.

Ich akzeptiere die Wörter als Befehlszeilenargumente im Zeichenfolgenformat.

Sie können die Ziffern des unendlichen Wortes entweder ohne Begrenzer oder mit einem konsistenten Begrenzer zwischen jedem Paar benachbarter Ziffern drucken.

Ich benutze newline als konsistenten Begrenzer.

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.

Ich greife saußerhalb der Grenzen zu. Dies muss sicherlich irgendwann mit einem Segfault oder einer Zugriffsverletzung enden.swird zufällig am Ende des Datensegments platziert, sodass andere Variablen nicht überlastet werden und vor diesem Segfault eine falsche Ausgabe erfolgen sollte. Hoffnungsvoll.

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 -cmuss er mindestens eine Million Stellen W für (W -1 , W 0 ) ausgeben. = (1, 0) .

Beim Testen mit { ./program 1 0 | tr -d '\n' & sleep 60; kill $!; } | wc -cerhalte 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:

#include <stdio.h>

// Instead of starting with -1 and 0, start with 0 and 1. I will use lowercase w for that,
// so that wx = W(x-1).

// Declare a variable length array of numbers indicating what has been printed.
// The length is indicated through a pointer just past the end of the values.
// The first element of the array is a special marker.
// [0 3 1] means that w3 w1 has been printed.
// The array is initialised to [0] meaning nothing has been printed yet.
int stack[99999];
int *ptr = stack + 1;

int main(int argc, char *argv[]) {
  ++argv; // Let argv[0] and argv[1] refer to w0 and w1.
  for(;;) {
    // Determine the word to print next, either 0 or 1.
    // If we just printed 1 that wasn't the end of a different word, we need to print 0 now.
    // Otherwise, we need to print 1.
    int word = ptr[-1] != 1;

    // Print the word, and mark the word as printed.
    puts(argv[word]);
    *ptr++ = word;

    // If we just printed w(x) w(x-1) for any x, we've printed w(x+1).
    while (ptr[-1] + 1 == ptr[-2]) {
      --ptr;
      ++ptr[-1];
    }
  }
}
hvd
quelle
Dein böser 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 Sie prekursiv anrufen ? Das würde die Notwendigkeit für a beseitigen main.
Dennis
@Dennis Um fair zu sein, würde die Version, die durch Drucken von W97 betrügt, beim Drucken von W∞ für> 3000 Jahre das Richtige tun. Ich werde sehen, ob ich das verbessern kann. :)
HDV
@Dennis Ich habe es geschafft, es mit der gleichen Anzahl von Bytes für das Programm zum Laufen zu bringen, aber es für GCC spezifisch zu machen und keine saubere Funktion mehr zu haben. Ich verstehe nicht, wie ich die Logik des wiederholten Aufrufs pin sich pselbst umsetzen kann, ohne weiteren Code hinzuzufügen, aber wenn ich einen Weg finde, werde ich ihn erneut bearbeiten.
HDV
1

Javascript (53 Bytes)

(a,c)=>{for(;;process.stdout.write(a))b=a,a=c,c=b+a;}

Die Eingabe sollte eine Zeichenfolge und keine Zahl sein ( '0'und nicht nur 0).

Naouak
quelle
2
Willkommen bei Programming Puzzles & Code Golf! Unsere Regeln für Code-Golf-Herausforderungen besagen, dass Einsendungen standardmäßig vollständige Programme oder Funktionen sein müssen. Als solche müssen sie eine Art Benutzereingabe akzeptieren; Eine Hardcodierung der Eingabe ist nicht zulässig. Darüber hinaus druckt Ihr Code die Sequenz Wn , nicht die Grenze.
Dennis
1

Perl 5, 45 55 49 Bytes

44 Bytes plus 1 für -Estatt-e

sub{$i=1;{say$_[++$i]=$_[$i].$_[$i-1];redo}}

Verwenden Sie als zB

perl -E'sub{$i=1;{say$_[++$i]=$_[$i].$_[$i-1];redo}}->(1,0)'

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 :

sub{print$_[0];{print$_[1];unshift@_,$_[0].$_[1];redo}}

Wird auf die gleiche Weise verwendet, jedoch mit den Argumenten in umgekehrter Reihenfolge . Erfordert nicht -E:

perl -e'sub{print$_[0];{print$_[1];unshift@_,$_[0].$_[1];redo}}->(0,1)'

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 entfernen sub) und neu zugewiesen hatprintredo Blocks übergebenen :

Mit -aneund Lesen von <>(beide Eingänge in einer Zeile, getrennt durch Leerzeichen, in umgekehrter Reihenfolge); 48 + 2 Bytes:

$_=$F[0];{print;unshift@F,$F[0].($_=$F[1]);redo}

Und basierend darauf habe ich ein weiteres Byte rasiert (wie oben, aber jetzt sind die Eingaben in der richtigen Reihenfolge); 47 + 2 Bytes:

$_=$F[1];{print;push@F,$F[-1].($_=$F[-2]);redo}
msh210
quelle
1

REXX , 48

arg a b
do forever
b=a||b
say b
a=b||a
say a
end

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.

f(A,B,C):-atom_concat(B,A,D),(C=D;f(B,D,C)).

:- C='0';C='1';(f(1,0,C)).
Menplant
quelle
1

Python 2, 67 Bytes

a,b=input()
print'\n'.join(b+a)
while 1:a,b=b,b+a;print'\n'.join(a)

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:

$ time python golf.py <<< '"1","0"' 2>/dev/null | head -c2000000 > /dev/null

real    0m1.348s
user    0m0.031s
sys     0m0.108s
Mego
quelle
1
Die Frage erlaubt ein konsistentes Trennzeichen zwischen den Ziffern. Sie können mindestens 28 Byte speichern, indem Sie jede Ziffer in einer separaten Zeile ausgeben.
Dennis
1

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.

user46915
quelle
1

Minkolang 0,11 , 62 Bytes

(od" "=,6&xI0G2@dO$I)I1-0G($d2[I2:g]Xx0c2*1c-0g0g-d[icO]0G0G1)

Probieren Sie es hier aus. Erwartet Eingaben in der Reihenfolge W 0 , W -1 mit einem Leerzeichen dazwischen.

Erläuterung

(                             Open while loop (for input-reading)
 od                           Read in character from input and duplicate
   " "=,                      0 if equal to " ", 1 otherwise
        6&                    Jump 6 characters if this is non-zero
          xI0G2@              Dump, push length of stack, move to front, and jump next two
                dO            Duplicate and output as character if 1
                  $I)         Close while loop when input is empty
                     I1-0G    Push length of stack - 1 and move it to the front

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 aund bjeweils 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>.

(                                       Open while loop (for calculation and output)
 $d                                     Duplicate the whole stack
   2[I2:g]                              Pull <a+b> and <a> from the middle of the stack
          Xx                            Dump the top <a> elements (and <a+b>)
            0c2*1c-                     Get <a+b> and <a>, then calculate
                                        2*<a+b> - <a> = <a+2b> = <a+b> + <b>
                   0g0g-                Get <a+b> and <a>, then subtract
                        d[icO]          Output as character the first <b> elements
                              0G0G      Move both to front
                                  1)    Infinite loop (basically, "while 1:")
El'endia Starman
quelle
(Anmerkung: Das ergibt nicht 1 Million Ziffern in einer Minute ... nur 0,5 Millionen. Da dies natürlich eine relativ langsame Sprache ist, kann ich ein wenig
nachlassen
1

Python 3, 32

def f(a,b):print(end=b);f(b,a+b)

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 endArgument in Python 3 einfügen

xnor
quelle
1

Perl, 32 Bytes

#!perl -pa
$#F=3}for(@F){push@F,$F[-1].$_

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

$ echo 0 1 | perl inf-ftw.pl
0100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001...

$ echo 110 101 | perl inf-ftw.pl
1101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101...
primo
quelle
1

Prolog, 69 Bytes

q(A,B):-atom_concat(B,A,S),write(A),q(B,S).
p(A,B):-write(B),q(A,B).

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.

Emigna
quelle