Generate all Brain-Flak Snippets

Question

This question is the second of several Brain-flak Birthday challenges designed to celebrate Brain-Flak's first Birthday! You can find more information about Brain-Flak's Birthday here

Challenge

For this challenge you'll be generating all fully matched strings from a list of brackets. To borrow DJMcMayhem's definition of a fully matched string:

• For the purpose of this challenge, a "bracket" is any of these characters: ()[]{}<>.

• A pair of brackets is considered "matched" if the opening and closing brackets are in the right order and have no characters inside of them, such as

  ()
  []{}
  

  Or if every subelement inside of it is also matched.

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

  Subelements can also be nested several layers deep.

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

• A string is considered "Fully matched" if and only if each pair of brackets has the correct opening and closing bracket in the right order.

---

Input

Your program or function will take a list of four non-negative numbers in any convenient, consistent format. This includes (but is not limited to) a list of integers, a non-digit delimited string, or separate arguments. These four numbers represent the number of matched pairs of each type of bracket. For example, [1,2,3,4] would represent:

• 1 pair of ()

• 2 pairs of {}

• 3 pairs of [] and

• 4 pairs of <>

You may choose which pair of brackets each input corresponds to as long as it is consistent.

Output

You should output all fully matched string that can be formed from this list of brackets without duplicates. Output can be in any reasonable format which includes printing a non-bracket delimited string to STDOUT, or a list of strings as a return value from a function.

Your algorithm must work for any arbitrary input, but you don't need to worry about memory, time or integer size limits (e.g. if your answer is in C you won't get 2³³ as an input).

This is code-golf, so the shortest answer in bytes wins.

Example Input and Output

For these example I will use the same input order as above.

For each example, the first line will be input and the following lines will be the output

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

Answer 1

Haskell, 128 bytes

f is the main function, it takes a list of Ints and returns a list of 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)

Try it online!

How it works

• f transforms its input list into a list of lists of tuples, each tuple containing a bracket pair, with each type of bracket in its own sublist. E.g. [1,2,0,0] becomes [[('{','}')],[('[',']'),('[',']')]]. Then it calls g with the transformed list.
• The remaining functions use a partially continuation-passing style intermingled with list manipulation. Each continuation function c takes a list l of remaining bracket tuple lists and returns a list of possible strings to be suffixed to what's already been generated.
• g l generates the list of fully matched strings formable by using all the brackets in l.
  • It does this by calling l#g to generate strings beginning with some bracket. The recursive g parameter is itself used as a continuation by #, to generate what comes after the first bracketed subelement.
  • In the case where there are no such strings (because l has no brackets left inside) g instead returns [""], the list containing just the empty string. Since [""] compares smaller to all nonempty lists produceable by #, we can do this by applying max.
• l#c generates strings from l beginning with at least one bracketed subelement, leaving to the continuation c to determine what follows the element.
  • b and e are a selected pair of brackets in the tuple x, and r is the list of remaining tuples of the same bracket type.
  • r:filter(/=x:r)l is l with the tuple x removed, slightly rearranged.
  • ? is called to generate the possible subelements between b and e. It gets its own continuation map(e:).c, which prefixes e to each of the suffix strings generated by c.
  • # itself prepends the initial b to all the strings generated by ? and c.
• l?c generates the fully matched strings formable by using zero or more bracket pairs from l, and then leaves to its continuation c to handle what's left over. The c l part goes directly to c without adding any subelements, while l#(?c) uses # to generate one subelement and then call (?c) recursively for possible further ones.

Answer 2

Jelly, (削除) 50 40 (削除ここまで) 34 bytes

-6 bytes thanks to Leaky Nun (getting reduce to work where I couldn't)

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

Plain and inefficient.

Try it online! (times out at TIO for [1,1,1,1] - yes, inefficient.)

How?

Recursively removes pairs of matching brackets that reside right next to each other until no more may be removed for every possible string one may form, keeping such strings which reduce to nothing (hence have all matching content).

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

• Leaky Nun: No need to use eval tricks... use reduce instead. 35 bytes
• Leaky Nun: Moving the first line to the second... 34 bytes
• Jonathan Allan: @LeakyNun Thanks! I tried but couldn't get a reduce to work (hence resorted to using eval).
• Adalynn: Nice, I used the same approach of œṣ-F-µÐL in a somewhat related problem.

Answer 3

05AB1E, (削除) 33 (削除ここまで) (削除) 32 (削除ここまで) (削除) 30 (削除ここまで) (削除) 27 (削除ここまで) 25 bytes

Saved 7 bytes thanks to Riley.

Input order is [(),<>,[],{}]

×ばつ©JœJÙD[D®õ:DŠQ#]€g_Ï

Try it online!

Explanation

ž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

• Riley: 1. I think : vectorizes (you can skip most of the infinite loop). 2. It's 1 bytes shorter to use UX at the beginning and X when you need the list of brackets again.
• Emigna: @Riley: I did try just : first, but we get issues when for example replacements on {} creates possible replacements on () as we've already tried replacing all (). Good point about UX though. We can get another byte with ©® as well.
• Riley: The fact that U pops the top was always frustrating. I didn't know about ©®.
• Riley: I was looking at this answer. Did 05AB1E get an update that broke it, or is that answer not valid?
• Riley: That answer works for [([]{})<{[()<()>]}()>{}], but not for [({})<{[()<()>]}()>{}]. The only difference is the removed []. I'll ask about it in TNB.

Answer 4

Pyth - (削除) 83 (削除ここまで) (削除) 74 (削除ここまで) (削除) 71 (削除ここまで) 63 bytes

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

Try It

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

Also, this 53-byte version thanks to Leaky Nun

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

Here

• math junkie: Jelly beaten by Pyth? What is this sorcery?
• Maria: @mathjunkie I didn't beat Jelly; I screwed up the input syntax.
• Jonathan Allan: ...and I think I can improve :D
• Leaky Nun: @JonathanAllan so can this answer.
• Leaky Nun: Step 1: instead of ("\[]""{}""\(\)""<>"), we do c"\[] \{} \(\) <>") (split on whitespace); instead of :@Kd*\2円k, we do -@Kd followed by two backslashes; then, instead of mapping on U4, we do *V-R\\KQ (multiply two arrays in parallel). The first array is generated using R, namely -R\\k This will give you a 54-byte version

Answer 5

Ruby, 123 bytes

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

Try it online! It's inefficient, though, so even inputs like [1,2,1,1] will time out online. All the listed examples will work, at least!

Explanation

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