Brain-Flak ist eine Stack-basierte Turing-Tarpit-Sprache, die ich zusammen mit DJMcMayhem und 1000000000 geschrieben habe .

Einige Benutzer sind sehr erfahren in den mysteriösen Wegen von Brain-Flak. Daher hielt ich es für eine gute Idee, diese Frage so einzurichten, dass wir und hoffentlich auch andere unser Wissen an die Community weitergeben und die Zugangsbeschränkung für diese Sprache senken können, die „schmerzhaft anzuwenden ist“. Und vielleicht sogar diejenigen von uns mit mehr Erfahrung einige neue Tricks beibringen.

Also, welche Tipps haben Sie für das Golfen in Brain-Flak? Ich bin auf der Suche nach Ideen, die sich auf Code-Golf-Probleme im Allgemeinen anwenden lassen, die zumindest etwas spezifisch für Brain Flak sind (z. B. "Kommentare entfernen" ist keine Antwort).

Bitte posten Sie einen Tipp pro Antwort.

Verwenden Sie den dritten Stapel

Wenn Sie den Titel gelesen haben, sind Sie möglicherweise etwas verwirrt. Sicher gibt es in Brain-Flak nur zwei Stapel? Ich versichere Ihnen jedoch, dass es existiert und eines der mächtigsten, wenn nicht das mächtigste Werkzeug beim Schreiben und Golfen von Brain-Flak ist.

Was ist der "Dritte Stapel"?

Jedes Brain-Flak-Programm verwendet den dritten Stapel auf die eine oder andere Weise, aber der Großteil der Verwendung geschieht hinter den Kulissen, und es ist oft nützlich, die Tatsache, dass er existiert, einfach zu ignorieren. Jede Klammer im Programm fügt entweder ein Element zum Stapel hinzu oder entfernt es. Drei der offenen Klammern ([<fügen alle einen Gegenstand zum Stapel hinzu, während ihre drei Konjugate )]>alle einen Gegenstand vom Stapel entfernen. Der Wert des Elements auf dem Stapel entspricht dem Wert des aktuellen Programmumfangs, und die Verwendung von Nullen ändert diesen Wert auf bestimmte Weise. Die enge Klammer )hat die einzigartige Funktion, ein Element vom dritten Stapel in den aktuellen Stapel zu verschieben. ein Stoß.

Hoffentlich wird dir das klar. Der dritte Stapel ist eine Art Stapel, der sich die Rückgabewerte des bereits ausgeführten Codes merkt. Lassen Sie uns ein Beispiel eines einfachen Programms durchgehen, das die beiden normalen Stapel und den dritten Stapel verfolgt.

Beispiel

Wir werden das folgende Programm durchgehen. Dieses Programm schiebt -3, 1, -2auf den Stapel.

(([()()()])(()))

Wir beginnen mit drei offenen Klammern, die alle eine Null auf den dritten Stapel schieben.

Unsere Stapel sehen jetzt so aus, der dritte Stapel ist der rechts und der aktive Stapel hat einen ^darunter:

        0
        0
  0  0  0
  ^

(([()()()])(()))
   ^

Jetzt haben wir drei ()Niladen. Diese machen nichts mit den normalen zwei Stapeln, aber sie addieren jeweils einen oben auf dem dritten Stapel, so dass unsere Stapel wie folgt aussehen:

        3
        0
  0  0  0
  ^

(([()()()])(()))
         ^

Jetzt stellen wir ]fest, dass in geschweiften Klammern ein Element aus dem dritten Stapel entfernt wird. Es ]hat jedoch die Funktion, das entfernte Element vom oberen Rand des Stapels zu subtrahieren. So sehen unsere neuen Stacks aus:

       -3
  0  0  0
  ^

(([()()()])(()))
          ^

Das macht Sinn; [...]tut die Verneinung so ]sollte nach unten subtrahieren.

Jetzt müssen wir eine ausführen ). Wie Sie sich wahrscheinlich erinnern, )ist dies die Stelle im Programm, an der die Daten auf den Stapel verschoben werden, sodass wir den oberen Teil des dritten Stapels auf den aktuellen Stapel verschieben. Außerdem werden wir -3das Element zum nächsten Element im dritten Stapel hinzufügen .

 -3  0 -3
  ^

