¡Esta pregunta es el segundo de varios desafíos de cumpleaños de Brain-flak diseñados para celebrar el primer cumpleaños de Brain-Flak! Puede encontrar más información sobre el cumpleaños de Brain-Flak aquí

Desafío

Para este desafío, generará todas las cadenas totalmente coincidentes a partir de una lista de paréntesis. Para tomar prestada la definición de DJMcMayhem de una cadena totalmente coincidente:

Para el propósito de este desafío, un "paréntesis" es cualquiera de estos caracteres: ()[]{}<> .
Un par de paréntesis se considera "coincidente" si los paréntesis de apertura y cierre están en el orden correcto y no tienen caracteres dentro de ellos, como
```
()
[]{}
```
O si cada subelemento dentro de él también coincide.
```
[()()()()]
{<[]>}
(()())
```
Los subelementos también se pueden anidar en varias capas de profundidad.
```
[(){<><>[()]}<>()]
<[{((()))}]>
```
Una cadena se considera "Totalmente coincidente" si y solo si cada par de corchetes tiene el corchete de apertura y cierre correcto en el orden correcto.

Entrada

Su programa o función tomará una lista de cuatro números no negativos en cualquier formato conveniente y consistente. Esto incluye (pero no se limita a) una lista de enteros, una cadena delimitada sin dígitos o argumentos separados. Estos cuatro números representan el número de pares coincidentes de cada tipo de paréntesis. Por ejemplo, [1,2,3,4]representaría:

1 par de ()
2 pares de {}
3 pares de []y
4 pares de <>

Puede elegir a qué par de paréntesis corresponde cada entrada, siempre que sea coherente.

Salida

Debe generar todas las cadenas totalmente coincidentes que se pueden formar a partir de esta lista de corchetes sin duplicados. La salida puede estar en cualquier formato razonable que incluya la impresión de una cadena delimitada sin corchetes en STDOUT, o una lista de cadenas como valor de retorno de una función.

Su algoritmo debe funcionar para cualquier entrada arbitraria, pero no necesita preocuparse por los límites de memoria, tiempo o tamaño entero (por ejemplo, si su respuesta está en C, no obtendrá 2 ³³ como entrada).

Este es el código de golf , por lo que gana la respuesta más corta en bytes.

Ejemplo de entrada y salida

Para este ejemplo, usaré el mismo orden de entrada que el anterior.

Para cada ejemplo, se ingresará la primera línea y las siguientes serán la salida.

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]

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

code-golf string permutations balanced-string brain-flak Riley
fuente

Relacionado

Riley

6

Haskell , 128 bytes

fes la función principal, toma una lista de Intsy devuelve una lista 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)

Pruébalo en línea!

Cómo funciona

ftransforma su lista de entrada en una lista de listas de tuplas, cada tupla contiene un par de paréntesis, con cada tipo de paréntesis en su propia sublista. Por ejemplo, se [1,2,0,0]convierte [[('{','}')],[('[',']'),('[',']')]]. Luego llama gcon la lista transformada.
Las funciones restantes usan un estilo de paso de continuación parcialmente mezclado con la manipulación de listas. Cada función de continuación ctoma una lista lde las listas de tuplas de paréntesis restantes y devuelve una lista de posibles cadenas para que tengan como sufijo lo que ya se ha generado.
g lgenera la lista de cadenas totalmente coincidentes formables mediante el uso de todos los corchetes l.
- Lo hace llamando l#ga generar cadenas que comienzan con un paréntesis. El gparámetro recursivo se utiliza como continuación por# para generar lo que viene después del primer subelemento entre corchetes.
- En el caso de que no existan tales cadenas (porque lno tiene corchetes dentro), en su glugar [""], la lista contiene solo la cadena vacía. Debido a que [""]compara listas más pequeñas con todas las no producibles #, podemos hacerlo aplicando max.
l#cgenera cadenas desde el lprincipio con al menos un subelemento entre corchetes, dejando a la continuaciónc para determinar qué sigue al elemento.
- by eson un par de paréntesis seleccionados en la tupla x, y res la lista de tuplas restantes del mismo tipo de paréntesis.
- r:filter(/=x:r)les lcon la tupla xeliminada, ligeramente reorganizada.
- ?se llama para generar los subelementos posibles entre by e. Obtiene su propia continuación map(e:).c, que prefija ea cada una de las cadenas de sufijo generadas por c.
- #antecede la inicial ba todas las cadenas generadas por ?y c.
l?cgenera las cadenas totalmente coincidentes formables mediante el uso de cero o más pares de paréntesis l, y luego deja su continuación cpara manejar lo que queda. La c lparte va directamente a csin agregar ningún subelemento, mientras que se l#(?c)usa #para generar un subelemento y luego llama (?c)recursivamente para posibles más.

