Blasen Sie die Klammern!

27

Auf dieser Site gibt es einige Fragen zum Ausgleichen von Klammern und zum Überprüfen, ob die Klammern ausgewogen sind. Ich schlage vor, es ist jetzt Zeit, diese ausgewogenen Klammern für etwas zu verwenden!

In Mathematik und Programmierung sind Klammern wie Blasen, die alles Innere von allem Äußeren isolieren, sodass alles, was drinnen ist, in Ruhe seine Sache tun kann und alles, was draußen ist, nur ein Objekt sieht. Eine Reihe von Klammern ist jedoch eindimensional, während Blasen gewöhnlich mindestens zweidimensional sind. Das bedeutet, dass sich Blasen frei bewegen können, solange sie sich nicht berühren oder sich zwischen der Innenseite und der Außenseite anderer Blasen kreuzen.

Herausforderung

Die Eingabe ist eine Zeichenfolge aus aufeinander abgestimmten Klammern eines einzelnen Typs, entweder rund (), quadratisch [], geschweift {}oder winklig <>. Es liegt an Ihnen, welche Art von Programm Sie akzeptieren möchten, und ein Programm, das nur eine einzige Art von Klammern akzeptiert, wird akzeptiert. (Imaginärer Bonus, wenn Ihr Programm einen von ihnen verarbeiten kann, massive imaginäre Bonuspunkte, wenn es alle in derselben Eingabe verarbeiten kann.) Die Eingabe darf nichts zwischen den Klammern enthalten, obwohl abschließende Leerzeichen zulässig sind.

Bei der Ausgabe handelt es sich um alle möglichen Reorganisationen (in beliebiger Reihenfolge und einschließlich der ursprünglichen Eingabe) derjenigen Klammern, die dieselbe Blasenkonfiguration ohne zwei identische Zeichenfolgen ergeben. Das heißt, bei einer Eingabe von ()()ist die Ausgabe auch gerecht ()(), obwohl es technisch gesehen zwei Blasen sind, die Plätze tauschen könnten. Für den massiven imaginären Bonus führt eine Eingabe des {}[]()Willens natürlich zu einer Ausgabe von 6 verschiedenen Elementen / Strings / Linien.

Zwei Blasenkonfigurationen sind "gleich", wenn Sie eine Blase in die andere verschieben können, ohne dass sich eine Blase von innen nach außen oder von außen nach innen kreuzt. Wenn Sie verschachtelte Klammern mit Bäumen vergleichen (jedes übereinstimmende Paar ist ein Knoten, und jedes übereinstimmende Paar innerhalb ist ein Unterknoten, und jedes übereinstimmende Paar innerhalb ist wieder ein Unterknoten usw.), werden die Unterknoten eines bestimmten Knotens sortiert Dann ist eine einzelne Konfiguration von Blasen ein Baum, in dem die Knoten ungeordnet sind.

Jedes vernünftige Ausgabeformat reicht aus, z. B. das Zurückgeben einer Liste von Zeichenfolgen oder einer Liste von Einzelzeichen oder einer einzelnen Zeichenfolge mit einer Art von Leerzeichen oder das Drucken in stdoutoder stderrmit einer Form von sichtbarem Leerzeichen (meistens Zeilenvorschub oder Leerzeichen) dazwischen jede Neuorganisation.

Nachgestellte Leerzeichen für jede Reorganisation sowie nachgestellte und vorangestellte Zeilen / leere Listenelemente vor und nach der eigentlichen Ausgabe sind zulässig. Sie sollten in Ihrer Ausgabe die gleichen Klammern verwenden, die Sie in Ihrer Eingabe akzeptieren. Abgesehen von den hier angegebenen Klammern, Zeilenumbrüchen und Leerzeichen und dem von Ihnen verwendeten Trennzeichen sollte nichts gedruckt werden (einschließlich unsichtbarer / Null-Zeichen).

Die Punktzahl ist die Anzahl der Bytes im Code. Die niedrigste Anzahl für jede Sprache gewinnt. Sie können feststellen, ob Sie einen imaginären Bonus erhalten, entweder regulär oder massiv, aber dies hat keinen Einfluss auf Ihre Punktzahl. Tatsächliche Boni sind zu schwer auszugleichen.

Input-Output-Beispiele

Beispiel 1:

Eingang:

()(())

Ausgabe:

()(())
(())()

Beispiel 2:

Eingang:

(()())()()

Ausgabe:

(()())()()
()(()())()
()()(()())

Beispiel 3:

Eingang:

(()(()))()

Ausgabe:

((())())()
()((())())
(()(()))()
()(()(()))
Arthur
quelle
Warum können wir nicht ((()))in Beispiel 1 kommen? oder ()()()? Es scheint, als ob Ihnen für jede Eingabe Permutationen fehlen.
Weizen-Zauberer
@ WheatWizard Das würde nicht die gleiche Konfiguration von Blasen ergeben: eine große Blase mit zwei leeren Blasen im Inneren.
Arthur
@ WheatWizard Soweit ich weiß, kann man keine Blase von innen nach außen oder umgekehrt ziehen.
Grzegorz Puławski
@ WheatWizard Ich habe eine kleine Erklärung hinzugefügt.
Arthur
7
Übrigens, Willkommen bei PPCG! Schöne erste Herausforderung!
Mr. Xcoder

Antworten:

4

CJam , 18 Bytes

{~{_{{B}%e!}&}:B~}

Probieren Sie es online!

-2 dank Business Cat .

Erhält Eingaben als Zeichenfolge, die nur enthält []. Gibt eine Liste mit Permutationen zurück (leere Listen sind die gleichen wie leere Zeichenfolgen in CJam, statt dass []Sie sie erhalten "").

Erik der Outgolfer
quelle
Warum ist die Ausgabe [][]nur für ""? - Sollte der Eingang in einem zusätzlichen Satz von enthalten sein []? Wenn ja, warum gibt es eine zusätzliche Menge von [](vielleicht?) Was ist die Ausgabe für das oben genannte Beispiel? In der Frage heißt es auch: "Sie sollten in Ihrer Ausgabe die gleichen Klammern verwenden, die Sie in Ihrer Eingabe akzeptieren. Abgesehen von den hier angegebenen Klammern, Zeilenumbrüchen und Leerzeichen und dem von Ihnen verwendeten Trennzeichen sollte nichts gedruckt werden." Ich bin mir nicht sicher, ob eine Mischung aus []und ""akzeptabel ist.
Jonathan Allan
@ JonathanAllan Ja, ich denke, Sie müssen [][]ein zusätzliches Paar beifügen []. Für die anderen bin ich mir nicht sicher, ob sie ungültig sind.
Erik der Outgolfer
Ich denke, Sie können _{{B}%e!}&anstelle von_!!{{B}%e!}*
Business Cat
@BusinessCat &Kurzschluss oder so?
Erik der Outgolfer
&Läuft den Block nur, wenn der andere Wert wahr ist
Business Cat
4

Haskell , 227 210 208 205 Bytes

import Data.List
l=last
a!x=init a++[l a++[x]]
h[]=[""]
h(x:y)=["("++z++")"++t|z<-v x,t<-h y]
g(a,r)x|x=='('=(a+1,l$(r++h[]):[r!x|a>0])|1>0=(a-1,l$r:[r!x|a>1])
v s=nub$h=<<(permutations.snd$foldl g(0,[])s)

Probieren Sie es online!

Dieser war hart!

Ein bisschen Golf gespielt

Zwei Bytes dank Laikoni gespart

Sparen Sie zwei Bytes dank Bruce Forte

