Füllen Sie die Klammern aus

18

Normale Klammern ( (), [], <>und {}) sind schön und eindeutig sein , aber jemand dachte , dass es eine gute Idee wäre , nicht Klammerzeichen wie Klammern zu verwenden. Diese Zeichen |und "sind nicht eindeutig. Zum Beispiel tut

""""

entsprechen

(())

oder

()()

Es ist unmöglich zu sagen.

Interessant wird es zum Beispiel, wenn Sie Typen von mehrdeutigen Klammern mischen

"|""||""|"

Könnte eine der folgenden sein

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

Aufgabe

Ihre Aufgabe ist es, eine Zeichenfolge aus mehrdeutigen Zeichen zu erstellen und alle möglichen ausgewogenen Zeichenfolgen auszugeben, die der Autor beabsichtigt haben könnte.

Genauer gesagt, Sie geben alle ausgewogenen Saiten aus, die |durch entweder [oder ]und "durch entweder (oder ersetzt werden können ). Sie sollten keine symmetrische Zeichenfolge zweimal ausgeben.

IO

Als Eingabe sollte ein String aus |und verwendet werden ". Wenn Sie zwei verschiedene Zeichen als |und "als Ersatz auswählen möchten, können Sie dies tun. Sie sollten einen Container mit ausgeglichenen Zeichenfolgen ausgeben. Sie können wählen, ersetzen []und ()in der Ausgabe mit irgendwelchen anderen beiden Bügelpaare ( (), [], <>oder {}) Sie möchten. Ihr Ausgabeformat sollte über mehrere Läufe hinweg konsistent sein.

Wertung

Dies ist daher werden die Antworten in Bytes bewertet, wobei weniger Bytes besser sind.

Testfälle

"" -> ["()"]
"|"| -> []
||| -> []
"""" -> ["(())","()()"]
""|| -> ["()[]"]
"|"||"|" -> ["([([])])"]    
"|""||""|" -> ["([(([]))])","([()[]()])","([()][()])"]    
Weizen-Assistent
quelle
4
wartet auf eine BrainFlak-Antwort
caird coinheringaahing
Können wir ganze Zahlen anstelle von Zeichenfolgen verwenden? Was ist mit Listen von Ziffern oder ganzen Zahlen?
Zgarb
@ Zgarb Sicher ist das in Ordnung
Weizen-Assistent

Antworten:

7

Python 2 , 135 Bytes

s=input()
for k in range(2**len(s)):
 try:c=''.join("[]() , ,"[int(c)|k>>i&1::4]for i,c in enumerate(s));eval(c);print c[::2]
 except:0

Probieren Sie es online!

Erwartet Eingaben wie 2002anstelle von "||"und in Anführungszeichen.

Durchläuft alle 2 N möglichen Zuweisungen von "open" und "close" für die Zeichenfolge und erstellt Zeichenfolgen cwie:

"( [ ( ),],[ ( ),],),( ),"

Wenn evaldiese Zeichenfolge eine Ausnahme auslöst, ist die Übereinstimmung nicht gegeben. Wenn nicht, drucken wir c[::2]und geben:

([()][()])()
Lynn
quelle
6

Netzhaut , 59 56 55 Bytes

