Générez tous les extraits de Brain-Flak

14

Cette question est la deuxième de plusieurs défis d'anniversaire de Brain-flak conçus pour célébrer le premier anniversaire de Brain-Flak! Vous pouvez trouver plus d'informations sur l'anniversaire de Brain-Flak ici

Défi

Pour ce défi, vous allez générer toutes les chaînes parfaitement adaptées à partir d'une liste de crochets. Pour emprunter la définition de DJMcMayhem d'une chaîne entièrement appariée:

  • Aux fins de ce défi, un « support » est l' un de ces caractères: ()[]{}<>.

  • Une paire de crochets est considérée comme "assortie" si les crochets d'ouverture et de fermeture sont dans le bon ordre et ne contiennent aucun caractère à l'intérieur d'eux, tels que

    ()
    []{}
    

    Ou si chaque sous-élément à l'intérieur est également mis en correspondance.

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

    Les sous-éléments peuvent également être imbriqués plusieurs couches en profondeur.

    [(){<><>[()]}<>()]
    <[{((()))}]>
    
  • Une chaîne est considérée comme "entièrement mise en correspondance" si et seulement si chaque paire de supports a le support d'ouverture et de fermeture correct dans le bon ordre.


Contribution

Votre programme ou fonction prendra une liste de quatre nombres non négatifs dans n'importe quel format pratique et cohérent. Cela inclut (mais sans s'y limiter) une liste d'entiers, une chaîne non délimitée par des chiffres ou des arguments séparés. Ces quatre nombres représentent le nombre de paires appariées de chaque type de support. Par exemple, [1,2,3,4]représenterait:

  • 1 paire de ()

  • 2 paires de {}

  • 3 paires de []et

  • 4 paires de <>

Vous pouvez choisir à quelle paire de parenthèses chaque entrée correspond tant qu'elle est cohérente.

Production

Vous devez sortir toutes les chaînes entièrement correspondantes qui peuvent être formées à partir de cette liste de crochets sans doublons. La sortie peut être dans n'importe quel format raisonnable qui inclut l'impression d'une chaîne non délimitée par des crochets sur STDOUT, ou une liste de chaînes comme valeur de retour d'une fonction.

Votre algorithme doit fonctionner pour toute entrée arbitraire, mais vous n'avez pas à vous soucier de la mémoire, du temps ou des limites de taille entières (par exemple, si votre réponse est en C, vous n'obtiendrez pas 2 33 en entrée).

C'est du , donc la réponse la plus courte en octets l'emporte.

Exemple d'entrée et de sortie

Pour ces exemples, j'utiliserai le même ordre d'entrée que ci-dessus.

Pour chaque exemple, la première ligne sera entrée et les lignes suivantes seront la sortie

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
la source
En relation
Riley

Réponses:

6

Haskell , 128 octets

fest la fonction principale, elle prend une liste de Ints et retourne une liste de Strings.

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)

Essayez-le en ligne!

Comment ça fonctionne

  • ftransforme sa liste d'entrée en une liste de listes de tuples, chaque tuple contenant une paire de parenthèses, avec chaque type de parenthèse dans sa propre sous-liste. Par exemple, [1,2,0,0]devient [[('{','}')],[('[',']'),('[',']')]]. Ensuite, il appelle gavec la liste transformée.
  • Les fonctions restantes utilisent un style de passage partiellement continu mélangé à une manipulation de liste. Chaque fonction de continuation cprend une liste ldes listes de tuple de parenthèses restantes et renvoie une liste de chaînes possibles à suffixer à ce qui a déjà été généré.
  • g lgénère la liste des chaînes entièrement mises en correspondance pouvant être formées à l'aide de tous les crochets de l.
    • Il le fait en appelant l#gpour générer des chaînes commençant par une parenthèse. Le gparamètre récursif est lui-même utilisé comme suite par# , pour générer ce qui vient après le premier sous-élément entre crochets.
    • Dans le cas où il n'y a pas de telles chaînes (car lil n'y a plus de crochets à l'intérieur) gretourne à la place [""], la liste contenant uniquement la chaîne vide. Étant donné que la [""]comparaison est plus petite que toutes les listes non vides pouvant être produites par #, nous pouvons le faire en appliquant max.
  • l#cgénère des chaînes à partir du ldébut avec au moins un sous-élément entre crochets, laissant à la suitec élément de déterminer ce qui suit l'élément.
    • bet esont une paire sélectionnée de parenthèses dans le tuple x, et rest la liste des tuples restants du même type de parenthèse.
    • r:filter(/=x:r)lest lavec le tuple xretiré, légèrement réarrangé.
    • ?est appelé pour générer les sous-éléments possibles entre bet e. Il obtient sa propre continuation map(e:).c, qui préfixe echacune des chaînes de suffixes générées par c.
    • #lui-même ajoute l'initiale bà toutes les chaînes générées par ?et c.
  • l?cgénère les chaînes entièrement appariées pouvant être formées en utilisant zéro ou plusieurs paires de crochets de l, puis laisse à sa suite cpour gérer ce qui reste. La c lpartie passe directement à csans ajouter de sous-éléments, tandis qu'elle est l#(?c)utilisée #pour générer un sous-élément, puis appeler (?c)récursivement pour d'autres possibles.
