Tipps zum Golfen in Brainfuck

23

Welche allgemeinen Tipps haben Sie zum Golfen in Brainfuck? Ich bin auf der Suche nach Ideen, die sich generell auf Code-Golf-Probleme anwenden lassen, die zumindest etwas spezifisch für Brainfuck sind (z. B. "Kommentare entfernen" ist keine Antwort). Bitte posten Sie einen Tipp pro Antwort.

RAM
quelle

Antworten:

25

Ein Tipp pro Antwort wäre viel zu viele Antworten.

  • Lerne in Brainfuck zu denken. Es ist ganz anders als alles andere. Lesen und schreiben, umschreiben und viele Brainfuck-Programme umschreiben. Die Sprache gibt Ihnen nicht viel zu arbeiten, deshalb ist es wichtig, das, was sie Ihnen bietet, flexibel und effizient einzusetzen. Lass keine Abstraktionen zwischen dich und die Sprache geraten - steig ein und setze dich damit auseinander.

  • Machen Sie es sich mit der zerstörungsfreien Durchflussregelung sehr bequem. Um aus einer Entscheidungsschleife herauszukommen, anstatt die Startzelle auf Null zu setzen, indem sie an eine andere Stelle kopiert und nach Verlassen der Schleife wieder zurückkopiert wird, ist es oft besser, den Zeiger auf eine bereits vorhandene Null in der Nähe zu bewegen. Ja, dies bedeutet, dass sich der Zeiger an verschiedenen Stellen befindet, je nachdem, ob Sie die Schleife durchlaufen haben, aber dies bedeutet auch, dass diese Stellen wahrscheinlich unterschiedliche Anordnungen von Nullen und Nicht-Nullen in der Nähe haben, mit denen Sie die Zeigerposition mit einer anderen Schleife neu synchronisieren können. Diese Technik ist für eine gute Brainfuck-Programmierung von grundlegender Bedeutung, und verschiedene Formen davon werden sich ständig als nützlich erweisen.

  • Dies und die Tatsache, dass jede >oder jede <Kosten bedeuten, dass die Details des Speicherlayouts wichtig sind. Probieren Sie so viele Variationen Ihres Layouts aus, wie Sie Geduld haben. Denken Sie daran, dass Ihr Speicherlayout keine starre Zuordnung von Daten zu Standorten sein muss. Es kann sich im Laufe der Ausführung verändern.

  • Überlegen Sie in größerem Maßstab, und versuchen Sie sogar, eine Vielzahl verschiedener Algorithmen zu implementieren. Zunächst ist nicht klar, welcher Algorithmus der beste ist. Möglicherweise ist nicht einmal klar, welcher grundlegende Ansatz am besten ist, und es wird wahrscheinlich etwas anderes sein als der, der in einer normalen Sprache am besten ist.

  • Wenn Sie mit großen oder variablen Daten arbeiten, prüfen Sie, ob Sie möglicherweise lokal damit umgehen können, ohne zu wissen, wie groß die Daten sind oder an welcher Stelle sie sich befinden.

  • Dieselben Daten können zwei verschiedene Dinge sein. (Meistens eine Zahl oder ein Zeichen und auch eine Nicht-Null-Positionsmarkierung. Siehe jedoch random.b , wobei ein Bitzähler als Wert einer Zelle eines zellularen Automaten fungiert.)

  • Derselbe Code kann zwei verschiedene Dinge tun, und es ist viel einfacher, dies in einer Sprache zu tun, in der der Code so allgemein ist wie <+<. Achten Sie auf solche Möglichkeiten. Tatsächlich werden Sie gelegentlich bemerken, dass es auch in einem gut geschriebenen Programm kleine Teile gibt, die vollständig gelöscht werden können, nichts hinzugefügt wird, und dass die Sache zufällig immer noch fehlerfrei läuft.

  • In den meisten Sprachen verwenden Sie häufig einen Compiler oder Interpreter, um das Verhalten Ihres Programms zu überprüfen. Die Brainfuck-Sprache erfordert eine größere konzeptionelle Kontrolle. Wenn Sie einen Compiler benötigen, der Ihnen mitteilt, was Ihr Programm tut, haben Sie nicht genügend Ahnung von Ihrem Programm, und Sie müssen es wahrscheinlich genauer betrachten - zumindest, wenn Sie ein klares Bild von haben möchten der konzeptionelle Heiligenschein ähnlicher Programme soll gut im Golf sein. Mit der Zeit werden Sie ein Dutzend Versionen Ihres Programms erstellen, bevor Sie versuchen, eine auszuführen, und zu diesem Zeitpunkt sind Sie zu 95% sicher, dass Ihre kürzeste Version korrekt ausgeführt wird.

  • Viel Glück! Sehr wenige Leute haben die Mühe, Brainfuck kurz zu schreiben, aber ich denke, nur so kann die Sprache möglicherweise die fortgesetzte Aufmerksamkeit rechtfertigen - als erstaunlich obskure Kunstform.

