Esta pergunta é o segundo de vários desafios do aniversário do Brain-flak, projetados para comemorar o primeiro aniversário do Brain-Flak! Você pode encontrar mais informações sobre o aniversário de Brain-Flak aqui

Desafio

Para esse desafio, você estará gerando todas as seqüências totalmente correspondentes a partir de uma lista de colchetes. Para emprestar a definição de DJMcMayhem de uma sequência totalmente correspondente:

Para o propósito deste desafio, um "suporte" é qualquer um desses caracteres: ()[]{}<>.
Um par de colchetes é considerado "correspondente" se os colchetes de abertura e fechamento estiverem na ordem correta e não tiverem caracteres dentro deles, como
```
()
[]{}
```
Ou se todos os subelementos dentro dele também corresponderem.
```
[()()()()]
{<[]>}
(()())
```
Os subelementos também podem ser aninhados com várias camadas de profundidade.
```
[(){<><>[()]}<>()]
<[{((()))}]>
```
Uma string é considerada "Totalmente correspondida" se, e somente se, cada par de colchetes tiver o colchete de abertura e fechamento correto na ordem correta.

Entrada

Seu programa ou função fará uma lista de quatro números não negativos em qualquer formato conveniente e consistente. Isso inclui (mas não está limitado a) uma lista de números inteiros, uma sequência delimitada por não dígitos ou argumentos separados. Esses quatro números representam o número de pares correspondentes de cada tipo de colchete. Por exemplo, [1,2,3,4]representaria:

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

Você pode escolher qual par de colchetes cada entrada corresponde, desde que seja consistente.

Resultado

Você deve gerar todas as seqüências totalmente correspondentes que podem ser formadas a partir desta lista de colchetes sem duplicatas. A saída pode estar em qualquer formato razoável, que inclua a impressão de uma string delimitada sem colchetes em STDOUT ou uma lista de strings como valor de retorno de uma função.

Seu algoritmo deve funcionar para qualquer entrada arbitrária, mas você não precisa se preocupar com limites de tamanho de memória, tempo ou número inteiro (por exemplo, se sua resposta estiver em C, você não receberá 2 ³³ como entrada).

Isso é código-golfe , então a resposta mais curta em bytes vence.

Exemplo de entrada e saída

Neste exemplo, usarei a mesma ordem de entrada que acima.

Para cada exemplo, a primeira linha será inserida e as seguintes linhas serão a saída

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
fonte

Relacionado

Riley

6

Haskell , 128 bytes

fé a função principal, pega uma lista de se Intretorna uma 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)

Experimente online!

Como funciona

ftransforma sua lista de entrada em uma lista de listas de tuplas, cada uma contendo uma par de colchetes, com cada tipo de colchete em sua própria sub-lista. Por exemplo, [1,2,0,0]torna-se [[('{','}')],[('[',']'),('[',']')]]. Em seguida, ele chama gcom a lista transformada.
As funções restantes usam um estilo de passagem de continuação parcialmente misturado à manipulação de lista. Cada função de continuação cpega uma lista lde listas de tupla de colchete restantes e retorna uma lista de possíveis strings a serem sufixadas no que já foi gerado.
g lgera a lista de seqüências de caracteres totalmente correspondentes, configuráveis usando todos os colchetes l.
- Isso é feito chamando l#gpara gerar strings começando com algum colchete. O gpróprio parâmetro recursivo é usado como uma continuação de #, para gerar o que vem após o primeiro subelemento entre colchetes.
- No caso em que não existem essas cadeias (porque lnão há colchetes dentro), em gvez disso [""], a lista contém apenas a cadeia vazia. Como [""]compara menor a todas as listas não vazias produzíveis por #, podemos fazer isso aplicando max.
l#cgera sequências do linício com pelo menos um subelemento entre colchetes, deixando a continuação cpara determinar o que segue o elemento.
- be esão um par selecionado de colchetes na tupla xe ré a lista de tuplas restantes do mesmo tipo de colchete.
- r:filter(/=x:r)lé lcom a tupla xremovida, ligeiramente reorganizada.
- ?é chamado para gerar os possíveis subelementos entre be e. Ele obtém sua própria continuação map(e:).c, que prefixa ecada uma das cadeias de sufixos geradas por c.
- #em si precede a inicial ba todas as seqüências geradas por ?e c.
l?cgera as seqüências de caracteres totalmente correspondentes configuráveis usando zero ou mais pares de colchetes de le, em seguida, deixa a continuação cpara lidar com o que resta. A c lparte vai diretamente para csem adicionar subelementos, enquanto l#(?c)usa #para gerar um subelemento e depois chamar (?c)recursivamente para possíveis outros.