0`"
<$%">
}0`'
{$%"}
.+
$&_$&
+m`^_|(<>|{})(?=.*_)

A`_

Probieren Sie es online! Leider übertrifft das Testen von zwei Sätzen übereinstimmender Klammern die Leistung eines einzelnen .NET-Regex, sodass 15 Byte für die manuelle Prüfung eingespart werden. Bearbeiten: 3 4 Bytes dank @ H.PWiz gespeichert. Erläuterung:

0`"
<$%">

Suchen Sie a "und machen Sie zwei Kopien der Zeile, eine mit a <und eine mit a >. Führen Sie dies nacheinander durch ", sodass sich "die Anzahl der Zeilen jeweils verdoppelt.

}0`'
{$%"}

Ähnlich mit ', {und }. Ersetzen Sie dann so lange, bis alle "s und 's auf allen Kopien ersetzt wurden.

.+
$&_$&

Machen Sie ein Duplikat der Klammern, getrennt durch ein _.

+m`^_|(<>|{})(?=.*_)

Löschen Sie im Duplikat wiederholt übereinstimmende Klammern, bis keine mehr vorhanden sind. Löschen Sie in diesem Fall auch die Klammern _.

A`_

Löschen Sie alle Zeilen mit einem _.

Retina , 74 71 70 Bytes

0`"
<$%">
}0`'
{$%"}
Lm`^(.(?<=(?=\3)(<.*>|{.*}))(?<-3>)|(.))+(?(3)_)$

Probieren Sie es online! Erläuterung: Die ersten beiden Stufen sind wie oben. In der dritten Stufe wird das Ergebnis des Abgleichs zweier Sätze übereinstimmender Klammern direkt gedruckt. Hierbei werden die Bilanzkreise von .NET verwendet. In jeder Phase des Spiels versucht der Regex, einem Charakter zu entsprechen, sucht dann nach einem Paar übereinstimmender Klammern und prüft, ob die Oberseite des Stapels mit der offenen Klammer übereinstimmt. Wenn dies möglich ist, wird die Klammer ausgeglichen, und die offene Klammer wird vom Stapel genommen. Ansonsten wird davon ausgegangen, dass wir uns an einer offenen Klammer befinden, die auf den Stapel geschoben werden muss. Wenn diese Annahmen nicht zutreffen, ist der Stapel am Ende nicht leer und die Übereinstimmung schlägt fehl.

Alternativer Ansatz, auch 74 71 Bytes:

Lm`^((?=(<.*>|{.*})(?<=(.))).|\3(?<-3>))+(?(3)_)$

Hier schauen wir voraus entweder <... >oder {... }, dann schauen Sie hinter die schieben Schließbügel auf den Stapel. Andernfalls müssen wir die zuvor erfasste schließende Klammer abgleichen und platzieren. In dieser Version schafft es der Regex möglicherweise nicht einmal bis zum Ende der Zeichenfolge, aber einige Zeichenfolgen, wie z. B. <<<>, rutschen durch das Netz, wenn wir nicht nach einem leeren Stapel suchen.

Neil
quelle
1
Sie können einige Bytes beim
Escape-Vorgang
@ H.PWiz Ah, ich muss das bisschen über die Verwendung alternativer Klammerpaare übersehen haben, danke!
Neil
Sie können auch |in der Eingabe ändern
H.PWiz
2

Schale , 19 Bytes

fo¬ω`ḞoΣx½¨÷₂¨ΠmSe→

Probieren Sie es online! Verwendet die Zeichen dsin der Eingabe sowie die entsprechenden Klammerpaare deund stin der Ausgabe.

Erläuterung

Die Idee ist, alle möglichen Klammern der Eingabe zu generieren und diejenigen zu behalten, die sich auf die leere Zeichenfolge reduzieren, wenn wir wiederholt benachbarte Klammern entfernen. Dies ¨÷₂¨ist eine komprimierte Zeichenfolge, in "dest"die expandiert wird und die ausgewählt wurde, weil sie eine kurze komprimierte Form hat und aus Zeichenpaaren mit benachbarten Codepunkten besteht. Somit entspricht das Programm dem Folgenden.

fo¬ω`ḞoΣx½"dest"ΠmSe→  Implicit input, say "ddssdd".
                 m     Map over the string:
                  Se    pair character with
                    →   its successor.
                       Result: ["de","de","st","st","de","de"]
                Π      Cartesian product: ["ddssdd","ddssde",..,"eettee"]
f                      Keep those strings that satisfy this:
                        Consider argument x = "ddsted".
   ω                    Iterate on x until fixed:
         ½"dest"         Split "dest" into two: ["de","st"]
    `Ḟ                   Thread through this list (call the element y):
        x                 Split x on occurrences of y,
      oΣ                  then concatenate.
                          This is done for both "de" and "st" in order.
                        Result is "dd".
 o¬                    Is it empty? No, so "ddsted" is not kept.
                      Result is ["destde","ddstee"], print implicitly on separate lines.
Zgarb
quelle
2

Perl, 56 55 53 Bytes

Enthält +1fürn

verwendet [für []und {für{}

perl -nE 's%.%"#1$&,+\\$&}"^Xm.v6%eg;eval&&y/+//d+say for< $_>' <<< "[{[[{{[[{["

Generiert alle 2 ^ N-Möglichkeiten und evalprüft dann mithilfe von Perl , ob ein String wie '+ [+ {}]' ein gültiger Code ist. Wenn dies der +Fall ist, wird das Ergebnis entfernt und gedruckt

Tonne Hospel
quelle
1

Sauber , 203 186 179 Bytes

?['(':l][')':t]= ?l t
?['[':l][']':t]= ?l t
?l[h:t]= ?[h:l]t
?[][]=True
?_ _=False
@['"']=[['('],[')']]
@['|']=[['['],[']']]
@[h:t]=[[p:s]\\[p]<- @[h],s<- @t]
$s=[k\\k<- @s| ?[]k]

Probieren Sie es online!

Verwendet nur Mustererkennung und Verstehen.

Οurous
quelle
1

Perl, 56 Bytes

Beinhaltet +fürn

Verwendet die Eingabe [für die Ausgabe[oder]

Verwendet Input {für Output {oder}

perl -nE '/^((.)(?{$^R.$2})(?1)*\2(?{$^R.=$2^v6}))*$(?{say$^R})^/' <<< "[{[[{{[[{["

Verwendet einen erweiterten Perl-Regex, um die Klammern anzupassen und die während der Rückverfolgung getroffenen Entscheidungen zu verfolgen. Dies kann sehr viel effizienter sein, als alle 2 ^ N Kandidaten zu generieren, da bereits viele unmögliche Zuweisungen auf halbem Weg durch die Eingabezeichenfolge zurückgewiesen werden

Tonne Hospel
quelle
0

Kotlin , 240 236 234 Bytes

fold(listOf("")){r,c->r.flatMap{i->when(c){'"'->"()".map{i+it}
else->"[]".map{i+it}}}}.filter{val d=ArrayList<Char>()
it.all{fun f(c:Any)=d.size>1&&d.removeAt(0)==c
when(it){')'->f('(')
']'->f('[')
else->{d.add(0,it);1>0}}}&&d.size<1}

Verschönert

    fold(listOf("")) {r,c ->
        r.flatMap {i-> when(c) {
            '"'-> "()".map {i+it}
            else -> "[]".map {i+it}
        }}
    }.filter {
        val d = ArrayList<Char>()
        it.all {
            fun f(c:Any)=d.size>1&&d.removeAt(0)==c
            when(it) {
                ')' -> f('(')
                ']' -> f('[')
                else -> {d.add(0,it);1>0}
            }
        } && d.size<1
    }

Prüfung

private fun String.f(): List<String> =
fold(listOf("")){r,c->r.flatMap{i->when(c){'"'->"()".map{i+it}
else->"[]".map{i+it}}}}.filter{val d=ArrayList<Char>()
it.all{fun f(c:Any)=d.size>1&&d.removeAt(0)==c
when(it){')'->f('(')
']'->f('[')
else->{d.add(0,it);1>0}}}&&d.size<1}

data class Test(val input: String, val outputs: List<String>)

val tests = listOf(
    Test("""""""", listOf("()")),
    Test(""""|"|""", listOf()),
    Test("""|||""", listOf()),
    Test("""""""""", listOf("(())","()()")),
    Test("""""||""", listOf("()[]")),
    Test(""""|"||"|"""", listOf("([([])])")),
    Test(""""|""||""|"""", listOf("([(([]))])","([()[]()])","([()][()])"))
)

fun main(args: Array<String>) {
    for ((input, output) in tests) {
        val actual = input.f().sorted()
        val expected = output.sorted()
        if (actual != expected) {
            throw AssertionError("Wrong answer: $input -> $actual | $expected")
        }
    }

Bearbeitungen

  • -4 jrtapsell - Überarbeitetes Überprüfungsprädikat
  • -2 jrtapsell - true-> 1>0und == 0->< 1
jrtapsell
quelle
0

C (gcc) , 315 Bytes

j,b;B(char*S){char*s=calloc(strlen(S)+2,b=1)+1;for(j=0;S[j];b*=(S[j]<62||*--s==60)*(S[j++]-41||*--s==40))S[j]==60?*s++=60:0,S[j]<41?*s++=40:0;return*s>0&*--s<1&b;}f(S,n,k)char*S;{if(n<strlen(S))for(k=2;k--;)S[n]==46-k-k?S[n]=40+k*20,f(S,n+1),S[n]=41+k*21,f(S,-~n),S[n]=46-k-k:0;else B(S)&&puts(S);}F(int*S){f(S,0);}

Probieren Sie es online!


C (gcc) , 334 Bytes (alte Version)

j,b;B(char*S){char*s=calloc(strlen(S)+2,1)+1;for(b=1,j=0;S[j];j++){if(S[j]==60)*s++=60;if(S[j]<41)*s++=40;b*=!(S[j]>61&&*--s!=60)*!(S[j]==41&&*--s!=40);}return*s>0&*--s<1&b;}f(S,n,k)char*S;{if(n>=strlen(S))return B(S)&&puts(S);for(k=0;k<2;k++)S[n]==46-k-k&&(S[n]=40+k*20,f(S,n+1),S[n]=41+k*21,f(S,-~n),S[n]=46-k-k);}F(char*S){f(S,0);}

Probieren Sie es online!


Erklärung (alte Version)

j,b;B(char*S){                   // determine if string is balanced
 char*s=calloc(strlen(S)+2,1)+1; // array to store matching brackets
 for(b=1,j=0;S[j];j++){          // loop through string (character array)
  if(S[j]==60)*s++=60;           // 60 == '<', opening bracket
  if(S[j]<41)*s++=40;            // 40 == '(', opening bracket
  b*=!(S[j]>61&&*--s!=60)*       // 62 == '>', closing bracket
   !(S[j]==41&&*--s!=40);}       // 41 == ')', closing bracket
 return*s>0&*--s<1&b;}           // no unmatched brackets and no brackets left to match
f(S,n,k)char*S;{                 // helper function, recursively guesses brackets
 if(n>=strlen(S))                // string replaced by possible bracket layout
  return B(S)&&puts(S);          // print if balanced, return in all cases
 for(k=0;k<2;k++)                // 46 == '.', guess 40 == '(',
  S[n]==46-k-k&&(S[n]=40+k*20,   //  guess 41 == '(', restore
   f(S,n+1),S[n]=41+k*21,        // 44 == ',', guess 60 == '<',
   f(S,-~n),S[n]=46-k-k);}       //  guess 62 == '>', restore
F(char*S){f(S,0);}               // main function, call helper function

Probieren Sie es online!

Jonathan Frech
quelle
Können Sie keine Arrays mit variabler Länge von GCC verwenden, um das Calloc loszuwerden?
Ton Hospel
@TonHospel Ich müsste dann aber entweder das Array in einen Zeiger konvertieren oder eine andere Indexvariable einführen, die ich nicht weiß, ob sie es wert ist, da ich *s++an einigen Stellen verwende.
Jonathan Frech
char S[n],*s=Sist noch kürzer alschars*s=calloc(n,1)
Ton Hospel
@TonHospel Ich weiß nicht wirklich warum, obwohl es nicht zu funktionieren scheint .
Jonathan Frech
@ceilingcat Vielen Dank.
Jonathan Frech