Daniel Cristofani
quelle
3
Wenn ich das lese, möchte ich jetzt versuchen, in Brainfuck zu programmieren.
Claudiu
Heilige Scheiße, dachte ich hätte deinen Namen erkannt. Großer Fan Ihrer Brainfuck-Programme, insbesondere Ihres superkurzen Selbstinterpreten!
Jo King
"Sie werden gelegentlich bemerken ... dass es kleine Teile gibt, die komplett gelöscht werden können, nichts hinzugefügt wird und die Sache zufällig immer noch fehlerfrei läuft." Dies gilt insbesondere für Anfänger. Ich habe in BF immer nur eine Antwort geschrieben, soweit ich mich erinnern kann, aber der Versionsverlauf enthält mindestens 3 Fälle, in denen ich mit dem Programm gespielt habe und nach dem Zufallsprinzip "Hey, das Programm funktioniert immer noch, wenn ich dieses Bit entferne! "
ETHproductions
"Probieren Sie so viele Variationen Ihres Layouts aus, wie Sie
möchten
9

Ein paar Tipps hier:

Konstanten:

Auf der Konstantenseite von Esolangs finden Sie eine äußerst nützliche Liste der kürzesten Möglichkeiten, um bestimmte Werte zu erstellen. Ich sehe mich mindestens zweimal pro Programm auf dieser Seite.

Der Anfang von allem:

+++[[<+>>++<-]>]

Dadurch wird das Band im Format 3 * n ^ 2 erstellt, wie es aussieht

3 6 12 24 48 96 192 128 0 0 '

Warum ist das so wichtig?

Gehen wir die Liste durch:

  • 3 und 6 sind langweilig
  • 12: Fast 10 (Zeilenvorschub) oder 13 (Wagenrücklauf). Kann auch für den Zähler für 0-9 verwendet werden
  • 24: Fast 26, die Anzahl der Buchstaben im Alphabet
  • 48: ASCII für 0
  • 96: Nahe an 97, ASCII für a
  • 196 und 128: 196-128 = 64, nahe 65, der ASCII für A.

Von diesem einen Algorithmus sind wir am Anfang praktisch jeder Sequenz im ASCII-Bereich, zusammen mit einem Zähler für jede und einer leicht erreichbaren Newline.

Ein praktisches Beispiel:

Drucken aller Groß- und Kleinbuchstaben und Ziffern.

Mit Algorithmus:

+++[[<+>>++<-]>]<<[-<->]<<<<++[->>+.>+.<<<]<--[>>.+<<-]

Ohne:

+++++++++++++[->+++++++>++>+++++>++++>+<<<<<]>+++++>[-<+.>>.+<]>>---->---[-<.+>]

Wir verbringen die meisten Bytes damit, nur das Band im zweiten Beispiel zu initialisieren . Ein Teil davon wird durch die zusätzlichen Bewegungen im ersten Beispiel ausgeglichen, aber diese Methode hat eindeutig den Vorteil.

