Schreiben Sie ein Brainfuck-Programm mit maximal 256 Zeichen, das so viele Schritte wie möglich ausführt, aber keine Endlosschleife ausführt. Das Programm darf keine Eingaben machen.
Genauer:
- Nehmen Sie eine unendliche Anzahl von Zellen rechts an.
- Eine
<Zelle ganz links tut nichts. - A,
-wenn der Zellenwert Null ist, setzt die Zelle auf255. +-<>.Alle Anweisungen zählen bei der Ausführung als ein Schritt.- Wenn ein
[oder]angetroffen wird, zählt es als ein Schritt. Wenn jedoch die Bedingung wahr ist und Steuerfluß springt, die entsprechende]oder[sich nicht wieder als Schritt zählen. - Die Lösung mit den meisten Schritten gewinnt.
- Wenn Ihre Lösung eine Art Muster enthält, ist die Angabe einer Funktion für die Anzahl der Schritte, die ein ähnliches Längenprogramm ausführen
nwürde, erwünscht, jedoch nicht zwingend. - Um Anweisungen zu zählen, können Sie diesen modifizierten Interpreter verwenden :
Beispiel:
++[-]
Die gefundenen Anweisungen lauten ++[-]-]und das Programm wurde in 7 Schritten ausgeführt.
code-challenge
brainfuck
busy-beaver
Anton Golov
quelle
quelle
floatoderdoubleprimitiven Elemente, die für die allgemeine alltägliche Datenverarbeitung verwendet werden. (Zu diesem Zeitpunkt manipuliert der Computer meist nur Zeichenfolgen, die die Gleichung darstellen.)Antworten:
Hier ist ein Programm mit 41 Zeichen, das schließlich anhält und mehr als 10 ↑ (10 ↑ 28) zusammenhängende Zellen auf 1 setzt (die Anzahl der ausgeführten Anweisungen ist also sehr viel größer als diese):
Wenn ich mich nicht irre, ist das eine korrekte Übersetzung des folgenden Programms in die BF-Variantensprache, die ein einzelnes Bit für jede Speicherzelle verwendet (dh Zelleninhalt 0..1 statt 0..255, also '+' Dient dazu, den Bitwert einfach umzudrehen.
Der genaue Wert (die Anzahl der benachbarten 1-Bits), die von dem letzteren Programm erzeugt werden, ist
Das obige Programm initialisiert und berechnet eine Funktion, die wie folgt wächst: 2 ↑↑ x (in Knuth-Aufwärtspfeilnotation ). Eine ähnliche Konvertierung eines Varianten-BF-Programms, das eine Funktion initialisiert und berechnet, die wie 2 ↑ 23 x wächst, bietet das folgende 256-Zeichen-Programm:
Das hält schließlich an und lässt mehr als 2 ↑ 23 6 benachbarte Zellen gleich 1 (die Anzahl der Schritte ist also enorm höher).
NB-1 : 2 ↑ 23 6 ist eine "unvorstellbar große" Zahl; ZB übertrifft bereits 2 ↑ 4 6 = 2 ↑↑↑↑ 6 den ersten Term (3 ↑↑↑↑ 3) in der Sequenz, die zur Berechnung von Grahams Zahl verwendet wird .
NB-2 : Ich denke, es ist wahrscheinlich, dass 256 Zeichen für ein BF-Programm ausreichen, um eine Funktion zu initialisieren und zu berechnen, deren Ausgabe viel größer als Grahams Zahl ist. Wenn ich Zeit finde, werde ich vielleicht versuchen, eine zu schreiben.
NB-3 : Falls sich jemand für die Herkunft der oben genannten Programme interessiert, finden Sie hier einige Programmierressourcen für "Brainf * ck F" mit verschiedenen in Python geschriebenen Programmen. ("Brainf * ck F", oder einfach "F", nannte ich eine Turing-vollständige Variante der Smallf * ck- Sprache.) Ich habe gerade diese Dateien hochgeladen, die seit mehreren Jahren offline sind, und jetzt die Die verlinkte Webseite ist nur ein "Archiv" - in der Datei Busy_Beavers.txt finden Sie eine ausführliche Beschreibung der oben genannten Programme.
quelle
Hier ist eine schöne 39 Zeichen:
Es macht im Grunde genommen einen 3 Felder breiten "Schlitten", der sich nach rechts bewegt und um eins dekrementiert. Abgeschlossen in 31.919.535.558 Anweisungen, wobei die innerste Schleife 256 ^ 3-mal ausgeführt wird. Ich habe immer noch viel Platz, um dies mit einer Geschwindigkeit von 14 Zeichen auf eine andere Größenordnung zur Laufzeit zu erweitern.
Funktioniert auf jedem Interpreter mit unbegrenztem Speicher oder mit Wrapping Memory.
Ich überlasse es dem Leser, zu bestimmen, wann die um 2 Schleifen verbesserte Version fertig sein wird:
Es ist jetzt über Nacht gelaufen und hat mehr als 3.000.000.000 Schritte. Immer noch nicht durch eine einzige Iteration der äußeren Schleife gekommen. Hat es kaum über 15% der zweiten Schleife geschafft.
quelle
Dieses Programm arbeitet in unendlich vielen Zellen. Am Anfang werden zwei Werte mit ASCII-Werten 255 initialisiert. Der erste Wert bei der ersten Drehung der Hauptschleife wird auf 255 Zellen aufgeteilt und sie werden mit jeweils 255 initialisiert, bei der zweiten Drehung der Hauptschleife wird jeder Wert in 255 Zellen erneut aufgeteilt Bis zu 255 * 255 Zellen. In der gleichen Weise werden für die Drehung der Hauptschleife 255 Zellen mit insgesamt 255 ^ 255 initialisiert. Der zweite Wert bestimmt, wie oft die Hauptschleife wiederholt werden soll.
quelle
Dieses Programm ist fast identisch mit meinem vorherigen Programm. Der Unterschied besteht darin, dass der Wert, der die äußere Schleife bestimmt, in einer bestimmten Zelle festgelegt bleibt, sodass sowohl die Anzahl der initialisierten Zellen als auch die Gesamtanzahl der Schritte am Ende des Programms erhöht werden können
Zellen initialisiert am Ende des Programms 255 ^ 255
Zellen, die am Ende des Programms initialisiert wurden 255 ^ 255 ^ 3
Ich habe es weiter modifiziert, um noch mehr Schritte ausführen zu können.
Es initialisiert 255 ^ 255 Zellen während der ersten Drehung der Hauptschleife 255 ^ (255 ^ 255 * 255) Zellen während der zweiten Drehung der Hauptschleife 255 ^ {255 ^ (255 ^ 255 * 255) * 255} Zellen während der dritten Drehung der Hauptschleife in Auf diese Weise wird die Schleife 255 Mal wiederholt
quelle