Ich bin mir nicht sicher, ob das in jedem Fall funktioniert. Einige Erklärungen:

  • a!xfüge den String xder letzten Liste von Strings hinzu a(a ist vom Typ [[String]])

  • snd$foldl(\(a,r)x->if x=='('then(a+1,last$(r++[[]]):[r!x|a>0])else(a-1,last$r:[r!x|a>1])verwendet die kürzere Bedingung , um die einfache Idee auszudrücken: Teilen Sie einen String auf root )( s. ZB "(()(()))()"gibt ["()(())", ""].

  • Wir müssen jeden Teil der Teilung verarbeiten, dann alle Zeichenfolgen sammeln und verbinden, um die richtige Ausgabe zu erhalten:

    1. hVerarbeitet eine Teileliste: Sie gilt vfür den ersten Teil und kombiniert das Ergebnis mit dem Prozess der übrigen Teile.

    2. v aggregiert die Ergebnisse für jede Permutation der Teile und entfernt die Duplikate.

Um eine umfassendere Ansicht hinzuzufügen: Sie haben im Grunde einen Baum (keinen binären) mit leeren Knoten. Urlaub sind (). Sie müssen für jeden Knoten alle Permutationen der Zweige erzeugen, dürfen jedoch keinen Zweig von einem Knoten nehmen und auf einen anderen Knoten legen. Ich habe eine Art Tiefensuche durchgeführt.

jferard
quelle
Sie können die Klammern herum fallen lassen init a.
Laikoni
2

Python 2, 353 350 331 Bytes

s=input()
f=lambda i,t=0:i+1if t<0else f(i+1,t-1)if"("<s[i+1]else f(i+1,t+1)
c=[(x,f(x))for x in range(len(s))if")">s[x]]
p=lambda l:[[]]if len(l)<1else[x for y in p(l[1:])for x in[y[:i]+[l[0]]+y[i:]for i in range(len(y)+1)]]
print[''.join(x)for x in p([s[c[x][0]:c[x][1]]for x in range(len(c))if all(c[x][1]>y[1]for y in c[:x])])]

Erhält den String ()als Eingabe und druckt das Ergebnis.

Probieren Sie es hier aus!

Ich habe es vermieden, itertools.permutationsmit Hilfe von Paolo die Antwort auf diese Frage zu verwenden .

Vielen Dank an Business Cat für das Auffinden von 3 Bytes und an Mr. Xcoder für unglaubliche 19 Bytes!

Erläuterung

  1. Erstellen Sie eine Liste von Tupeln der Indizes jedes ()Paars in der Eingabezeichenfolge.
  2. Löschen Sie alle Tupel aus der Liste, die von einem anderen ()Paar umgeben sind.
  3. Schneiden Sie die Zeichenfolge an den Indizes der verbleibenden Tupel.
  4. Erstellen Sie eine Liste aller Permutationen der Liste der Slices.
  5. Treten Sie der Liste mit einer neuen Zeile zum Drucken bei.
Lösung
quelle
Ich sehe ein paar Bytes, die rasiert werden könnten. Sie haben einige Leerzeichen, die entfernt werden können, und zwar nach printund an Stellen wie i+1 if(könnte i+1if). Auch an einer Stelle, die Sie haben y[0:i], können Sie die 0 weglassen.
Business Cat
Vielen Dank, @BusinessCat! Meine IDE beklagt sich über einige davon, deshalb lerne ich immer noch einige der Code-Golf-Tricks.
Auflösung
342 Bytes (-8 Bytes), indem einige Bedingungen neu angeordnet werden, um Leerzeichen zu entfernen.
Mr. Xcoder
340 Bytes (-10 Bytes) unter Verwendung eines lexikografischen Vergleichs über die Gleichheitsprüfung.
Mr. Xcoder
331 Bytes (-19 Bytes), da die Abfrage die Rückgabe einer Liste von Strings ermöglicht. Ja, wir haben Mathematica geschlagen :-)
Mr. Xcoder
2

JavaScript (Firefox 30-57), 222 Byte

s=>(g=a=>a+a?[for(x of g(a[0]))for(y of a.keys())for(z of g(a.slice(1)))(z.splice(y,0,x),z)]:[a])(eval(`[${s.replace(/]\[/g,`],[`)}]`)).map(g=a=>`[`+a.map(g).join``+`]`).sort().filter(s=>t<(t=s),t=``).map(s=>s.slice(1,-1))

Nimmt []Saiten. Erläuterung:

s=>(                                Inner function to permute an array
 g=a=>a+a?[                         If array is not empty
  for(x of g(a[0]))                 Permute the first element of the array
  for(y of a.keys())                Generate a list of insertion points
  for(z of g(a.slice(1)))           Permute the rest of the array
  (z.splice(y,0,x),z)]:             Make all possible permutations
  [a]                               Otherwise return a list of an empty array
)(eval(`[${                         Convert the string to a nested array
   s.replace(/]\[/g,`],[`)}]`)      ... inserting commas where necessary
).map(                              Process the results
 g=a=>`[`+a.map(g).join``+`]`       Recursively convert back to string
).sort().filter(s=>t<(t=s),t=``     Check for duplicates
).map(s=>s.slice(1,-1))             Remove outer `[]`s
Neil
quelle
0

Mathematica, 337 Bytes

Nicht um Code-Golf-Punkte zu bekommen, sondern um die Verwendung von Permutationsund Distributein diesem Problem zu zeigen . Es kann jedoch bessere Ansätze geben.

( seq: Sequenz alt,: Alternativen)

SetAttributes[alt, {Flat, OneIdentity}]
StringTake[
  StringReplace[ToString[
    ToExpression["{" <> StringReplace[#, "}{" -> "},{"] <> "}"]
        /. List -> Permutations@*seq
       /. List -> alt
      /. seq -> (Distribute[seq@##, alt] &)
     /. {seq -> List, alt -> Alternatives}],
   {", " -> "", "} | {" -> "\n"}],
  {2, -2}] &

Nehmen Sie die Eingabe in geschweiften Klammern {und als Zeichenfolge }. Ausgabe eines mehrzeiligen Strings.

user202729
quelle