(([()()()])(()))
           ^

Wieder treffen wir auf eine unserer drei offenen Klammern, damit wir unserem dritten Stapel ein weiteres Element hinzufügen können.

        0
 -3  0 -3
  ^

(([()()()])(()))
            ^

Wie bereits erwähnt, ()wird der obere Teil unseres dritten Stapels um eins erhöht.

        1
 -3  0 -3
  ^

(([()()()])(()))
              ^

Und )verschiebt den oberen Rand des dritten Stapels auf den aktiven Stapel und addiert ihn nach unten

  1
 -3  0 -2
  ^

(([()()()])(()))
               ^

Der letzte )verschiebt den dritten Stapel auf den aktiven Stapel, und da auf dem dritten Stapel keine Elemente mehr zum Hinzufügen vorhanden sind, geschieht nichts anderes.

 -2
  1
 -3  0
  ^

(([()()()])(()))
                ^

Das Programm ist beendet und wir beenden es und geben es aus.

Dieses Beispiel soll Ihnen ein Gefühl dafür vermitteln, was der dritte Stapel ist und tut. Es enthält nicht alle Operationen, aber hoffentlich können Sie herausfinden, was jede für sich tut. Wenn Sie immer noch Probleme haben, habe ich ein "Spickzettel" am Ende dieser Antwort beigefügt, um Ihnen weiterzuhelfen.

In Ordnung und jetzt?

Ok, jetzt verstehst du den dritten Stapel, aber "Na und"? Sie haben es bereits verwendet, auch wenn Sie es nicht als "Third Stack" bezeichnet haben. Wie hilft Ihnen das Denken in Bezug auf den Third Stack beim Golfen?

Schauen wir uns ein Problem an. Sie möchten das Dreieck einer Zahl nehmen . Dies ist die Summe aller Zahlen kleiner als n.

Ein Ansatz könnte darin bestehen, einen Akkumulator im Offstack zu erstellen und diesen beim Herunterzählen hinzuzufügen. Dies erzeugt Code, der so aussieht:

(<>)<>{(({}[()])()<>{})<>}{}<>({}<>)

Probieren Sie es online!

Dieser Code ist ziemlich kompakt und man könnte meinen, dass er nicht viel kleiner werden kann. Wenn wir es jedoch von einem dritten Stapel aus betrachten, wird klar, dass dies grob ineffizient ist. Anstatt unseren Akku in den Stapel zu legen, können wir ihn mit einem auf den dritten Stapel legen (und ihn am Ende unseres Gebrauchs abrufen ). Wir werden noch einmal alle Zahlen durchlaufen, aber dieses Mal müssen wir nicht viel tun, um unseren dritten Stapel zu erhöhen, das Programm erledigt das für uns. Das sieht so aus:

({()({}[()])}{})

Probieren Sie es online

Dieser Code ist weniger als halb so groß wie die ziemlich gut golfene Version, die wir zuvor gemacht haben. Tatsächlich hat eine Computersuche bewiesen, dass dieses Programm das kürzestmögliche Programm ist, das diese Aufgabe ausführen kann. Dieses Programm kann mit dem Ansatz "Summe aller Läufe" erklärt werden, aber ich denke, es ist viel intuitiver und klarer, wenn es mit einem Third-Stack-Ansatz erklärt wird.

Wann verwende ich den dritten Stapel?

Wenn Sie mit der Arbeit an einem neuen Problem in Brain-Flak beginnen, sollten Sie sich im Idealfall überlegen, wie ich dies mit Blick auf den dritten Stapel tun würde. Als Faustregel gilt jedoch, dass Sie immer dann, wenn Sie eine Art Akkumulator oder eine laufende Summe im Auge behalten müssen, versuchen sollten, diesen auf Ihren dritten Stapel zu legen, anstatt auf die beiden echten Stapel.