Ørjan Johansen
la source
4

Gelée , 50 40 34 octets

-6 octets grâce à Leaky Nun (se réduire au travail là où je ne pouvais pas)

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

Simple et inefficace.

Essayez-le en ligne!(expiration à TIO pour [1,1,1,1] - oui, inefficace.)

Comment?

Supprime récursivement des paires de crochets correspondants qui résident juste à côté les uns des autres jusqu'à ce qu'il n'y ait plus de suppression pour chaque chaîne possible que l'on peut former, en gardant ces chaînes qui se réduisent à rien (donc ont tout le contenu correspondant).

“()“{}“[]“<>”©ẋ"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
la source
1
Pas besoin d'utiliser des astuces eval ... utilisez plutôt réduire. 35 octets
Leaky Nun
1
Déplacer la première ligne vers la seconde ... 34 octets
Leaky Nun
@LeakyNun Merci! J'ai essayé mais je n'ai pas pu obtenir de réduction au travail (donc j'ai eu recours à eval).
Jonathan Allan
Bien, j'ai utilisé la même approche de œṣ- F- µÐLdans un problème quelque peu connexe .
Zacharý
3

Pyth - 83 74 71 63 octets

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

Essayez-le

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

Aussi, cette version de 53 octets grâce à Leaky Nun

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

Ici

Maria
la source
Gelée battue par Pyth? Quelle est cette sorcellerie?
junkie de mathématiques
@mathjunkie Je n'ai pas battu Jelly; J'ai foiré la syntaxe d'entrée.
Maria
... et je pense que je peux m'améliorer: D
Jonathan Allan
@JonathanAllan peut donc cette réponse.
Leaky Nun
1
Étape 1: au lieu de ("\[]""{}""\(\)""<>"), nous le faisons c"\[] \{} \(\) <>")(divisé sur un espace blanc); au lieu de :@Kd*\\2k, nous avons -@Kdsuivi de deux barres obliques inverses; puis, au lieu de mapper U4, nous faisons *V-R\\KQ(multiplier deux tableaux en parallèle). Le premier tableau est généré en utilisant R, à savoir -R\\kCela vous donnera une version de 54 octets
Leaky Nun
2

05AB1E , 33 32 30 27 25 octets

Enregistré 7 octets grâce à Riley .

L'ordre d'entrée est [(),<>,[],{}]

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

Essayez-le en ligne!

Explication

ž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
la source
1. Je pense que :vectorise (vous pouvez sauter la plupart de la boucle infinie). 2. Il est plus court de 1 octet à utiliser UXau début et Xlorsque vous avez à nouveau besoin de la liste des crochets.
Riley
@Riley: J'ai essayé tout d' :abord, mais nous rencontrons des problèmes lorsque, par exemple, les remplacements sur {}créent des remplacements possibles, ()car nous avons déjà essayé de tout remplacer (). Bon point UXcependant. Nous pouvons également obtenir un autre octet ©®.
Emigna
Le fait que Ule sommet apparaisse était toujours frustrant. Je n'en savais rien ©®.
Riley
Je regardais cette réponse . 05AB1E a-t-il reçu une mise à jour qui l'a interrompue, ou cette réponse n'est-elle pas valide?
Riley
Cette réponse fonctionne pour [([]{})<{[()<()>]}()>{}], mais pas pour [({})<{[()<()>]}()>{}]. La seule différence est la suppression []. Je vais poser des questions à ce sujet dans TNB.
Riley
2

Rubis , 123 octets

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

Essayez-le en ligne! Cependant, il est inefficace, même les entrées comme celles- [1,2,1,1]ci expireront en ligne. Tous les exemples énumérés fonctionneront, au moins!

Explication

->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
Encre de valeur
la source