Eine ausgeglichene Zeichenfolge ist eine Folge von Klammern, ()
sodass jede Klammer mit einer anderen übereinstimmen kann. Strenger sind dies die Zeichenketten, die von dieser Grammatik umspannt werden:
S → (S)S | ε
Wir können eine Zeichenfolge "von links" drehen, indem wir:
Alle Vorkommen von
(
und)
miteinander wechselnVerschieben von Zeichen von der Vorderseite der Zeichenfolge nach hinten, bis die Zeichenfolge wieder ausgeglichen ist.
Lass uns ein Beispiel machen.
Wir beginnen mit der ausgeglichenen Saite:
(()(())())
Wir tauschen dann die Parens um zu machen
))())(()((
Verschieben Sie dann die Zeichen von der Vorderseite der Zeichenfolge zur Rückseite der Zeichenfolge, bis die Zeichenfolge ausgeglichen ist.
))())(()((
)())(()(()
())(()(())
))(()(())(
)(()(())()
(()(())())
Das ist unser Ergebnis!
Beachten Sie, dass einige Zeichenfolgen auf mehrere Arten umgedreht werden können, z. B. die Zeichenfolge
(()())
Wenn umgekehrt, kann entweder sein:
()(())
oder
(())()
Jeder String hat jedoch mindestens eine Lösung .
Aufgabe
Schreiben Sie ein Programm, um eine ausgeglichene Zeichenfolge als Eingabe und Ausgabe zu verwenden. In Fällen, in denen es mehrere gültige Ausgaben geben kann, müssen Sie nur eine davon ausgeben. Sie können eine andere Klammer Typ verwenden ( <>
, []
oder {}
) , wenn Sie dies wünschen.
Da dies ein Code-Golf- Wettbewerb ist, sollten Sie versuchen, die Größe Ihres Quellcodes, gemessen in Bytes, zu minimieren.
Testfälle
(()()) -> ()(()), (())()
(()(())()) -> (()(())())
((())())() -> (()(()()))
quelle
Antworten:
Haskell ,
12412011911711311010910610510410198 Byte4 Bytes gespart dank bartavelle!
3 Bytes gespart dank Zgarb
1 Byte gespart dank Peter Taylor
Hier ist eine Lösung, die ich in Haskell ausgearbeitet habe. Es ist
jetzt in Ordnung,dank einiger Hilfe, die ich erhalten habe, ziemlich gut, aber ich versuche, dies zu verkürzen, daher sind Feedback / Vorschläge willkommen.Probieren Sie es online!
Erläuterung
Dieses Programm definiert 4 Funktionen, wobei die erste
(!)
bestimmt, ob eine Saite ausgeglichen ist. Es ist wie folgt definiert:Bei dieser Überprüfung wird angenommen, dass die Eingabe dank eines Vorschlags von Peter Taylor die gleiche Anzahl offener und geschlossener Parens aufweist.
Der nächste
g
dreht die Saite einmal.Dann haben wir,
d
was einfach ein Paren nimmt und es spiegeltEndlich haben wir die Funktion, mit der wir uns befassen. Hier verwenden wir eine punktfreie Darstellung von
until(!0)g
komponiert mitmap d
, died
auf die Eingabe abgebildet und angewendet wird ,g
bis das Ergebnis ausgeglichen ist. Dies ist der genaue Vorgang, der in der Frage beschrieben wird.quelle
g x@(a:b)|x!0=x|1>0=g$b++[a]
verschrotten und die Parens entfernend '('=')'
.d
verursacht einen Compilerfehler, glauben Sie mir, ich habe es versucht. Aber der erste Vorschlag ist willkommen. Vielen Dank!!
da Sie keine Fälle behandeln müssen, in denen die Zeichenfolge eine ungleiche Anzahl offener und geschlossener Klammern enthält. Sie können also die ersten beiden Fälle tauschen und haben_!1=1<0
[]!_=0<1
until
, um zu verkürzeng
: TIOd
Karte'('
an(-1)
und irgendetwas anderes anfertigt1
, und dann können die zwei längsten Fälle von!
zu kombiniert werden(i:a)!x=a!(x+i)
. Die Struktur der obersten Ebene muss dann überarbeitet werden, ummap d
dieuntil
Bedingung zu erfüllen, und ich muss rennen, damit ich jetzt keine Zeit habe, herauszufinden, welche Kombinatoren erforderlich sind, um alles zusammenzukleben.SOGL V0.12 ,
1211 BytesProbieren Sie es hier aus!
Erläuterung:
Hinweis:
l{
könnte durch ( für 10 Byte ersetzt werden, ist aber leider nicht implementiert.quelle
CJam (20 Zeichen)
Online-Demo
oder für die gleiche Zeichenanzahl
Online-Demo
Präparation
Die beiden Versionen haben eine gemeinsame Kopf- und Fußzeile
Dann berechnet das Bit in der Mitte offensichtlich, wie weit gedreht werden muss. Beide verwenden die Auswertung und sind darauf angewiesen
(
, der CJam-Dekrementierungsoperator und)
der Inkrementierungsoperator zu sein.vs
quelle
JavaScript (ES6),
111 bis105 Byte(2 Bytes gespart dank @CraigAyre, 2 Bytes dank @PeterTaylor, 2 Bytes dank @Shaggy.)
Ungolfed:
Testfälle:
Code-Snippet anzeigen
quelle
Netzhaut ,
4638 BytesProbieren Sie es online! Link enthält Testfälle. Bearbeiten: 8 Bytes mit Hilfe von @MartinEnder gespeichert. Die erste Stufe transponiert einfach die Klammern, während die zweite Stufe nach dem längsten Suffix sucht, bei dem es sich um ein gültiges ausgeglichenes Präfix handelt. Dies ist anscheinend eine ausreichende Bedingung, um die Rotation vollständig auszugleichen. Der Abgleich wird über Bilanzkreise ermittelt. Das Konstrukt
((\()|(?<-4>\)))+
entspricht einer beliebigen Anzahl von(
s plus einer beliebigen Anzahl von)
s, solange wir bereits (<-4>
) so viele(
s gesehen haben. Da wir nur nach einem gültigen Präfix suchen, müssen wir nicht mit den verbleibenden)
s übereinstimmen .quelle
((\()|(?<-2>\)))
. Aber Ihr Versuch inspiriert mich nur einen völlig neuen Ansatz zu finden, der zwei weitere spart:(?<-1>(\()*\))+
. Dies wird sich in Zukunft sicherlich als nützlich erweisen. Vielen Dank. :)(?<-1>(\()*\))+
überhaupt funktioniert, da sie vom1
Stapel zu springen scheint, bevor sie tatsächlich mit irgendetwas übereinstimmt ...\(*
.PHP,
110108 BytesLaufen Sie als Pipe mit
-nR
oder testen Sie es online .Nervenzusammenbruch
quelle
Python 3 ,
112103101 Bytes-2 Bytes dank @ Mr.Xcoder
Probieren Sie es online!
quelle
Oktave, 62 Bytes
Probieren Sie es online!
Eine Funktion, die die Zeichenfolge als Eingabe verwendet und alle Ergebnisse druckt.
Erläuterung:
quelle
Mathematica, 78 Bytes
quelle
JavaScript (ES6), 97 Byte
Arbeitet durch rekursives Drehen der Eingabezeichenfolge, bis die Transponierung ausgeglichen ist, und anschließendes Transponieren.
quelle
APL (Dyalog Unicode) ,
3530 BytesEin neuer Ansatz dank @ Adám
Probieren Sie es online!
Golfen ist im Gange.
Erläuterung
quelle
Python 2 , 99 Bytes
Probieren Sie es online!
In Funktionsform für einfache Testfälle:
Python 2 , 108 Bytes
Probieren Sie es online!
Dies verwendet einen etwas anderen Ansatz - anstatt den String rekursiv zu drehen, wenn wir die Parens als Inkrementieren und Dekrementieren eines Balance-Zählers betrachten, darf ein ausgeglichener String niemals eine Gesamtsumme von Inkrementen haben - Dekremente, die kleiner als 0 sind.
Also nehmen wir
Invertiere die Eltern:
und konvertiere es in eine Liste von Summen von Inkrementen / Dekrementen:
-3 ist das Minimum bei Index 4 (nullbasiert); also wollen wir uns um diesen Index + 1 verschieben. Dies garantiert, dass das kumulative Inkrement / Dekrement niemals kleiner als 0 ist; und wird zu 0 summieren.
quelle
r=0,
stattdessen tunr=[0]
?r+=[r[-1]+2*b-1]
mitr+=r[-1]+2*b-1,
als auchClojure, 118 Bytes
Gibt eine Folge von Zeichen zurück, also würde ich es so nennen:
Klammern werden zuerst umgedreht und dann wiederholt, solange die kumulative Summe der Klammernanzahl an einem bestimmten Punkt der Sequenz negativ wird.
quelle
Brainfuck , 82 Bytes
Probieren Sie es online!
Erläuterung
Mit jedem gelesenen Zeichen wird ein Zähler wie folgt geändert:
)
erhöht sich der Zähler um 1.(
Änderung verringert sich der Zähler um 1, es sei denn, der Zähler war 0. In diesem Fall bleibt der Zähler unverändert.Jedes Präfix ist genau dann ein gültiges Suffix eines ausgeglichenen Strings (nach der Inversion), wenn dieser Zähler 0 ist. Dieser Code verwendet das längste Präfix, um die Ausgabe zu bilden.
quelle