Ein paar andere interessante Algorithmen in der gleichen Richtung:

3 * 2 ^ n + 1:

+++[[<+>>++<-]+>]
Tape: 4 7 13 25 49 65 197 129 1 0'

Dies versetzt die Werte um 1, was einige Dinge bewirkt. Es macht die 12 zu einem Wagenrücklauf, die 64 zum eigentlichen Beginn des Großbuchstabens und die 24 näher an der 26.

2 ^ n:

+[[<+>>++<-]>]
Tape: 1 2 4 8 16 32 64 128

Da 64 für Großbuchstaben geeignet ist, ist 32 der ASCII-Wert für Leerzeichen und 128 kann als Zähler für 26 verwendet werden (130/5 = 26). In bestimmten Situationen, in denen Ziffern und Kleinbuchstaben nicht benötigt werden, können so Bytes gespart werden.

Wählen Sie die Implementierung, die zu der Frage passt:

  • Negative Zellen sind fast immer nützlich, und es gibt keinen Grund, sie zu vermeiden (es sei denn, dies ändert nichts an Ihrem Bytecount).
  • Fast dasselbe gilt für das Umschließen von Zellen, zumal viele Konstanten das Umschließen verwenden.
  • Beliebige Zellgrößen sind nützlich für unendliche mathematische Sequenzen, z. B. die Berechnung der Fibonacci-Sequenz unendlich ( +[[-<+>>+>+<<]>]) oder die Verarbeitung größerer / negativer Zahlen. Der Nachteil ist, dass einige der gebräuchlichsten Methoden, wie z. B. [-]und [->+<]nicht, angewendet werden können, nur für den Fall, dass die Zahl negativ ist.
  • EOF als 0, -1 oder keine Änderung. In der Regel ist 0 vorzuziehen, da Sie eine ganze Eingabe ohne zusätzliche Prüfungen durchlaufen können. -1 ist nützlich, wenn Sie eine Schleife über Array-Strukturen ausführen. Ich habe noch keine Verwendung für keine Änderung gefunden :(.

Behalte den Überblick, was mit dem Frick los ist:

Zu jeder Zeit sollten Sie Kommentare dazu haben, wo sich der Zeiger in Bezug auf die umliegenden Daten befinden soll, und sicherstellen, dass Sie den Bereich der möglichen Werte jeder Zelle kennen. Dies ist besonders wichtig, wenn Sie den Zeiger vor einer Schleife geteilt haben, da Sie die beiden Möglichkeiten anschließend wieder zusammenfügen möchten.

Zu jedem Zeitpunkt ist mein Code mit Kommentaren in jeder anderen Zeile übersät, die so aussehen:

*0 *dat a_1 ?  0' !0 0*
 or
*0 *dat 0' ap1 0  !0 0*

Ein zusätzlicher Rat ist, den Symbolen besondere Bedeutungen zuzuweisen. In dem obigen Beispiel bedeutet 'der Zeiger *Wiederholung in dieser Richtung, ?bedeutet eine Zelle mit unbekanntem Wert, !0bedeutet eine Zelle ungleich Null, _ist ein Ersatz für -und pist ein Ersatz für +. orimpliziert, dass das Band wie eine der Darstellungen aussehen kann und als solche behandelt werden muss.

Ihr Symbolschema muss nicht unbedingt dasselbe sein wie meins (mit einigen Fehlern), es muss nur konsistent sein. Dies ist auch beim Debuggen äußerst nützlich, da Sie es bis zu diesem Punkt ausführen und das tatsächliche Band mit dem vergleichen können, was Sie haben sollten , was auf potenzielle Fehler in Ihrem Code hinweisen kann.

Scherzen
quelle
5

Mein wichtigster Ratschlag wäre, nicht zu tun.

OK, gut, du willst etwas Nützlicheres als das. BF ist bereits eine sehr knappe Sprache, aber was Sie wirklich umbringt, ist Arithmetik, was effektiv in unary getan werden muss. Es lohnt sich, die Seite mit den Konstanten in Esolang zu lesen, um herauszufinden, wie große Zahlen effizient geschrieben werden können, und den Zeilenumbruch zu nutzen, wo immer dies möglich ist.

Speicherzugriff ist auch sehr teuer. Da Sie von einer Kassette lesen, müssen Sie berücksichtigen, wo sich Ihr Kopf zu einem bestimmten Zeitpunkt bewegt. Im Gegensatz zu anderen Sprachen, in denen Sie nur schreiben akönnen b, cmüssen Sie in bf den Kopf explizit um eine bestimmte Anzahl von Bytes nach links oder rechts bewegen, damit Sie wissen, wo Sie was speichern. Ich bin mir ziemlich sicher, dass es sehr schwer ist, Ihr Gedächtnis optimal zu organisieren, also viel Glück damit.

ymbirtt
quelle
5

In dieser Antwort beziehe ich mich mehrmals auf eine bestimmte Zelle auf dem Band. Es spielt keine Rolle, um welche Zelle es sich handelt, aber es ist in der gesamten Antwort dieselbe Zelle. Für die Zwecke dieses Beitrags werde ich diese Zelle "Todd" nennen.

Wenn Sie versuchen, eine Zelle auf einen konstanten Wert zu setzen, lohnt es sich manchmal, sie nicht sofort zu beenden. Angenommen, Sie möchten, dass Todd 30 enthält. Später in Ihrem Code (der möglicherweise den Wert von Todd ändert, ihn aber nie liest) kehren Sie zu Todd zurück. Wenn Todd den Wert 0 hat, wird das Programm beendet. Andernfalls wird der Wert von Todd für immer gedruckt.

Laut der esolangs.org-Seite mit Brainfuck-Konstanten (die wahrscheinlich selbst Gegenstand eines Trinkgeldes sein könnten!) Ist der kürzeste Weg, um 30 zu bekommen >+[--[<]>>+<-]>+. Dieser Hinweis >dient nur dazu, sicherzustellen, dass nichts links vom Zeiger geändert wird. In diesem Fall gehen wir jedoch davon aus, dass uns das egal ist, und lassen ihn fallen. Mit diesem Code würde Ihr Code ungefähr so ​​aussehen:

+[--[<]>>+<-]>+(MISC. CODE)(GO TO TODD)[.]

Sie können sich das erste Stück Code so vorstellen:

(SET TODD TO 30)(MISC. CODE)(GO TO TODD)[.]

Aber denken Sie daran , die letzten zwei Zeichen in diesem Brocken: >+. Es ist genauso gültig, es so zu sehen:

(SET TODD TO 29)(GO TO TODD)(ADD 1 TO TODD)(MISC. CODE)(GO TO TODD)[.]

Beachten Sie, dass Sie (GO TO TODD)zweimal! Sie könnten stattdessen Ihren Code folgendermaßen schreiben:

(SET TODD TO 29)(MISC. CODE)(GO TO TODD)(ADD 1 TO TODD)[.]
+[--[<]>>+<-](MISC. CODE)(GO TO TODD)+[.]

Unter der Annahme, dass die Anzahl der benötigten Bytes (GO TO TODD)gleich ist, bedeutet ein Zug weniger == ein Byte weniger! Manchmal nimmt die Tatsache, dass sich Ihre Ausgangsposition geändert hat, diesen Vorteil weg, aber nicht immer.

untergrundbahn
quelle
0

Ein kleiner Tipp für Herausforderungen ohne Input. Sie können ,anstelle von verwenden [-], wenn Sie die Zelle schnell löschen müssen, da die meisten Interpreter (einschließlich der TIO.run-1) den Zelleninhalt auf die EOF-Darstellung Null setzen. Das macht Programme ein bisschen unportabel, aber wen interessiert das überhaupt im Codegolf?

Krzysztof Szewczyk
quelle