Eine andere Möglichkeit, über die Verwendung Ihres dritten Stapels nachzudenken, besteht darin, dass Sie auf den beiden anderen Stapeln keinen Platz zum Speichern von Werten haben. Dies kann besonders nützlich sein, wenn Sie an zwei vorhandenen Stapeln Änderungen vornehmen und einen Wert für die spätere Verwendung speichern möchten, ohne den Überblick zu behalten, wo er sich befindet.

Einschränkungen des dritten Stapels

Der dritte Stapel ist in vielerlei Hinsicht sehr leistungsfähig, hat jedoch seine eigenen Einschränkungen und Nachteile.

Zunächst wird die maximale Stapelhöhe für den dritten Stapel zu einem bestimmten Zeitpunkt zur Kompilierungszeit festgelegt. Dies bedeutet, dass Sie, wenn Sie eine Menge Speicherplatz auf dem Stapel verwenden möchten, diesen Speicherplatz beim Schreiben des Programms zuweisen müssen.

Zweitens ist der dritte Stapel kein wahlfreier Zugriff. Dies bedeutet, dass Sie keine Operationen mit einem Wert ausführen können, der nicht der höchste Wert ist. Außerdem können Sie keine Werte auf dem Stapel verschieben (z. B. die ersten beiden Elemente austauschen).

Fazit

Der dritte Stapel ist ein mächtiges Werkzeug und ich würde es für jeden Brain-Flak-Benutzer als wesentlich erachten. Es ist gewöhnungsbedürftig und erfordert ein Umdenken in Bezug auf das Programmieren in Brain-Flak, aber bei richtiger Anwendung macht es den Unterschied zwischen einem anständigen und einem erstaunlichen Golfspiel.

Spickzettel

Hier finden Sie eine Liste der Vorgänge und deren Auswirkungen auf den dritten Stapel

 Operation  |                 Action
====================================================
   (,[,<    | Put a zero on top of the Third Stack
----------------------------------------------------
     )      | Add the top of the Third Stack to the
            | second element and move it to the 
            | active stack
----------------------------------------------------
     ]      | Subtract the top of the Third Stack
            | from the second element and pop it
----------------------------------------------------
     >      | Pop the top of the Third Stack
----------------------------------------------------
     ()     | Add one to the top of the Third Stack
----------------------------------------------------
     {}     | Pop the top of the active stack and
            | add it to the top of the Third Stack
----------------------------------------------------
     []     | Add the stack height to the Third
            | Stack
----------------------------------------------------
   <>,{,}   | Nothing

Modul / Rest ermitteln

Das Finden von n Modulo m ist eine der Grundrechenarten, die für viele Herausforderungen wichtig ist. Für Fälle m> 0 und n> = 0 kann das folgende 46-Byte-Snippet verwendet werden. Es wird davon ausgegangen, dass n auf dem aktiven Stapel mit m auf dem nächsten Stapel liegt und durch n mod m ersetzt wird . Der Rest der Stapel bleibt erhalten.

({}(<>))<>{(({})){({}[()])<>}{}}{}<>([{}()]{})

Diese kommentierte Version zeigt den Stapelinhalt an einigen Stellen im Programm. ;trennt die beiden Stapel und .markiert den aktiven Stapel.

. n m;
({}(<>))<>
{   . m; r 0   (r = n - km)
    (({}))
    . m m; r 0
    {({}[()])<>}
    {}
}
m-n%m-1 m; . 0
{}<>([{}()]{})
. n%m;

Push-Pop-Redundanz

Dies ist eine große. Es ist auch ein bisschen nuanciert.

Die Idee ist, dass, wenn Sie etwas drücken und es dann öffnen, ohne etwas zu tun, Sie es überhaupt nicht gedrückt haben sollten.

Wenn Sie beispielsweise etwas in den Offstack verschieben und dann hinzufügen möchten, können Sie den folgenden Code eingeben:

({}<>)({}())

Das kann einfacher sein:

({}<>())

Das erste Programm nimmt den Gegenstand auf, bewegt ihn, nimmt ihn wieder auf und fügt einen hinzu, während das zweite Programm beides auf einen Schlag erledigt.

Dieses Beispiel war einfach, aber es kann sehr viel komplexer werden. Nimm zum Beispiel:

