Generiere alle Brain-Flak-Schnipsel

14

Diese Frage ist die zweite von mehreren Brain-Flak-Geburtstagsherausforderungen, mit denen Brain-Flaks erster Geburtstag gefeiert werden soll! Weitere Informationen zu Brain-Flaks Geburtstag finden Sie hier

Herausforderung

Für diese Herausforderung generieren Sie alle vollständig übereinstimmenden Zeichenfolgen aus einer Liste von Klammern. So leihen Sie die Definition von DJMcMayhem für eine vollständig übereinstimmende Zeichenfolge aus:

  • Für die Zwecke dieser Herausforderung ist eine „Klammer“ eines dieser Zeichen: ()[]{}<>.

  • Ein Klammerpaar wird als "übereinstimmend" betrachtet, wenn die öffnende und schließende Klammer in der richtigen Reihenfolge sind und keine Zeichen enthalten, z

    ()
    []{}
    

    Oder wenn jedes Unterelement in ihm auch übereinstimmt.

    [()()()()]
    {<[]>}
    (()())
    

    Unterelemente können auch mehrere Ebenen tief verschachtelt sein.

    [(){<><>[()]}<>()]
    <[{((()))}]>
    
  • Eine Zeichenfolge wird nur dann als "vollständig passend" betrachtet, wenn jedes Paar von Klammern die richtige öffnende und schließende Klammer in der richtigen Reihenfolge aufweist.


Eingang

Ihr Programm oder Ihre Funktion erstellt eine Liste mit vier nicht negativen Zahlen in einem beliebigen geeigneten, konsistenten Format. Dies schließt eine Liste von ganzen Zahlen, eine nicht durch Ziffern getrennte Zeichenfolge oder separate Argumente ein (ist jedoch nicht darauf beschränkt). Diese vier Zahlen geben die Anzahl der übereinstimmenden Paare für jeden Klammertyp an. Zum Beispiel [1,2,3,4]würde darstellen:

  • 1 Paar ()

  • 2 Paare von {}

  • 3 Paare von []und

  • 4 Paar <>

Sie können auswählen, welchem ​​Klammerpaar jeder Eingang entspricht, solange er konsistent ist.

Ausgabe

Sie sollten alle vollständig übereinstimmenden Zeichenfolgen ausgeben, die aus dieser Liste von Klammern ohne Duplikate gebildet werden können. Die Ausgabe kann in jedem vernünftigen Format erfolgen, einschließlich des Druckens einer Zeichenfolge ohne Klammerbegrenzung nach STDOUT oder einer Liste von Zeichenfolgen als Rückgabewert einer Funktion.

Ihr Algorithmus muss für jede beliebige Eingabe funktionieren, Sie müssen sich jedoch keine Gedanken über Speicher-, Zeit- oder Ganzzahlgrößenbeschränkungen machen (z. B. wenn Ihre Antwort in C ist, erhalten Sie 2 33 nicht als Eingabe).

Das ist , also gewinnt die kürzeste Antwort in Bytes.

Beispiel für Ein- und Ausgabe

Für dieses Beispiel verwende ich die gleiche Eingabereihenfolge wie oben.

Für jedes Beispiel wird die erste Zeile eingegeben und die folgenden Zeilen werden ausgegeben

Example 0:
[0,0,0,0]


Example 1:
[1,0,0,0]
()

Example 2:
[0,2,0,0]
{}{}
{{}}

Example 3:
[0,0,1,1]
[]<>
[<>]
<[]>
<>[]

Example 4:
[0,1,2,0]
{}[][]  {}[[]]  {[]}[]  {[][]}  {[[]]} 
[{}][]  [{}[]]  [{[]}]  []{}[]  []{[]} 
[][{}]  [][]{}  [[{}]]  [[]{}]  [[]]{}

Example 5:
[1,0,0,3]
()<><><>  ()<><<>>  ()<<>><>  ()<<><>>  ()<<<>>>  (<>)<><>  (<>)<<>>
(<><>)<>  (<><><>)  (<><<>>)  (<<>>)<>  (<<>><>)  (<<><>>)  (<<<>>>)
<()><><>  <()><<>>  <()<>><>  <()<><>>  <()<<>>>  <(<>)><>  <(<>)<>>
<(<><>)>  <(<<>>)>  <>()<><>  <>()<<>>  <>(<>)<>  <>(<><>)  <>(<<>>)
<><()><>  <><()<>>  <><(<>)>  <><>()<>  <><>(<>)  <><><()>  <><><>()
<><<()>>  <><<>()>  <><<>>()  <<()>><>  <<()><>>  <<()<>>>  <<(<>)>>
<<>()><>  <<>()<>>  <<>(<>)>  <<>>()<>  <<>>(<>)  <<>><()>  <<>><>()
<<><()>>  <<><>()>  <<><>>()  <<<()>>>  <<<>()>>  <<<>>()>  <<<>>>()

