Diese Challenge wurde im Rahmen der LotM-Challenge im April 2018 sowie zum 2. Geburtstag von Brain-Flak veröffentlicht
Ich dachte darüber nach, wie man Brain-Flak-Programme am effizientesten codieren könnte. Da es nur 8 gültige Zeichen gibt, ist es naheliegend, jedes Zeichen einer 3-Bit-Sequenz zuzuordnen. Dies ist sicherlich sehr effektiv, aber es ist immer noch sehr redundant. Es gibt einige Funktionen von Brain-Flak-Code, die wir nutzen könnten, um die Codierung zu verkürzen.
Die Nullen, die alle durch 2 übereinstimmende Klammern dargestellt werden, fungieren tatsächlich als einzelne Informationseinheit anstatt als 2. Wenn wir jede Klammer durch ein einzelnes Byte-Zeichen ersetzen, würden die Codierungen viel kleiner, ohne dass Daten verloren gehen.
Dieser ist weniger offensichtlich, aber die abschließenden Bytes der Monaden sind auch redundant. Denken Sie, Sie könnten erraten, was die
'?'
Zeichen im folgenden Ausschnitt darstellen?{(({}?<>?<>?
Wenn wir davon ausgehen, dass die Eingabe ein gültiger Brain-Flak-Code ist, gibt es für jedes dieser Fragezeichen nur eine Option. Dies bedeutet, dass wir eindeutig ein enges Monadenzeichen verwenden können, um jede schließende Klammer darzustellen. Dies hat den zusätzlichen Vorteil, dass der Zeichensatz klein gehalten wird, was sehr hilfreich wäre, wenn wir eine Huffman-Codierung verwenden möchten. Da das enge Monadenzeichen mit großer Wahrscheinlichkeit das am häufigsten vorkommende Zeichen ist, könnte es durch ein einzelnes Bit dargestellt werden, was äußerst effizient ist.
Mit diesen beiden Tricks können wir Brain-Flak-Code mithilfe des folgenden Algorithmus komprimieren:
Ersetzen Sie jede schließende Klammer einer Monade durch
|
. Oder mit anderen Worten, ersetzen Sie jede schließende Klammer, der kein Eröffnungsspiel vorausgeht, durch einen Balken. So...(({})<(()()())>{})
würde werden
(({}|<(()()()||{}|
Ersetzen Sie jeden Nilad mit seiner schließenden Klammer. Daher verwenden übereinstimmende Klammern, in denen sich nichts befindet, die folgende Zuordnung:
() --> ) {} --> } [] --> ] <> --> >
Jetzt lautet unser letztes Beispiel:
((}|<()))||}|
Entfernen Sie nachfolgende
|
Zeichen. Da wir wissen, dass die Gesamtzahl der Balken der Gesamtzahl der({[<
Zeichen entsprechen sollte, können wir auf fehlende Balken am Ende schließen. Also ein Beispiel wie:({({})({}[()])})
würde werden
({(}|(}[)
Ihre Herausforderung für heute ist es, diesen Prozess umzukehren.
(){}[]<>|
Erweitern Sie eine Zeichenfolge aus komprimiertem Brain-Flak, die nur die Zeichen enthält , in den ursprünglichen Brain-Flak-Code. Sie können davon ausgehen, dass die Eingabe immer zu gültigem Brain-Flak erweitert wird. Dies bedeutet, dass kein Präfix der Eingabe mehr |
als ({[<
Zeichen enthält.
Die Eingabe enthält keine nachgestellten |
Zeichen. Diese müssen aus dem Kontext abgeleitet werden.
Wie üblich können Sie entweder ein vollständiges Programm oder eine Funktion einreichen, und Eingabe- / Ausgabeformate sind zulässig. Und da dies ein Code-Golf ist , wird Ihr Code durch die Länge des Quellcodes in Bytes bewertet. Je kleiner die Punktzahl, desto besser.
Testfälle
Hier sind einige Testfälle. Wenn Sie mehr möchten, können Sie mit diesem Python-Skript und dem Brain-Flak-Wiki , aus dem die meisten dieser Testfälle stammen , Ihre eigenen Testfälle generieren .
#Compressed code
#Original code
())))
(()()()())
([([}()||||(>||{(})|>|}{((<}|||>}|}>}
([([{}(())])](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}
({(}|(}[)|||}
({({})({}[()])}{})
(((()))||(](((}}||(}([(((}))||||(]((}}|}|}}|||]||]|[))||(}))|}(}|(}]]|}
((((()()()))([]((({}{}))({}([((({}()())))]([](({}{}){}){}{})))[]))[])[()()])({}()()){}({})({}[][]){}
quelle
Antworten:
Brain-Flak ,
952 916818 Bytes360 Bytes gespart, indem entgegengesetzte Klammern relativ und nicht von Grund auf neu berechnet werden (zB
')'
='(' + 1
statt(((5 * 2) * 2) * 2) + 1
)34 Bytes mit einigen direkten Ersetzungen von DJMcMayhem gespeichert
10 Byte durch Überlappung des
>]}
Bearbeitungscodes eingespart118 Bytes durch Deduplizieren von Rollen eingespart
40 Bytes gespart, indem der leere Stapel genutzt wird, um die erste Rolle zu vereinfachen
Durch Markieren von EOF mit -1 wurden 48 Bytes gespart, was einen präziseren Rollcode ermöglicht
36 Bytes gespart durch Verwendung der " stock equals" -Logik anstelle meiner eigenen
98 Bytes gespart, da Jo King eine effizientere Methode zum Erstellen der Ausgabe gefunden hat
Probieren Sie es online!
Das erste Mal Golf spielen in Brain-Flak, also gibt es wahrscheinlich einige wirklich große Verbesserungen, aber es funktioniert. Viel Kopieren / Einfügen für jeden Bracket-Typ und groß dank des automatischen Ganzzahlgenerators und des Roll-Snippets von hier .
Erklärung hier , TIO formatiert es einfacher
Bonusantwort:
Komprimiertes Brain-Flak 583 Bytes
Probieren Sie es online!
(Beachten Sie, dass der obige Link nicht funktioniert, da TIO keinen Compressed Brain-Flak-Interpreter hat. Einen Transpiler für Brain-Flak finden Sie hier. )
Ich habe überprüft, ob dies gültig ist, indem ich mit diesem Tool auf Brain-Flak transpiliere. Es ist jetzt so effizient, dass ein Timeout unwahrscheinlich ist.
quelle
<>(<()>)
mit(<>)
. Sie können auch(<>{}<>)(<()>)
zu(<(<>{}<>)>)
Retina 0.8.2 ,
10398 BytesProbieren Sie es online! Link enthält Testfälle. Bearbeiten: 5 Bytes mit Inspiration von @MartinEnder gespeichert. Erläuterung:
Setzen Sie
;
nach jeder schließenden Klammer ein und ändern Sie alle Klammern in offene Klammern. Ändern Sie auch das|
s in;
s.Zählen Sie die Anzahl nicht übereinstimmender offener Klammern und addieren Sie diese Anzahl
;
s.Kopieren Sie jede öffnende Klammer in die entsprechende
;
.Klappen Sie die kopierten Klammern um und löschen Sie die
;
s.quelle
|
in etwas wie übersetzen!
. Es wäre nicht einmal Bytes kosten , wenn Sie übersetzen>-}
zu<-{
(was meiner Meinung nach gibtz
für|
).z
aber ich habe mir trotzdem eine Möglichkeit ausgedacht, ein paar Bytes mehr zu sparen.TIS ,
670666 Bytes-4 Bytes für den Sprung vorwärts, um zurückzuspringen
Code:
Layout:
Probieren Sie es online!
Ich bezweifle, dass dies das kleinste ist, aber ich sehe keinen Weg, es kleiner zu machen. Leider
NOP
scheinen alle s für das Timing notwendig zu sein, und ich kann den Stack nicht dort platzieren, wo er sich@14
gerade befindet, da von dort eingelesenANY
wurde@11
.Die Struktur dieser Lösung ist wie folgt:
Wenn eine offene Klammer angezeigt wird, wird die offene Klammer entlang der linken Spalte gesendet, um ausgegeben zu werden, und die schließende Klammer wird entlang der rechten Spalte an den Stapel gesendet.
Wenn eine schließende Klammer angezeigt wird, werden sowohl das Öffnen als auch das Schließen entlang der linken Spalte gesendet, um ausgegeben zu werden.
Beim Erkennen einer Pipe wird der Stapel abgelegt und an die Ausgabe gesendet.
Bei EOF
@1
wird@2
anstelle des Eingabestreams von mit dem Lesen von begonnen@0
.@2
erzeugt einen endlosen Strom von Rohren, so dass der Stapel abgelassen wird.Sobald sowohl die Eingabe als auch der Stapel erschöpft sind, wird das Programm angehalten.
Warnung: Aufgrund der Einschränkungen von TIS ist die Stapelgröße auf 15 begrenzt. Wenn etwas tiefer verschachtelt ist, führt diese Implementierung zu einem falschen Ergebnis.
quelle
JavaScript (ES6), 107 Byte
Nimmt die Eingabe als Array von Zeichen. Gibt eine Zeichenfolge zurück.
Probieren Sie es online!
quelle
Haskell,
127121 BytesProbieren Sie es online!
Bearbeiten Sie: -6 Bytes, indem Sie die @ Laikoni- Funktion verwenden, um die passende Klammer zu finden .
quelle
Rubin , 104 Bytes
Dies ist ein vollständiges Programm, das auf der Konsole ausgegeben wird.
(i<5?a:$>)<<r[-i]
muss einer der coolsten Golfplätze sein, die ich je gemacht habe.Probieren Sie es online!
Rubin , 106 Bytes
Dies ist meine erste Lösung. Eine anonyme Lambda-Funktion, die Zeichenfolgen akzeptiert und zurückgibt.
Probieren Sie es online!
quelle
Brain-Flak ,
606 548 496 418 394390 BytesProbieren Sie es online!
Ich habe dies damit begonnen, dass ich Kamil Drakaris Antwort golfen habe , aber sie ist mir bis zu dem Punkt entgangen , an dem ich beschlossen habe, sie als separate Antwort zu veröffentlichen.
Erläuterung:
Und natürlich...
Komprimierte Gehirnflocken, 285 Bytes:
quelle
Java 10, 424 Bytes
Es ist etwas langwierig, aber ich konnte nicht herausfinden, wie ich es weiter verkürzen kann. Dies ist jedoch eine schöne Herausforderung.
Probieren Sie es hier online aus .
Ungolfed-Version:
quelle
Python 2,
188184180177174173 Bytes4 Bytes gespart dank DJMcMayhem.
Probieren Sie es online!
quelle
s
es leer ist. Andernfalls befinden sich die zusätzlichen Zeichen am falschen Ende.Python 3 , 122 Bytes
Probieren Sie es online!
quelle
Haskell , 152 Bytes
Probieren Sie es online! oder überprüfen Sie alle Testfälle .
p
Implementiert einen rekursiven Parser, der für die einfache Grammatik möglicherweise überflüssig ist.quelle
m
, um die passende Halterung zu finden.Python 2 , 244 Bytes
Probieren Sie es online!
Es dauerte weit mehr als ein oder zwei Stunden, um das zum Laufen zu bringen ...
quelle