Ørjan Johansen
fuente

4

Jalea , 50 40 34 bytes

-6 bytes gracias a Leaky Nun (reduciéndome al trabajo donde no podía)

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

Llano e ineficiente.

Pruébalo en línea!(tiempo de espera en TIO para [1,1,1,1] - sí, ineficiente)

¿Cómo?

Elimina recursivamente pares de corchetes coincidentes que residen uno al lado del otro hasta que no se puedan quitar más por cada posible cadena que se pueda formar, manteniendo tales cadenas que se reducen a nada (por lo tanto, tienen todo el contenido coincidente).

“()“{}“[]“<>”©ẋ"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
fuente

1

No es necesario usar trucos de evaluación ... use reducir en su lugar. 35 bytes

Leaky Nun

1

Moviendo la primera línea a la segunda ... 34 bytes

Leaky Nun

@LeakyNun ¡Gracias! Lo intenté pero no pude conseguir una reducción para trabajar (por lo tanto, recurrí al uso de eval).

Jonathan Allan

Bien, usé el mismo enfoque de œṣ...F - µÐLen un problema de alguna manera relacionado .

Zacharý

3

Pyth - 83 74 71 63 bytes

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

Intentalo

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

Además, esta versión de 53 bytes gracias a Leaky Nun

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

aquí

Maria
fuente

¿Jalea golpeada por Pyth? ¿Qué es esta hechicería?

adicto a las matemáticas

@mathjunkie No le gané a Jelly; Arruiné la sintaxis de entrada.

Maria

... y creo que puedo mejorar: D

Jonathan Allan

@ JonathanAllan también puede esta respuesta.

Leaky Nun

1

Paso 1: en lugar de ("\[]""{}""\(\)""<>"), lo hacemos c"\[] \{} \(\) <>")(dividir en espacios en blanco); en lugar de :@Kd*\\2k, seguimos -@Kddos barras invertidas; entonces, en lugar de mapear U4, lo hacemos *V-R\\KQ(multiplicamos dos matrices en paralelo). La primera matriz se genera usando R, a saber, -R\\kEsto le dará una versión de 54 bytes

Leaky Nun

2

05AB1E , 33 32 30 27 25 bytes

Guardado 7 bytes gracias a Riley .

El orden de entrada es [(),<>,[],{}]

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

Pruébalo en línea!

Explicación

ž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
fuente

1. Creo que :vectoriza (puede omitir la mayor parte del bucle infinito). 2. Es 1 bytes más corto para usar UXal principio y Xcuando necesita la lista de corchetes nuevamente.

Riley

@Riley: Intenté solo :primero, pero tenemos problemas cuando, por ejemplo, los reemplazos {}crean posibles reemplazos ()ya que ya hemos intentado reemplazar todos (). Buen punto sobre UXsin embargo. También podemos obtener otro byte ©®.

Emigna

Riley

Estaba mirando esta respuesta . ¿Recibió 05AB1E una actualización que la rompió o esa respuesta no es válida?

Riley

Esa respuesta funciona para [([]{})<{[()<()>]}()>{}], pero no para [({})<{[()<()>]}()>{}]. La única diferencia es la eliminada []. Lo preguntaré en TNB.

Riley

2

Ruby , 123 bytes

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

Pruébalo en línea!Sin embargo, es ineficiente, por lo que incluso las entradas como [1,2,1,1]se agotarán en línea. ¡Todos los ejemplos enumerados funcionarán, al menos!

Explicación

->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

Tinta de valor
fuente

Genera todos los fragmentos de Brain-Flak

Desafío

Entrada

Salida

Ejemplo de entrada y salida

Respuestas:

Haskell , 128 bytes

Cómo funciona

Jalea , 50 40 34 bytes

¿Cómo?

Pyth - 83 74 71 63 bytes

05AB1E , 33 32 30 27 25 bytes

Ruby , 123 bytes

Explicación