({}<({}<>)><>)(<((()()()){}[((){}{})])>)

Die Reduzierung ist hier weniger klar, aber der 4. Pop im Programm kann mit dem 2. Push wie folgt reduziert werden:

(<((()()()){}[((){}<({}<>)><>{})])>)

Dies ist das mächtigste Werkzeug in meinem Golfrepertoire, aber es bedarf einiger Übung, um es zu erlernen. Sobald Sie dies für eine Weile getan haben, können Sie diese fast sofort erkennen.

Optimieren Sie Ihre ganzen Zahlen

Ganzzahlen sind mühsam in Brain-Flak darzustellen. Zum Glück haben wir eine Frage, die Ihnen beim Golfen eines Brain-Flak-Integer hilft . (Beachten Sie, dass die Frage so konzipiert ist, dass die Ganzzahl auf den Stapel verschoben wird, sodass die Push-Pop-Redundanz wahrscheinlich für realistischere Programme gilt.)

Schieben Sie zusätzliche Schleifenzähler

Häufig möchten Sie so etwas tun

Führen Sie eine X- Operation für jedes Element im Stapel aus

oder

Führe X aus Operation für jedes Paar benachbarter Elemente im Stapel aus

Wenn die Eingabe '0' enthalten kann oder das Ergebnis der Operation X eine 0 ergibt, ist dies wirklich unpraktisch. Weil du Folgendes tun musst:

([])
{

  {}

  ({}...<>)
  ([])

}

Gehen Sie X auf jedes Element, und dann später

<>
([])
{
  {}
  ({}<>)
  <>
  ([])
}
<>

So kehren Sie das Array erneut um

Schlimmer noch, wenn wir mit Paaren benachbarter Elemente arbeiten, müssen wir dies ([][()])anstelle von tun ([]). Das ist wirklich unpraktisch. Hier ist der Trick: Während Sie X für jedes Element ausführen, drücken Sie eine 1 auf den alternativen Stapel direkt über dem X(element). Dann, während Sie es umkehren, können Sie einfach tun

<>
{
  {}
  ({}<>)
  <>
}
<>

Dies ist 8 Bytes kürzer. Wenn Sie also den zusätzlichen Code für Push 1 berücksichtigen, sparen Sie am Ende 4-6 Bytes. Vergleichen Sie für ein konkreteres Beispiel die Aufgabe, Deltas eines Arrays abzurufen. Ohne diesen Trick brauchst du:

([][()]){

    {}

    ([{}]({})<>)<>

    ([][()])

}{}{}<>

([])
{{}({}<>)<>([])}<>

Für 62. Mit diesem Trick haben Sie

([][()]){

    {}

    ([{}]({})<>)(())<>

    ([][()])

}{}{}<>

{{}({}<>)<>}<>

Für 58. Bei richtiger Verwendung (z. B. zuerst umkehren und ([][()])später zwei entfernen ) könnte dies in bestimmten Szenarien noch mehr sparen.

Nutzen Sie den 'Stack-Height'-Nilad

Insbesondere bei Herausforderungen mit Kolmogorov-Komplexität oder bei Herausforderungen, bei denen Sie die Größe der Eingabe immer kennen, können Sie den Nullpunkt "Stapelhöhe " verwenden [], um Ganzzahlen zu erstellen.

Lassen Sie uns dies mit einer hypothetischen Herausforderung durcharbeiten: Ausgabe CAT. Der nicht-golfende Weg besteht darin, den Online-Integer-Golfer zu verwenden, um 67, 65 und 84 zu drücken.

(((((()()()()){}){}){}()){}())

(((((()()()()){}){}){}){}())

((((((()()()){}()){}){})){}{})

(Zeilenumbrüche zur Verdeutlichung). Das sind 88 Bytes und nicht so toll. Wenn wir stattdessen die aufeinander folgenden Unterschiede zwischen den Werten verschieben, können wir viel sparen. Also wickeln wir die erste Zahl in einen Push- Anruf ein und subtrahieren 2:

(   (((((()()()()){}){}){}()){}())  [()()] )

