Schnellste Mini-Flak-Quine

26

Mini-Flak ist eine Teilmenge der Brain-Flak- Sprache <>.<...> und []Operationen nicht zulässig sind. Genau genommen darf es nicht mit dem folgenden regulären Ausdruck übereinstimmen :

.*(<|>|\[])

Mini-Flak ist die kleinste bekannte Turing-Teilmenge von Brain-Flak.

Vor einiger Zeit konnte ich eine machen Quine in Mini-Flak herstellen , aber es war zu langsam, um im Leben des Universums zu laufen.

Meine Herausforderung für Sie ist es, ein schnelleres Quine zu machen.

Wertung

Um Ihren Code zu bewerten, setzen Sie ein @cyFlag am Ende Ihres Codes und führen Sie es im Ruby-Interpreter ( Try it Online verwendet den Ruby-Interpreter) mit dem -dFlag aus. Ihre Punktzahl sollte wie folgt an STDERR gesendet werden:

@cy <score>

Dies ist die Anzahl der Zyklen, die Ihr Programm vor dem Beenden benötigt, und ist zwischen den Durchläufen gleich. Da für die Ausführung jedes Zyklus ungefähr dieselbe Zeit erforderlich ist, sollte Ihre Punktzahl in direktem Zusammenhang mit der Zeit stehen, die für die Ausführung Ihres Programms erforderlich ist.

Wenn Ihr Quine zu lang ist, um auf Ihrem Computer ausgeführt zu werden, können Sie die Anzahl der Zyklen von Hand berechnen.

Die Anzahl der Zyklen zu berechnen ist nicht sehr schwierig. Die Anzahl der Zyklen entspricht dem Zweifachen der Anzahl der durchgeführten Monaden plus der Anzahl der durchgeführten Niladen. Dies entspricht dem Ersetzen jedes Nullpunkts durch ein einzelnes Zeichen und dem Zählen der insgesamt ausgeführten Zeichen.

Beispiel Wertung

  • (()()()) punktet mit 5, weil es 1 Monade und 3 Niladen hat.

  • (()()()){({}[()])} erhält 29 Punkte, da der erste Teil derselbe wie zuvor ist und 5 Punkte erhält, während die Schleife 6 Monaden und 2 Niladen enthält, die 8 Punkte erzielen. Die Schleife wird dreimal ausgeführt, daher zählen wir ihre Punkte dreimal. 1*5 + 3*8 = 29

Bedarf

Ihr Programm muss ...

  • Seien Sie mindestens 2 Bytes

  • Gibt den Quellcode aus, wenn er in Brain-Flak mit dem -AFlag ausgeführt wird

  • Nicht mit dem regulären Ausdruck übereinstimmen .*(<|>|\[])

Tipps

  • Der Crane-Flak- Interpreter ist wesentlich schneller als der Ruby-Interpreter, verfügt jedoch nicht über die erforderlichen Funktionen. Ich würde empfehlen, Ihren Code zuerst mit Crane-Flak zu testen und ihn dann im Ruby-Interpreter zu bewerten, wenn Sie wissen, dass er funktioniert. Ich würde auch wärmstens empfehlen, Ihr Programm nicht in TIO auszuführen. TIO ist nicht nur langsamer als der Desktop-Interpreter, sondern es tritt auch eine Zeitüberschreitung von etwa einer Minute auf. Es wäre sehr beeindruckend, wenn es jemandem gelingen würde, ein so niedriges Ergebnis zu erzielen, dass er sein Programm ausführen kann, bevor die TIO-Zeit abgelaufen ist.

  • [(...)]{}und (...)[{}]arbeiten genauso wie, <...>aber brechen Sie nicht die eingeschränkte Quellenanforderung

  • Sie können Brain-Flak- und Mini-Flak- Quines ausprobieren, wenn Sie eine Vorstellung davon haben möchten, wie Sie sich dieser Herausforderung stellen können.

restricted-source quine fastest-code brain-flak Weizen-Assistent
quelle
1
"aktuell am besten" -> "nur aktuell"
HyperNeutrino

Antworten:

33

Mini-Flak, 6851113 Zyklen

Das Programm (wörtlich)

Ich weiß, dass die meisten Leute nicht damit rechnen, dass ein Mini-Flak-Quine nicht druckbare Zeichen und sogar Mehrbyte-Zeichen verwendet (was die Codierung relevant macht). Diese Quine macht es jedoch ziemlich schwierig, das Programm in diesem Beitrag zu platzieren, und die Unprintables in Kombination mit der Größe der Quine (93919 Zeichen, codiert als 102646 Bytes UTF-8).

Das Programm ist jedoch sehr repetitiv und wird als solches sehr gut komprimiert . Damit das gesamte Programm buchstäblich von Stack Exchange aus verfügbar ist, gibt es einen xxdreversiblen Hexdump einer gzipkomprimierten Version des vollständigen Quine, der sich hinter dem reduzierbaren darunter verbirgt:

Code-Snippet anzeigen

(Ja, es ist so repetitiv, dass Sie sogar die Wiederholungen sehen können, nachdem es komprimiert wurde).