Example 6:
[1,1,1,1]

(){}[]<>  (){}[<>]  (){}<[]>  (){}<>[]  (){[]}<>  (){[]<>}  (){[<>]}
(){<[]>}  (){<>}[]  (){<>[]}  ()[{}]<>  ()[{}<>]  ()[{<>}]  ()[]{}<>
()[]{<>}  ()[]<{}>  ()[]<>{}  ()[<{}>]  ()[<>{}]  ()[<>]{}  ()<{}[]>
()<{}>[]  ()<{[]}>  ()<[{}]>  ()<[]{}>  ()<[]>{}  ()<>{}[]  ()<>{[]}
()<>[{}]  ()<>[]{}  ({})[]<>  ({})[<>]  ({})<[]>  ({})<>[]  ({}[])<>
({}[]<>)  ({}[<>])  ({}<[]>)  ({}<>)[]  ({}<>[])  ({[]})<>  ({[]}<>)
({[]<>})  ({[<>]})  ({<[]>})  ({<>})[]  ({<>}[])  ({<>[]})  ([{}])<>
([{}]<>)  ([{}<>])  ([{<>}])  ([]){}<>  ([]){<>}  ([])<{}>  ([])<>{}
([]{})<>  ([]{}<>)  ([]{<>})  ([]<{}>)  ([]<>){}  ([]<>{})  ([<{}>])
([<>{}])  ([<>]){}  ([<>]{})  (<{}[]>)  (<{}>)[]  (<{}>[])  (<{[]}>)
(<[{}]>)  (<[]{}>)  (<[]>){}  (<[]>{})  (<>){}[]  (<>){[]}  (<>)[{}]
(<>)[]{}  (<>{})[]  (<>{}[])  (<>{[]})  (<>[{}])  (<>[]){}  (<>[]{})
{()}[]<>  {()}[<>]  {()}<[]>  {()}<>[]  {()[]}<>  {()[]<>}  {()[<>]}
{()<[]>}  {()<>}[]  {()<>[]}  {([])}<>  {([])<>}  {([]<>)}  {([<>])}
{(<[]>)}  {(<>)}[]  {(<>)[]}  {(<>[])}  {}()[]<>  {}()[<>]  {}()<[]>
{}()<>[]  {}([])<>  {}([]<>)  {}([<>])  {}(<[]>)  {}(<>)[]  {}(<>[])
{}[()]<>  {}[()<>]  {}[(<>)]  {}[]()<>  {}[](<>)  {}[]<()>  {}[]<>()
{}[<()>]  {}[<>()]  {}[<>]()  {}<()[]>  {}<()>[]  {}<([])>  {}<[()]>
{}<[]()>  {}<[]>()  {}<>()[]  {}<>([])  {}<>[()]  {}<>[]()  {[()]}<>
{[()]<>}  {[()<>]}  {[(<>)]}  {[]()}<>  {[]()<>}  {[](<>)}  {[]}()<>
{[]}(<>)  {[]}<()>  {[]}<>()  {[]<()>}  {[]<>()}  {[]<>}()  {[<()>]}
{[<>()]}  {[<>]()}  {[<>]}()  {<()[]>}  {<()>}[]  {<()>[]}  {<([])>}
{<[()]>}  {<[]()>}  {<[]>()}  {<[]>}()  {<>()}[]  {<>()[]}  {<>([])}
{<>}()[]  {<>}([])  {<>}[()]  {<>}[]()  {<>[()]}  {<>[]()}  {<>[]}()
[(){}]<>  [(){}<>]  [(){<>}]  [()]{}<>  [()]{<>}  [()]<{}>  [()]<>{}
[()<{}>]  [()<>{}]  [()<>]{}  [({})]<>  [({})<>]  [({}<>)]  [({<>})]
[(<{}>)]  [(<>){}]  [(<>)]{}  [(<>{})]  [{()}]<>  [{()}<>]  [{()<>}]
[{(<>)}]  [{}()]<>  [{}()<>]  [{}(<>)]  [{}]()<>  [{}](<>)  [{}]<()>
[{}]<>()  [{}<()>]  [{}<>()]  [{}<>]()  [{<()>}]  [{<>()}]  [{<>}()]
[{<>}]()  [](){}<>  [](){<>}  []()<{}>  []()<>{}  []({})<>  []({}<>)
[]({<>})  [](<{}>)  [](<>){}  [](<>{})  []{()}<>  []{()<>}  []{(<>)}
[]{}()<>  []{}(<>)  []{}<()>  []{}<>()  []{<()>}  []{<>()}  []{<>}()
[]<(){}>  []<()>{}  []<({})>  []<{()}>  []<{}()>  []<{}>()  []<>(){}
[]<>({})  []<>{()}  []<>{}()  [<(){}>]  [<()>{}]  [<()>]{}  [<({})>]
[<{()}>]  [<{}()>]  [<{}>()]  [<{}>]()  [<>(){}]  [<>()]{}  [<>({})]
[<>{()}]  [<>{}()]  [<>{}]()  [<>](){}  [<>]({})  [<>]{()}  [<>]{}()
<(){}[]>  <(){}>[]  <(){[]}>  <()[{}]>  <()[]{}>  <()[]>{}  <()>{}[]
<()>{[]}  <()>[{}]  <()>[]{}  <({})[]>  <({})>[]  <({}[])>  <({[]})>
<([{}])>  <([]){}>  <([])>{}  <([]{})>  <{()}[]>  <{()}>[]  <{()[]}>
<{([])}>  <{}()[]>  <{}()>[]  <{}([])>  <{}[()]>  <{}[]()>  <{}[]>()
<{}>()[]  <{}>([])  <{}>[()]  <{}>[]()  <{[()]}>  <{[]()}>  <{[]}()>
<{[]}>()  <[(){}]>  <[()]{}>  <[()]>{}  <[({})]>  <[{()}]>  <[{}()]>
<[{}]()>  <[{}]>()  <[](){}>  <[]()>{}  <[]({})>  <[]{()}>  <[]{}()>
<[]{}>()  <[]>(){}  <[]>({})  <[]>{()}  <[]>{}()  <>(){}[]  <>(){[]}
<>()[{}]  <>()[]{}  <>({})[]  <>({}[])  <>({[]})  <>([{}])  <>([]){}
<>([]{})  <>{()}[]  <>{()[]}  <>{([])}  <>{}()[]  <>{}([])  <>{}[()]
<>{}[]()  <>{[()]}  <>{[]()}  <>{[]}()  <>[(){}]  <>[()]{}  <>[({})]
<>[{()}]  <>[{}()]  <>[{}]()  <>[](){}  <>[]({})  <>[]{()}  <>[]{}()
Riley
quelle
Related
Riley