Dann nehmen wir diesen Code, wickeln ihn in einen Push- Aufruf ein und fügen am Ende 19 hinzu:

(  ((((((()()()()){}){}){}()){}())[()()])   ((((()()()){})){}{}()) )

Dies sind 62 Bytes, für eine unglaubliche 26-Byte-Golf!

Jetzt hier ist , wo wir die Vorteile der Stapelhöhe nilad nehmen zu bekommen. Als wir 19 drängen beginnen, wissen wir , dass es bereits zwei Elemente auf dem Stapel, so []wird bewerten zu 2. Wir können dies verwenden, um eine 19 in weniger Bytes zu erstellen. Der naheliegende Weg ist, das Innere ()()()zu verändern ()[]. Dies spart jedoch nur zwei Bytes. Es stellt sich heraus, dass wir mit etwas mehr basteln können

((([][]){})[]{})

Das spart uns 6 Bytes. Jetzt sind wir bei 56 angelangt.

Sie können sehen, dass dieser Tipp bei den folgenden Antworten sehr effektiv verwendet wird:

• Hallo Welt V1

• Hallo Welt V2

• Magie Die Versammlung, Freund oder Feind

• Die fehlende Ganzzahl ausgeben

• Diagonales Alphabet (mein persönlicher Favorit)

Benutze das Wiki

Wir haben ein Wiki ! Es hat einige Mängel, aber es ist eine hilfreiche Ressource. Es enthält Listen nützlicher, gut funktionierender, sauberer Stapelprogramme, die Sie in Ihren Code einfügen können. Wenn du etwas tun willst, von dem du denkst, dass es jemand getan hat, bevor es eine gute Chance gibt, ist es im Wiki.

Besseres Looping

Hier ist eine einfache:

Ein ziemlich verbreitetes Konstrukt ist:

(({})<{({}[()]<...>)}{}>)

Wo du n-mal loopen willst und trotzdem die n behalten willst. Dies kann jedoch wie folgt geschrieben werden:

({<({}[()]<...>)>()}{})

um 2 Bytes zu sparen.

Ein anderes ziemlich verbreitetes Paradigma ist

([])({<{}>...<([])>}{})

Dadurch wird der gesamte Stapel geloopt und angesammelt. Aufgrund einiger ausgefallener Mathematik ist dies dasselbe wie:

(([]){[{}]...([])}{})

Überprüfen Sie Ihre Negative

Manchmal können Sie ein paar Bytes Golf spielen, indem Sie strategisch auswählen, was mit dem zu negieren ist [...] Monade .

Ein einfaches Beispiel ist in verschachtelten [...]s. Könnte zum Beispiel [()()()[()()]]nur sein[()()()]()()

Angenommen, Sie möchten überprüfen, ob ein Wert in einer der Startklammern steht (<{[. Der erste Versuch besteht darin, die Differenz zwischen den einzelnen Zeichen zu ermitteln und sie in einer Schleife zu subtrahieren

({}<(((((       #Push the differences between start bracket characters
(((()()()()){}){}){})   #Push 32
[()])                   #Push 31
[((()()())()){}{}])     #Push 20
){})><>)                #Push 40
<>({<(([{}]<>{}))>(){[()](<{}>)}<>})

Sie können jedoch 4 Byte einsparen, indem Sie stattdessen die negativen Versionen der Unterschiede verschieben!

({}<(((((       #Push the differences between start bracket characters
((([()()()()]){}){}){}) #Push -32
())                     #Push -31
((()()())()){}{})       #Push -20
){})><>)                #Push -40
<>({<(({}<>{}))>(){[()](<{}>)}<>})

Im Allgemeinen spart dies nicht viel, aber es kostet auch sehr wenig Aufwand, um die [...]Umgebung zu ändern . Halten Sie Ausschau nach Situationen, in denen Sie das Negativ eines Zählers anstelle des Positivs drücken können, um zu sparen, dass Sie mehrmals inkrementieren, anstatt später zu dekrementieren. Oder tauschen Sie (a[b])mit aus ([a]b), um die Differenz zwischen zwei negativen statt positiven Zahlen zu ermitteln.