In der Frage steht: "Ich würde Ihnen auch wärmstens empfehlen, Ihr Programm nicht in TIO auszuführen. TIO ist nicht nur langsamer als der Desktop-Interpreter, sondern es tritt auch eine Zeitüberschreitung von etwa einer Minute auf. Es wäre äußerst beeindruckend, wenn es jemandem gelingen würde, niedrig genug zu sein, um ausgeführt zu werden ihr Programm, bevor TIO abgelaufen ist. " Ich kann das machen! Mit dem Ruby-Interpreter dauert es ungefähr 20 Sekunden, bis TIO ausgeführt wird: Probieren Sie es online aus!

Das Programm (lesbar)

Jetzt habe ich eine Version des Programms angegeben, die Computer lesen können. Probieren wir eine Version aus, die Menschen lesen können. Ich habe die Bytes, aus denen sich das Quine zusammensetzt, in Codepage 437 (sofern das hohe Bit gesetzt ist) oder Unicode-Steuerbilder (sofern es sich um ASCII-Steuercodes handelt) konvertiert und Leerzeichen hinzugefügt (alle zuvor vorhandenen Leerzeichen wurden in Steuerbilder konvertiert) ), «string×length»lauflängencodiert mit der Syntax und einige datenintensive Bits beseitigt:

␠
(((()()()()){}))
{{}
    (({})[(()()()())])
    (({})(
        {{}{}((()[()]))}{}
        (((((((({})){}){}{})){}{}){}){}())
        {
            ({}(
                (␀␀!S␠su! … many more comment characters … oq␝qoqoq)
                («()×35» («()×44» («()×44» («()×44» («()×44» («()×45»
                … much more data encoded the same way …
                («()×117»(«()×115»(«()×117»
                «000010101011┬â┬ … many more comment characters … ┬â0┬â┬à00␈␈
                )[({})(
                    ([({})]({}{}))
                    {
                        ((()[()]))
                    }{}
                    {
                        {
                            ({}(((({}())[()])))[{}()])
                        }{}
                        (({}))
                        ((()[()]))
                    }{}
                )]{}
                %Wwy$%Y%ywywy$wy$%%%WwyY%$$wy%$$%$%$%$%%wy%ywywy'×almost 241»
                ,444454545455┬ç┬ … many more comment characters … -a--┬ü␡┬ü-a␡┬ü
            )[{}()])
        }{}
        {}({}())
    )[{}])
    (({})(()()()()){})
}{}{}␊

(Die "fast 241" liegt daran, dass in der 241. Kopie das Ende fehlt ', sie ist jedoch ansonsten identisch mit der anderen 240.)

Erläuterung

Über die Kommentare

Die erste Sache, die erklärt werden muss, ist, was mit den nicht druckbaren Zeichen und anderem Müll los ist, die keine Mini-Flak-Befehle sind. Sie mögen denken, dass das Hinzufügen von Kommentaren zum Quine die Dinge nur schwieriger macht, aber dies ist ein Geschwindigkeitswettbewerb (kein Größenwettbewerb), was bedeutet, dass Kommentare die Geschwindigkeit des Programms nicht beeinträchtigen. Währenddessen wird der Inhalt des Stapels von Brain-Flak und damit von Mini-Flak auf die Standardausgabe ausgegeben. wenn Sie sicherstellen müssten, dass der Stapel enthalten ist nurFür die Zeichen, aus denen die Befehle Ihres Programms bestanden, müssten Sie Zyklen zum Reinigen des Stapels durchführen. So wie es ist, ignoriert Brain-Flak die meisten Zeichen, solange wir sicherstellen, dass Junk-Stack-Elemente keine gültigen Brain-Flak-Befehle sind (was dies zu einem Brain-Flak / Mini-Flak-Polyglot macht) und nicht negativ oder außerhalb sind Im Unicode-Bereich können wir sie einfach auf dem Stapel belassen, ausgeben lassen und dasselbe Zeichen in unser Programm an derselben Stelle einfügen, um die quine-Eigenschaft beizubehalten.

Es gibt eine besonders wichtige Möglichkeit, dies auszunutzen. Das Quine verwendet eine lange Datenzeichenfolge, und im Grunde wird die gesamte Ausgabe des Quine durch Formatieren der Datenzeichenfolge auf verschiedene Arten erzeugt. Es gibt nur einen Datenstring, obwohl das Programm mehrere Teile hat. Daher müssen wir in der Lage sein, denselben Datenstring zum Drucken verschiedener Teile des Programms zu verwenden. Mit dem Trick "Junk-Daten spielen keine Rolle" können wir dies auf sehr einfache Weise tun. Wir speichern die Zeichen, aus denen das Programm besteht, in der Datenfolge, indem wir einen Wert zu oder von ihrem ASCII-Code addieren oder subtrahieren. Insbesondere werden die Zeichen, aus denen der Programmstart besteht, als ASCII-Code + 4 gespeichert, die Zeichen, aus denen der Abschnitt besteht, der fast 241-mal als ASCII-Code - 4 wiederholt wird.jedes Zeichen der Datenkette mit einem Offset; Wenn wir es zum Beispiel mit 4 zu jedem Zeichencode drucken, erhalten wir eine Wiederholung des wiederholten Abschnitts mit einigen Kommentaren davor und danach. (Diese Kommentare sind einfach die anderen Abschnitte des Programms, wobei die Zeichencodes so verschoben sind, dass sie keine gültigen Brain-Flak-Befehle bilden, da der falsche Versatz hinzugefügt wurde. Wir müssen Brain-Flak-Befehlen ausweichen, nicht nur Mini- Flak-Befehle, um Verletzungen der eingeschränkten Quelle zu vermeiden der Frage ; die Auswahl von Offsets wurde entwickelt, um dies zu gewährleisten.)

Aufgrund dieses Kommentar-Tricks müssen wir eigentlich nur in der Lage sein, den auf zwei verschiedene Arten formatierten Datenstring auszugeben: a) auf die gleiche Weise wie in der Quelle codiert, b) als Zeichencodes mit einem festgelegten Versatz, der jedem Code hinzugefügt wird. Das ist eine enorme Vereinfachung, die die zusätzliche Länge absolut wert macht.

Programmstruktur

Dieses Programm besteht aus vier Teilen: dem Intro, dem Datenstring, dem Datenstring-Formatierer und dem Outro. Das Intro und Outro sind grundsätzlich dafür verantwortlich, den Datenstring und seinen Formatierer in einer Schleife auszuführen und dabei jedes Mal das entsprechende Format anzugeben (dh ob codiert oder versetzt werden soll und welcher Offset verwendet werden soll). Der Datenstring ist nur ein Datenstring und der einzige Teil des Quines, für den die Zeichen, aus denen er besteht, nicht wörtlich im Datenstring angegeben sind (dies wäre offensichtlich unmöglich, da es länger sein müsste als er selbst). Es ist so geschrieben, dass es besonders einfach ist, sich von selbst zu regenerieren. Der Datenkettenformatierer besteht aus 241 nahezu identischen Teilen, von denen jeder ein bestimmtes Datum aus den 241 in der Datenkette formatiert.

Jeder Teil des Programms kann wie folgt über den Datenstring und dessen Formatierer erstellt werden:

  • Formatieren Sie den Datenstring mit Offset +8, um das Outro zu erzeugen
  • Formatieren Sie die Datenzeichenfolge mit Offset +4, 241 mal, um den Datenzeichenfolge-Formatierer zu erstellen
  • Formatieren Sie die Datenzeichenfolge, um sie zu erstellen, indem Sie sie in das Quellformat codieren
  • Formatieren Sie die Datenzeichenfolge mit Offset -4, um das Intro zu erstellen

Wir müssen uns also nur ansehen, wie diese Teile des Programms funktionieren.

Die Datenzeichenfolge

(«()×35» («()×44» («()×44» («()×44» («()×44» («()×45» …

Wir benötigen eine einfache Codierung für den Datenstring, da wir die Codierung im Mini-Flak-Code umkehren können müssen. Einfacher geht es nicht!

Die Schlüsselidee hinter dieser Quine (abgesehen vom Kommentar-Trick) ist, dass es im Grunde nur einen Ort gibt, an dem wir große Datenmengen speichern können: die "Summen der Befehlsrückgabewerte" in den verschiedenen Verschachtelungsebenen der Programmquelle. (Dies ist allgemein als dritter Stapel bekannt "Arbeitsstapel", obwohl Mini-Flak keinen zweiten Stapel hat. "Arbeitsstapel" wahrscheinlich ein besserer Name im Mini-Flak-Kontext.) Die anderen Möglichkeiten zum Speichern von Daten wären main / first Stack (was nicht funktioniert, weil dort unsere Ausgabe abgelegt werden muss und wir die Ausgabe nicht auf eine remote effiziente Weise am Speicher vorbei verschieben können) und in ein Bignum in einem einzelnen Stack-Element codiert (was hierfür ungeeignet ist) Problem, weil es exponentiell lange dauert, Daten daraus zu extrahieren); wenn Sie diese beseitigen,

Um Daten auf diesem Stapel zu "speichern", verwenden wir unsymmetrische Befehle (in diesem Fall die erste Hälfte eines (…)Befehls), die später im Formatierer der Datenzeichenfolge verteilt werden. Jedes Mal, wenn wir einen dieser Befehle im Formatierer schließen, wird die Summe eines aus der Datenzeichenfolge entnommenen Datums und die Rückgabewerte aller Befehle auf dieser Verschachtelungsebene im Formatierer übertragen. Wir können sicherstellen, dass letztere zu Null addieren, sodass der Formatierer nur einzelne Werte aus dem Datenstring sieht.

Das Format ist sehr einfach: (gefolgt von n Kopien von (), wobei n die Zahl ist, die wir speichern möchten. (Beachten Sie, dass dies bedeutet, dass wir nur nicht negative Zahlen speichern können und das letzte Element der Datenzeichenfolge positiv sein muss.)

Ein etwas uninteressanter Punkt an der Datenzeichenfolge ist die Reihenfolge, in der sie sich befindet. Der "Anfang" der Datenzeichenfolge ist das Ende, das näher am Programmanfang liegt, dh die äußerste Verschachtelungsebene. Dieser Teil wird zuletzt formatiert (da der Formatierer von der innersten bis zur äußersten Verschachtelungsebene ausgeführt wird). Obwohl es zuletzt formatiert wurde, wird es zuerst gedruckt , da zuerst auf den Stapel geschobene Werte zuletzt vom Mini-Flak-Interpreter gedruckt werden. Dasselbe Prinzip gilt für das gesamte Programm. Wir müssen zuerst das Outro formatieren, dann den Datenstring-Formatierer, dann den Datenstring und dann das Intro, dh in umgekehrter Reihenfolge, in der sie im Programm gespeichert sind.

Der Formatierer der Datenzeichenfolge

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

Der Datenstring-Formatierer besteht aus 241 Abschnitten mit identischem Code (ein Abschnitt hat einen geringfügig unterschiedlichen Kommentar), die jeweils ein bestimmtes Zeichen des Datenstrings formatieren. (Wir konnten hier keine Schleife verwenden: Wir benötigen eine unsymmetrische Schleife ), um den Datenstring über den Abgleich mit der unsymmetrischen zu lesen (, und wir können keine solche {…}Schleife in eine Schleife einfügen, die einzige Form der Schleife, die existiert. Stattdessen verwenden wir "Entrollen Sie den Formatierer und veranlassen Sie einfach das Intro / Outro, die Datenzeichenfolge mit dem 241-fachen Versatz des Formatierers auszugeben.)

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

Der äußerste Teil eines Formatierungselements liest ein Element der Datenzeichenfolge. Die einfache Codierung des Datenstrings führt zu einer geringen Komplexität beim Lesen. Wir schließen zunächst den nicht übereinstimmenden Wert in der Datenzeichenfolge (…)und negieren dann ( […]) zwei Werte: das Datum, das wir gerade aus der Datenzeichenfolge ( ({})) gelesen haben, und den Rückgabewert des restlichen Programms. Wir kopieren den Rückgabewert des restlichen Formatierungselements mit (…)und fügen die Kopie der negierten Version mit hinzu {}. Das Endergebnis ist, dass der Rückgabewert des Datenzeichenfolgenelements und des Formatierungselements zusammen das Datum minus das Datum minus den Rückgabewert plus den Rückgabewert oder 0 ist. Dies ist erforderlich, damit das nächste Datenzeichenfolgenelement den richtigen Wert ergibt.

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

Der Formatierer verwendet das oberste Stapelelement, um zu ermitteln, in welchem ​​Modus es sich befindet (0 = Format bei der Formatierung von Datenzeichenfolgen, jeder andere Wert = der Offset, mit dem ausgegeben werden soll). Nachdem Sie jedoch die Datenzeichenfolge gelesen haben, befindet sich das Datum über dem Format auf dem Stapel, und wir möchten, dass sie umgekehrt sind. Dieser Code ist eine kürzere Variante des Brain-Flak-Tauschcodes, wobei a über b nach b über a  +  b steht . Es ist nicht nur kürzer, sondern (in diesem speziellen Fall) auch nützlicher, da der Nebeneffekt des Hinzufügens von b zu a nicht problematisch ist, wenn b 0 ist, und wenn b nicht 0 ist, wird die Offsetberechnung für uns durchgeführt.

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

Brain-Flak hat nur eine Kontrollflussstruktur. Wenn wir also etwas anderes als eine whileSchleife wollen, wird es ein bisschen Arbeit kosten. Dies ist eine "negative" Struktur; Wenn oben auf dem Stapel eine 0 ist, wird diese entfernt, andernfalls wird eine 0 oben auf dem Stapel platziert. (Das funktioniert ganz einfach: Solange sich keine 0 auf dem Stapel befindet, drücken Sie zweimal 1 - 1 auf den Stapel. Wenn Sie fertig sind, platzieren Sie das oberste Stapelelement.)

Es ist möglich, Code in eine Negativstruktur einzufügen, wie hier zu sehen. Der Code wird nur ausgeführt, wenn der Anfang des Stapels ungleich Null war. so , wenn wir zwei negate Strukturen haben, die beiden oberen Stapelelemente unter der Annahme sind nicht beide Nullen, werden sie sich gegenseitig aufheben, aber jeder Code innerhalb der ersten Struktur wird nur ausgeführt , wenn das obere Stapelelement ungleich Null ist, und der Code innerhalb Die zweite Struktur wird nur ausgeführt, wenn das oberste Stapelelement Null war. Mit anderen Worten, dies entspricht einer if-then-else-Anweisung.

In der "then" -Klausel, die ausgeführt wird, wenn das Format nicht Null ist, haben wir eigentlich nichts zu tun. Was wir wollen, ist, die Daten + Offset auf den Hauptstapel zu schieben (damit sie am Ende des Programms ausgegeben werden können), aber es ist bereits da. Wir müssen uns also nur mit dem Codieren des Datenzeichenfolgenelements in Quellform befassen.

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

So machen wir das. Die {({}( … )[{}()])}{}Struktur sollte als Schleife mit einer bestimmten Anzahl von Iterationen bekannt sein (dies funktioniert, indem der Schleifenzähler auf den Arbeitsstapel verschoben und dort gehalten wird; er ist vor jedem anderen Code geschützt, da der Zugriff auf den Arbeitsstapel damit verbunden ist Verschachtelungsebene des Programms). Der Hauptteil der Schleife ist ((({}())[()])), der drei Kopien des obersten Stapelelements erstellt und 1 zum niedrigsten addiert. Mit anderen Worten, es wandelt eine 40 auf dem Stapel in 40 über 40 über 41 oder als ASCII betrachtet (in ((); Wenn Sie dies wiederholt ausführen, wird dies (zu einem (()In- (()()In (()()()und so weiter. Dies ist ein einfacher Weg, um unsere Datenzeichenfolge zu generieren (vorausgesetzt, es befindet sich bereits eine (Oben-Position auf dem Stapel).

Sobald wir mit der Schleife fertig sind, (({}))duplizieren Sie den oberen Teil des Stapels (so dass er jetzt beginnt ((()…und nicht mehr (()…. Der führende (Teil wird von der nächsten Kopie des Formatierers für Datenzeichenfolgen verwendet, um das nächste Zeichen zu formatieren (es wird erweitert) (()(()…dann (()()(()…, und so weiter, so dass dies die Trennung (in der Datenzeichenfolge erzeugt).

%Wwy$%Y%ywywy$wy$%%%WwyY%$$wy%$$%$%$%$%%wy%ywywy'

Es gibt noch ein letztes interessantes Element im Formatierer der Datenzeichenfolge. OK, also meistens sind es nur die um 4 Codepunkte nach unten verschobenen Outro-Werte. Dieses Apostroph am Ende kann jedoch unangebracht aussehen. '(Codepunkt 39) verschiebt sich in +(Codepunkt 43), was kein Brain-Flak-Befehl ist. Vielleicht haben Sie erraten, dass er für einen anderen Zweck da ist.

Der Grund dafür ist, dass der Datenstring-Formatierer erwartet, dass sich bereits ein (auf dem Stapel befindet (er enthält nirgendwo ein Literal 40). Das'befindet sich tatsächlich am Anfang des Blocks, der wiederholt wird, um den Formatierer der Datenzeichenfolge zu bilden, und nicht am Ende. Nachdem die Zeichen des Formatierers der Datenzeichenfolge auf den Stapel geschoben wurden (und der Code im Begriff ist, mit dem Drucken der Datenzeichenfolge fortzufahren) selbst), passt das Outro die 39 oben auf dem Stapel in eine 40 an, die bereit ist, damit der Formatierer (diesmal der laufende Formatierer selbst, nicht seine Darstellung in der Quelle) davon Gebrauch macht. Deshalb haben wir "fast 241" Kopien des Formatierers; In der ersten Kopie fehlt das erste Zeichen. Und dieses Zeichen, der Apostroph, ist eines von nur drei Zeichen in der Datenfolge, die nicht dem Mini-Flak-Code irgendwo im Programm entsprechen. Es ist lediglich eine Methode zur Bereitstellung einer Konstanten.

Das Intro und Outro

(((()()()()){}))
{{}
    (({})[(()()()())])
    (({})(
        {{}{}((()[()]))}{}
        (((((((({})){}){}{})){}{}){}){}())
        {
            ({}(
                (␀␀!S␠su! … many more comment characters … oq␝qoqoq)
                …
            )[{}()])
        }{}
        {}({}())
    )[{}])
    (({})(()()()()){})
}{}{}␊

Intro und Outro sind konzeptionell derselbe Teil des Programms. Der einzige Grund, warum wir einen Unterschied machen, ist, dass das Outro vor dem Datenstring und seinem Formatierer ausgegeben werden muss (damit es nach ihnen gedruckt wird), während das Intro nach ihnen ausgegeben werden muss (vor ihnen gedruckt wird).

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

Wir beginnen damit, zwei Kopien von 8 auf den Stapel zu legen. Dies ist der Offset für die erste Iteration. Die zweite Kopie ist, weil die Hauptschleife erwartet, dass sich über dem Versatz ein Junk-Element oben auf dem Stapel befindet, das vom Test übrig bleibt, der entscheidet, ob die Hauptschleife vorhanden ist. Daher müssen wir dort ein Junk-Element platzieren es wirft nicht das Element weg, das wir wirklich wollen; Eine Kopie ist der schnellste Weg, dies zu tun.

Es gibt andere Darstellungen der Zahl 8, die nicht länger als diese sind. Wenn Sie sich jedoch für den schnellsten Code entscheiden, ist dies definitiv die beste Option. Zum einen ist using ()()()()schneller als zum Beispiel, (()()){}weil erstere, obwohl beide 8 Zeichen lang sind, ein Zyklus schneller ist, weil (…)sie als 2 Zyklen gezählt werden, aber ()nur als einer. Das Speichern eines Zyklus ist jedoch vernachlässigbar, verglichen mit einer viel größeren Überlegung für einen Quine : (und )hat viel niedrigere Codepunkte als {und }, so dass das Generieren des Datenfragments für sie viel schneller ist (und das Datenfragment weniger Platz im Code einnimmt, auch).

{{} … }{}{}

Die Hauptschleife. Dies zählt keine Iterationen (es ist eine whileSchleife, keine forSchleife, und verwendet einen Test, um auszubrechen). Sobald es beendet ist, werden die beiden obersten Stapelelemente verworfen. Das oberste Element ist eine harmlose 0, aber das Element darunter ist das "Format, das bei der nächsten Iteration verwendet werden soll", das (als negativer Versatz) eine negative Zahl ist und wenn sich beim Mini negative Zahlen auf dem Stapel befinden -Flak-Programm beendet sich, der Interpreter stürzt ab und versucht, sie auszugeben.

Da diese Schleife einen expliziten Test verwendet, um auszubrechen, verbleibt das Ergebnis dieses Tests auf dem Stapel, sodass wir es als erstes verwerfen (sein Wert ist nicht nützlich).

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

Dieser Code verschiebt 4 und f  - 4 über ein Stapelelement f , während dieses Element an Ort und Stelle bleibt. Wir berechnen das Format für die nächste Iteration im Voraus (während wir die Konstante 4 zur Hand haben) und bringen gleichzeitig den Stapel für die nächsten Teile des Programms in die richtige Reihenfolge: Wir verwenden f als Format für Diese Iteration, und die 4 wird davor benötigt.

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

Dadurch wird eine Kopie von f  - 4 auf dem Arbeitsstapel gespeichert, damit wir sie für die nächste Iteration verwenden können. (Der Wert von f ist zu diesem Zeitpunkt immer noch vorhanden, befindet sich jedoch an einer ungünstigen Stelle auf dem Stapel, und selbst wenn wir ihn an die richtige Stelle manövrieren könnten, müssten wir Zyklen damit verbringen, 4 von ihm zu subtrahieren. und druckt den Code zyklisch aus, um diese Subtraktion durchzuführen.

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

Ein Test, um festzustellen, ob der Versatz 4 ist (dh f  - 4 ist 0). Wenn dies der Fall ist, drucken wir den Formatierer der Datenzeichenfolge. Daher müssen wir die Datenzeichenfolge und ihren Formatierer 241-mal ausführen und nicht nur einmal an diesem Versatz. Der Code ist recht einfach: Wenn f  - 4 ungleich Null ist, ersetzen Sie f  - 4 und die 4 selbst durch ein Nullenpaar. In beiden Fällen platzieren Sie das oberste Stapelelement. Wir haben jetzt eine Zahl über f auf dem Stapel, entweder 4 (wenn wir diese Iteration 241 Mal drucken möchten) oder 0 (wenn wir sie nur einmal drucken möchten).

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

Dies ist eine interessante Art von Brain-Flak / Mini-Flak-Konstante; Die lange Linie stellt hier die Zahl 60 dar. Sie können verwirrt sein über das Fehlen von (), die normalerweise überall in Brain-Flak-Konstanten vorkommen; Dies ist keine reguläre Zahl, sondern eine Kirchenzahl, die Zahlen als Vervielfältigungsoperation interpretiert. Zum Beispiel erstellt die hier gezeigte Kirchenzahl für 60 60 Kopien ihrer Eingabe und kombiniert sie alle zu einem einzigen Wert. In Brain-Flak können wir nur reguläre Zahlen durch Addition kombinieren, sodass wir am Ende 60 Kopien der Stapeloberseite addieren und somit die Stapeloberseite mit 60 multiplizieren.

Als Randnotiz können Sie einen Unterlast-Nummernfinder verwenden , der Church-Nummern in Unterlast-Syntax generiert, um die entsprechende Nummer auch in Mini-Flak zu finden. Unterlastungszahlen (ungleich Null) verwenden die Operationen "oberstes Stapelelement duplizieren" :und "oberste zwei Stapelelemente kombinieren" *; beide diese Operationen existieren in Brain-Flak, so dass Sie nur übersetzen :zu ), *zu {}, prepend ein {}, und fügen Sie genug (zu Beginn zu Balance (das eine seltsame Mischung aus dem Hauptstapel verwendet und Arbeitsstapel, aber es funktioniert).

Dieses bestimmte Codefragment verwendet die Kirchenzahl 60 (effektiv ein "Multiplizieren mit 60" -Schnipsel) zusammen mit einem Inkrement, um den Ausdruck 60 x  + 1 zu generieren. Wenn wir also eine 4 aus dem vorherigen Schritt hatten, ergibt dies einen Wert von 241, oder wenn wir eine 0 hatten, erhalten wir nur einen Wert von 1, dh dies berechnet die Anzahl der Iterationen, die wir benötigen, korrekt.

Die Wahl von 241 ist kein Zufall; Es wurde ein Wert gewählt, der a) ungefähr der Länge entspricht, bei der das Programm ohnehin enden würde, und b) 1 mehr als das Vierfache einer runden Zahl. Runde Zahlen, in diesem Fall 60, sind in der Regel kürzer als Zahlen in der Kirche, weil Sie flexibler in Bezug auf die zu kopierenden Faktoren sind. Das Programm enthält später eine Auffüllung, um die Länge genau auf 241 zu bringen.

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

Dies ist eine for - Schleife, wie die oben gezeigte, die den Code einfach so oft ausführt, wie er im oberen Bereich des Hauptstapels enthalten ist (den sie verbraucht; der Schleifenzähler selbst ist auf dem Arbeitsstapel gespeichert, aber die Sichtbarkeit von Dies ist an die Verschachtelungsebene des Programms gebunden und daher ist es unmöglich, dass etwas anderes als die for-Schleife selbst damit interagiert. Auf diese Weise werden der Datenstring und sein Formatierer 1 oder 241 Mal ausgeführt. Da wir nun alle Werte, die wir für die Berechnung des Kontrollflusses verwendet haben, vom Hauptstapel abgerufen haben, haben wir das Format, das darauf verwendet werden kann, bereit der zu verwendende Formatierer.

(␀␀!S␠su! … many more comment characters … oq␝qoqoq)

Der Kommentar hier ist nicht ganz ohne Interesse. Zum einen gibt es ein paar Brain-Flak-Befehle; Das )Ende wird natürlich als Nebeneffekt der Art und Weise erzeugt, in der die Übergänge zwischen den verschiedenen Segmenten des Programms funktionieren. Daher wurde das (am Anfang manuell hinzugefügt, um es auszugleichen (und trotz der Länge des Kommentars ein Kommentar eingefügt) ()Da ein Befehl immer noch ein ()Befehl ist, wird lediglich 1 zum Rückgabewert des Datenstrings und seines Formatierers hinzugefügt (was von der for-Schleife vollständig ignoriert wird).

Insbesondere sind diese NUL-Zeichen zu Beginn des Kommentars eindeutig keine Offsets von irgendetwas (selbst der Unterschied zwischen +8 und -4 reicht nicht aus, um aus (einer NUL eine NUL zu machen). Das sind reine Auffüllungen, um den 239-Elemente-Datenstring auf 241 Elemente zu bringen (was sich leicht auszahlt: Es würde viel mehr als zwei Bytes erfordern, um 1 vs. 239 statt 1 vs. 241 zu generieren, wenn die Anzahl der erforderlichen Iterationen berechnet wird ). NUL wurde als Füllzeichen verwendet, da es den niedrigstmöglichen Codepunkt aufweist (wodurch der Quellcode für den Datenstring kürzer und damit schneller ausgegeben werden kann).

{}({}())

Löschen Sie das oberste Stapelelement (das von uns verwendete Format) und fügen Sie 1 zum nächsten hinzu (das letzte auszugebende Zeichen, dh das erste zu druckende Zeichen des gerade formatierten Programmabschnitts). Wir brauchen das alte Format nicht mehr (das neue Format versteckt sich auf dem Arbeitsstapel); und das Inkrement ist in den meisten Fällen harmlos und ändert das 'an einem Ende der Quellendarstellung des Datenzeichenfolge-Formatierers in ein ((was auf dem Stapel für das nächste Ausführen des Formatierers erforderlich ist, um die Datenzeichenfolge selbst zu formatieren). Wir brauchen eine Transformation wie diese im Outro oder Intro, weil das Erzwingen jedes Datenstring-Formatierungselements zu Beginn (etwas komplexer werden würde (da wir das schließen (und seinen Effekt später wieder rückgängig machen ), was undIrgendwie müssten (wir irgendwo ein Extra generieren, weil wir nur fast 241 Kopien des Formatierers haben, nicht alle 241 (also ist es am besten, dass ein harmloser Charakter wie 'derjenige fehlt).

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

Zum Schluss der Loop-Exit-Test. Der aktuelle Anfang des Hauptstapels ist das Format, das wir für die nächste Iteration benötigen (die gerade vom Arbeitsstapel zurückgekehrt ist). Dies kopiert es und fügt der Kopie 8 hinzu. Der resultierende Wert wird beim nächsten Mal in der Schleife verworfen. Wenn wir jedoch nur das Intro gedruckt haben, war der Versatz -4, sodass der Versatz für die "nächste Iteration" -8 ist. -8 + 8 ist 0, daher wird die Schleife beendet, anstatt danach mit der Iteration fortzufahren.

ais523s temporäres Konto
quelle
16

128.673.515 Zyklen

Probieren Sie es online aus

Erläuterung

Der Grund dafür, dass Miniflak-Quines zu langsam sind, ist der fehlende Direktzugriff von Miniflak. Um dies zu umgehen, erstelle ich einen Codeblock, der eine Zahl aufnimmt und ein Datum zurückgibt. Jedes Datum stellt wie zuvor ein einzelnes Zeichen dar und der Hauptcode fragt diesen Block einfach nach jeweils einem Zeichen ab. Dies funktioniert im Wesentlichen als Block eines Direktzugriffsspeichers.

Dieser Codeblock hat zwei Anforderungen.

  • Es muss eine Zahl sein und nur den Zeichencode für dieses Zeichen ausgeben

  • Es muss einfach sein, die Nachschlagetabelle Stück für Stück in Brain-Flak zu reproduzieren

Um diesen Block zu konstruieren, habe ich eine Methode aus meinem Beweis, dass Miniflak vollständig ist, wieder verwendet. Für jedes Datum gibt es einen Codeblock, der so aussieht:

(({}[()])[(())]()){(([({}{})]{}))}{}{(([({}{}(%s))]{}))}{}

Dies subtrahiert eins von der Zahl oben auf dem Stapel und wenn Null drückt %s das Datum darunter verschoben. Da jedes Stück die Größe um eins verringert, wenn Sie mit n auf dem Stapel beginnen, erhalten Sie das n-te Datum zurück.

Dies ist schön und modular, so dass es leicht von einem Programm geschrieben werden kann.

Als nächstes müssen wir die Maschine einrichten, die diesen Speicher tatsächlich in die Quelle übersetzt. Dies besteht aus 3 Teilen als solche:

(([()]())())
{({}[(
  -Look up table-
 )]{})
 1. (({}[()])[(())]()){(([({}{})]{}))}{}{([({}{}(([{}]))(()()()()()))]{})}{}

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

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

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

Die Maschine besteht aus vier Teilen, die in der Reihenfolge von 1 bis 3 abgearbeitet werden. Ich habe sie im obigen Code gekennzeichnet. Jeder Abschnitt verwendet auch dasselbe Lookup-Tabellenformat, das ich für die Codierung verwende. Dies liegt daran, dass das gesamte Programm in einer Schleife enthalten ist und wir nicht jedes Mal, wenn wir die Schleife durchlaufen, jeden Abschnitt ausführen möchten. Deshalb fügen wir dieselbe RA-Struktur ein und fragen den gewünschten Abschnitt jedes Mal ab.

1

Abschnitt 1 ist ein einfacher Einrichtungsabschnitt.

Das Programm teilt den ersten Abfragen Abschnitt 1 und Datum 0 mit. Datum 0 existiert nicht. Statt diesen Wert zurückzugeben, dekrementiert es die Abfrage einfach einmal für jedes Datum. Dies ist nützlich, da wir das Ergebnis verwenden können, um die Anzahl der Daten zu bestimmen, die in zukünftigen Abschnitten wichtig werden. Abschnitt 1 zeichnet die Anzahl der Daten auf, indem er das Ergebnis negiert und Abschnitt 2 und das letzte Datum abfragt. Das einzige Problem ist, dass wir Abschnitt 2 nicht direkt abfragen können. Da es noch eine Dekrementierung gibt, müssen wir einen nicht existierenden Abschnitt 5 abfragen. Dies ist in der Tat jedes Mal der Fall, wenn wir einen Abschnitt innerhalb eines anderen Abschnitts abfragen. Ich werde dies in meiner Erklärung ignorieren, aber wenn Sie einen Code suchen, denken Sie daran, dass 5 bedeutet, dass Sie einen Abschnitt zurückgehen, und 4 bedeutet, dass Sie denselben Abschnitt erneut ausführen.

2

Abschnitt 2 dekodiert die Daten in die Zeichen, die den Code nach dem Datenblock bilden. Jedes Mal, wenn erwartet wird, dass der Stapel so angezeigt wird:

Previous query
Result of query
Number of data
Junk we shouldn't touch...

Es ordnet jedes mögliche Ergebnis (eine Zahl von 1 bis 6) einem der sechs gültigen Miniflak-Zeichen ( (){}[]) zu und platziert es unter der Anzahl der Daten mit dem Zusatz "Junk, die wir nicht berühren sollten". Das bringt uns einen Stapel wie:

Previous query
Number of data
Junk we shouldn't touch...

Von hier aus müssen wir entweder das nächste Datum abfragen oder, wenn wir sie alle abgefragt haben, zu Abschnitt 3 übergehen. Bei der vorherigen Abfrage handelt es sich nicht um die exakte gesendete Abfrage, sondern um die Abfrage abzüglich der Anzahl der Daten im Block. Dies liegt daran, dass jedes Datum die Abfrage um eins dekrementiert, sodass die Abfrage ziemlich verstümmelt ausgegeben wird. Um die nächste Abfrage zu generieren, fügen wir eine Kopie der Anzahl der Daten hinzu und subtrahieren eine. Jetzt sieht unser Stack so aus:

Next query
Number of data
Junk we shouldn't touch...

Wenn unsere nächste Abfrage Null ist, haben wir den gesamten in Abschnitt 3 benötigten Speicher gelesen, fügen der Abfrage also die Anzahl der Daten erneut hinzu und legen eine 4 auf den Stapel, um zu Abschnitt 3 zu gelangen. Wenn die nächste Abfrage nicht Null ist, werden wir Lege eine 5 auf den Stapel, um Abschnitt 2 erneut auszuführen.

3

In Abschnitt 3 wird der Datenblock durch Abfragen des Arbeitsspeichers wie in Abschnitt 3 erstellt.

Der Kürze halber werde ich die meisten Details der Funktionsweise von Abschnitt 3 weglassen. Es ist fast identisch mit Abschnitt 2, mit der Ausnahme, dass anstatt jedes Datum in ein Zeichen zu übersetzen, jedes in einen langen Codeabschnitt übersetzt wird, der seinen Eintrag im RAM darstellt. Wenn Abschnitt 3 abgeschlossen ist, wird das Programm angewiesen, die Schleife zu verlassen.

Nachdem die Schleife ausgeführt wurde, muss das Programm nur das erste Bit der Quine verschieben ([()]())(()()()()){({}[(. Ich mache das mit dem folgenden Code, der Standard-Kolmogorov-Komplexitätstechniken implementiert.

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

Ich hoffe das war klar. Bitte kommentieren Sie, wenn Sie über irgendetwas verwirrt sind.

Weizen-Assistent
quelle
Wie lange dauert die Ausführung? Es läuft mal auf TIO.
Pavel
@Pavel Ich starte es nicht mit TIO, weil das unglaublich langsam wäre. Ich verwende denselben Interpreter wie TIO (den Ruby- Interpreter ). Das Ausführen auf einem alten Rack-Server, auf den ich Zugriff habe, dauert ungefähr 20 Minuten. Es dauert ungefähr 15 Minuten in Crain-Flak, aber Crain-Flak hat keine Debug-Flags, so dass ich es nicht bewerten kann, ohne es im Ruby-Interpreter auszuführen.
Weizen-Zauberer
@Pavel Ich habe es erneut ausgeführt und es zeitlich festgelegt. Die 30m45.284sFertigstellung auf einem eher Low-End-Server (etwa das Äquivalent eines durchschnittlichen modernen Desktops) mit dem Ruby-Interpreter war erforderlich.
Weizen-Assistent