Antworten:

6

Haskell , 128 Bytes

fist die Hauptfunktion, nimmt eine Liste von Ints und gibt eine Liste von Strings zurück.

f=g.($zip"({[<"")}]>").zipWith replicate
g=max[""].(#g)
l#c=[b:s|x@(b,e):r<-l,s<-(r:filter(/=x:r)l)?(map(e:).c)]
l?c=c l++l#(?c)

Probieren Sie es online!

Wie es funktioniert

  • ftransformiert seine Eingabeliste in eine Liste von Tupellisten, wobei jedes Tupel ein Klammerpaar enthält und jeder Klammertyp in einer eigenen Unterliste enthalten ist. ZB [1,2,0,0]wird [[('{','}')],[('[',']'),('[',']')]]. Dann ruft es gmit der transformierten Liste auf.
  • Die übrigen Funktionen verwenden einen teilweise fortlaufenden Stil, der mit der Manipulation von Listen vermischt ist. Jede Fortsetzungsfunktion erstellt ceine Liste lder verbleibenden Klammer-Tupellisten und gibt eine Liste der möglichen Zeichenfolgen zurück, die an die bereits generierten Zeichenfolgen angehängt werden sollen.
  • g lgeneriert die Liste der vollständig übereinstimmenden Zeichenfolgen, die mithilfe aller Klammern in gebildet werden können l.
    • Dazu werden l#gZeichenfolgen generiert, die mit einer eckigen Klammer beginnen. Der rekursive gParameter wird selbst als Fortsetzung von verwendet #, um zu generieren, was nach dem ersten in eckige Klammern eingeschlossenen Unterelement kommt.
    • In dem Fall, in dem keine solchen Zeichenfolgen vorhanden sind (da lkeine Klammern mehr enthalten sind), wird gstattdessen [""]die Liste zurückgegeben, die nur die leere Zeichenfolge enthält. Da der [""]Vergleich mit allen nicht leeren Listen, die von erstellt werden können #, kleiner ist , können wir dies durch Anwenden von tun max.
  • l#cGeneriert Zeichenfolgen, lbeginnend mit mindestens einem in eckige Klammern eingeschlossenen Unterelement, und clegt anschließend fest, was auf das Element folgt.
    • bund esind ein ausgewähltes Paar von Klammern im Tupel xund rdie Liste der verbleibenden Tupel desselben Klammertyps.
    • r:filter(/=x:r)list lmit dem Tupel xentfernt, leicht neu angeordnet.
    • ?wird aufgerufen, um die möglichen Unterelemente zwischen bund zu erzeugen e. Es erhält eine eigene Fortsetzung map(e:).c, die ejedem der von generierten Suffix-Strings vorangestellt wird c.
    • #selbst stellt die Initiale ballen Zeichenfolgen voran, die von ?und generiert werden c.
  • l?cgeneriert die vollständig übereinstimmenden Zeichenfolgen, die mithilfe von null oder mehr Klammernpaaren aus formbar sind l, und überlässt diese dann ihrer Fortsetzung c, um die verbleibenden Zeichenfolgen zu verarbeiten. Das c lTeil geht direkt zu, cohne Unterelemente hinzuzufügen, während es l#(?c)verwendet wird #, um ein Unterelement zu generieren und dann (?c)rekursiv nach möglichen weiteren aufzurufen .
Ørjan Johansen
quelle
4

Jelly , 50 40 34 Bytes

-6 Bytes dank Leaky Nun (immer weniger Arbeit, wo ich nicht konnte)

“()“{}“[]“<>”©ẋ"FŒ!QµW;®œṣF¥/µÐLÐḟ

Einfach und ineffizient.

Probieren Sie es online! (Timeout bei TIO für [1,1,1,1] - ja, ineffizient.)

Wie?

Entfernt rekursiv Paare übereinstimmender Klammern, die direkt nebeneinander stehen, bis für jede mögliche gebildete Zeichenfolge keine weiteren Klammern mehr entfernt werden können. Dabei werden solche Zeichenfolgen beibehalten, die sich auf nichts reduzieren (daher haben sie den gesamten übereinstimmenden Inhalt).

“()“{}“[]“<>”©ẋ"FŒ!QµW;®œṣF¥/µÐLÐḟ - Main link: list: [n(), n{}, n[], n<>]
“()“{}“[]“<>”                      - literal ["()", "{}", "[]", "<>"]
             ©                     - copy to register
               "                   - zip with:
              ẋ                    -   repeat list
                F                  - flatten
                 Œ!                - all permutations (yeah, it's inefficient!)
                   Q               - de-duplicate
                    µ              - monadic chain separation
                                Ðḟ - filter discard if (non empty is truthy):
                             µÐL   -   loop until no change:
                       ®           -     recall value from register
                     W             -     wrap loop variable in a list
                      ;            -     concatenate
                           ¥/      -     reduce with last two links as a dyad:
                        œṣ         -       split left on occurrences of sublist on the right
                          F        -       flatten the result
Jonathan Allan
quelle
1
Keine Notwendigkeit, Auswertungs-Tricks zu verwenden. Verwenden Sie stattdessen Reduzieren. 35 Bytes
Undichte Nonne
1
Verschieben der ersten Zeile in die zweite ... 34 Bytes
Undichte Nonne
@LeakyNun Danke! Ich habe es versucht, konnte aber keine Reduzierung zum Laufen bringen (daher habe ich auf eval zurückgegriffen).
Jonathan Allan
Schön, ich habe den gleichen Ansatz von œṣ- F- µÐLin einem etwas verwandten Problem verwendet .
Zacharý
3

Pyth - 83 74 71 63 Bytes

K("\[]""{}""\(\)""<>")Fd{.psm*:@Kd*\\2k@QdU4JdVldFHK=:JHk))I!Jd

Versuch es

1 : Kc "[] {} () <>") Fd {.ps * VR \ KQJdVldFHK =: JHk)) I! Jd