Ørjan Johansen
fonte

4

Geléia , 50 40 34 bytes

-6 bytes graças a Leaky Nun (ficando reduzido ao trabalho onde eu não podia)

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

Simples e ineficiente.

Experimente online! (atinge o tempo limite no TIO por [1,1,1,1] - sim, ineficiente.)

Quão?

Remove recursivamente pares de colchetes correspondentes que residem um ao lado do outro até que não mais sejam removidos para cada sequência possível, mantendo essas sequências que se reduzem a nada (portanto, têm todo o conteúdo correspondente).

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

1

Não há necessidade de usar truques de avaliação ... use reduzir em vez disso. 35 bytes

Freira vazada

1

Movendo a primeira linha para a segunda ... 34 bytes

Freira gotejante

@LeakyNun Thanks! Eu tentei, mas não consegui reduzir o trabalho (daí recorri ao uso de eval).

Jonathan Allan

Bom, usei a mesma abordagem de œṣ- F- µÐLem um problema um pouco relacionado .

Zacharý 9/09/17

3

Pitão - 83 74 71 63 bytes

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

Tente

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

Além disso, esta versão de 53 bytes graças a Leaky Nun

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

Aqui

Maria
fonte

Geléia vencida por Pyth? O que é essa feitiçaria?

matemática viciado em

@mathjunkie Eu não venci Jelly; Estraguei a sintaxe de entrada.

Maria

... e acho que posso melhorar: D

Jonathan Allan

@ JonAllAllan, também pode esta resposta.

Leaky Nun

1

Etapa 1: em vez de ("\[]""{}""\(\)""<>"), nós fazemos c"\[] \{} \(\) <>")(dividimos em espaço em branco); em vez de :@Kd*\\2k, -@Kdseguimos por duas barras invertidas; então, em vez de mapear U4, fazemos *V-R\\KQ(multiplique duas matrizes em paralelo). A primeira matriz é gerada utilizando R, nomeadamente -R\\kIsto lhe dará uma versão 54-byte

Leaky Nun

2

05AB1E , 33 32 30 27 25 bytes

Economizou 7 bytes graças a Riley .

A ordem de entrada é [(),<>,[],{}]

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

Experimente online!

Explicação

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

1. Eu acho que :vetoriza (você pode pular a maior parte do loop infinito). 2. É 1 bytes mais curto para usar UXno início e Xquando você precisar da lista de colchetes novamente.

Riley

@Riley: Eu tentei apenas :primeiro, mas temos problemas quando, por exemplo, substituições {}cria possíveis substituições, ()pois já tentamos substituir todas (). Bom ponto sobre UXembora. Também podemos obter outro byte ©®.

Emigna

Riley #

Eu estava olhando para esta resposta . 05AB1E recebeu uma atualização que a quebrou ou essa resposta não é válida?

Riley

Essa resposta funciona para [([]{})<{[()<()>]}()>{}], mas não para [({})<{[()<()>]}()>{}]. A única diferença é a removida []. Vou perguntar sobre isso na TNB.

Riley

2

Ruby , 123 bytes

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

Experimente online! É ineficiente, porém, mesmo entradas como [1,2,1,1]o tempo limite ficam on-line. Todos os exemplos listados funcionarão, pelo menos!

Explicação

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

Value Ink
fonte

Gere todos os snippets do Brain-Flak

Desafio

Entrada

Resultado

Exemplo de entrada e saída

Respostas:

Haskell , 128 bytes

Como funciona

Geléia , 50 40 34 bytes

Quão?

Pitão - 83 74 71 63 bytes

05AB1E , 33 32 30 27 25 bytes

Ruby , 123 bytes

Explicação