Auch diese 53-Byte-Version dank Leaky Nun

Kc"\[] \{} \(\) <>")Fd{.ps*V-R\\KQJdVldFHK=:JHk))I!Jd

Hier

Maria
quelle
Gelee von Pyth geschlagen? Was ist das für eine Zauberei?
Math Junkie
@mathjunkie Ich habe Jelly nicht geschlagen. Ich habe die Eingabesyntax verkorkst.
Maria
... und ich denke, ich kann mich verbessern: D
Jonathan Allan
@ JonathanAllan so kann diese Antwort.
Undichte Nonne
1
Schritt 1: stattdessen machen ("\[]""{}""\(\)""<>")wir c"\[] \{} \(\) <>")(auf Leerzeichen aufgeteilt); statt :@Kd*\\2k, haben wir -@Kddurch zwei Schrägstriche gefolgt; dann machen U4wir es , anstatt es zu mappen *V-R\\KQ(multiplizieren Sie zwei Arrays parallel). Das erste Array wird generiert mit R: -R\\kDies gibt Ihnen eine 54-Byte-Version
Leaky Nun
2

05AB1E , 33 32 30 27 25 Bytes

7 Bytes gespart dank Riley .

Eingabereihenfolge ist [(),<>,[],{}]

žu4äשJœJÙD[D®õ:DŠQ#]€g_Ï

Probieren Sie es online!

Erläuterung

žu                             # push the string "()<>[]{}"
  4ä                           # split in 4 parts
    ©                          # store a copy in register
     ×                         # repeat each bracket a number of times decided by input
      JœJÙ                     # get the unique permutations of the string of brackets
          D                    # duplicate
           [                   # start infinite loop
            D                  # duplicate current list of permutations
             ®õ:               # replace any instance of (), [], <>, {} 
                               # with an empty string
                DŠ             # duplicate and move down 2 places on stack
                  Q#           # if the operation didn't alter the list, exit loop
                    ]          # end loop
                     €g        # get the length of each subtring
                       _Ï      # keep only the strings in the original 
                               # list of unique permutations 
                               # that have a length of 0 in the resulting list
Emigna
quelle
Ich denke : vektorisiert (Sie können den größten Teil der Endlosschleife überspringen). 2. Es ist 1 Byte kürzer zu UXBeginn und Xwenn Sie die Liste der Klammern erneut benötigen.
Riley
@Riley: Ich habe es gerade erst versucht :, aber wir bekommen Probleme, wenn zum Beispiel Ersetzungen auf {}mögliche Ersetzungen auf erstellt werden() da wir bereits versucht haben, alle zu ersetzen (). Guter Punkt über UXobwohl. Wir können auch ein weiteres Byte mit bekommen ©®.
Emigna
Die Tatsache, dass U die Spitze auftaucht, war immer frustrierend. Ich wusste es nicht ©®.
Riley
Ich habe geschaut diese Antwort angesehen . Hat 05AB1E ein Update erhalten, das das Problem behoben hat, oder ist diese Antwort ungültig?
Riley
Diese Antwort funktioniert für [([]{})<{[()<()>]}()>{}], aber nicht für [({})<{[()<()>]}()>{}]. Der einzige Unterschied ist der entfernte []. Ich werde in TNB danach fragen.
Riley
2

Ruby , 123 Bytes

->a{"<>{}[]()".gsub(/../){$&*a.pop}.chars.permutation.map(&:join).uniq.grep /^((\(\g<1>\)|\[\g<1>\]|\{\g<1>\}|<\g<1>>)*)$/}

Probieren Sie es online! Es ist jedoch ineffizient, so dass selbst Eingaben wie [1,2,1,1]eine Zeitüberschreitung im Internet auftreten. Alle aufgeführten Beispiele funktionieren zumindest!

Erläuterung

->a{                                        # Procedure with input a
    "<>{}[]()".gsub(/../){                  # For all pairs of brackets
                          $&*a.pop          # Pop last item in input, then repeat
                                            #   the bracket pair by that number
                                  }.chars   # Get characters
        .permutation                        # All permutations of characters
                    .map(&:join)            # For each permutation, join the chars
                                .uniq       # Get unique permutations only
            .grep /^((\(\g<1>\)|\[\g<1>\]|\{\g<1>\}|<\g<1>>)*)$/}
                                            # Only return permutations that match
                                            #   this bracket-matching regex
Wert Tinte
quelle