# Fill in the Bracks

Normal brackets ((),[],<> and {}) are nice and unambiguous, however someone thought it would be a good idea to use non bracket characters as brackets. These characters, | and ", are ambiguous. For example does

""""


correspond to

(())


or

()()


It is impossible to tell.

Things start to get interesting when you mix types of ambiguous brackets, for example

"|""||""|"


Could be any of the following

([(([]))]),([()[]()]),([()][()])


Your task is to take a string made of ambiguous characters and output all the possible balanced strings the author could have intended.

More concretely you output all balanced strings that can be made replacing | with either [ or ] and " with either ( or ). You should not output any balanced string twice.

## IO

As input you should take a string consisting of | and ". If you would like to select two distinct characters other than | and " to serve as replacements you may do so. You should output a container of balanced strings. You may choose to replace [] and () in the output with any other two bracket pairs ((),[],<> or {}) you wish. Your output format should be consistent across runs.

## Scoring

This is so answers will be scored in bytes with fewer bytes being better.

## Test cases

"" -> ["()"]
"|"| -> []
||| -> []
"""" -> ["(())","()()"]
""|| -> ["()[]"]
"|"||"|" -> ["([([])])"]
"|""||""|" -> ["([(([]))])","([()[]()])","([()][()])"]

• waits for a BrainFlak answer Feb 2, 2018 at 22:43
• Can we use integers instead of strings? What about lists of digits or integers? Feb 3, 2018 at 18:46
• @Zgarb Sure that's fine Feb 4, 2018 at 17:54

# Python 2, 135 bytes

s=input()
for k in range(2**len(s)):
try:c=''.join("[]() , ,"[int(c)|k>>i&1::4]for i,c in enumerate(s));eval(c);print c[::2]
except:0


Try it online!

Expects input like 2002 instead of "||", and wrapped in quotes.

Iterates over all 2N possible assignments of "open" and "close" to the string, creating strings c like:

"( [ ( ),],[ ( ),],),( ),"


If eval-ing this string throws an exception, it is unmatched. If not, we print c[::2], giving:

([()][()])()


# Retina, 5956 55 bytes

0"
<$%"> }0' {$%"}
.+
$&_$&
+m^_|(<>|{})(?=.*_)

A_


Try it online! Unfortunately testing for two sets of matched brackets exceeds the golfiness of a single .NET regex, so it saves 15 bytes to check manually. Edit: Saved 3 4 bytes thanks to @H.PWiz. Explanation:

0"
<$%">  Find a " and make two copies of the line, one with a < and one with a >. Do this one " at a time, so that each " doubles the number of lines. }0' {$%"}


Similarly with ', { and }. Then, keep replacing until all "s and 's on all copies have been replaced.

.+
$&_$&


Make a duplicate of the brackets, separated by a _.

+m^_|(<>|{})(?=.*_)


In the duplicate, repeatedly delete matched brackets, until none are left, in which case delete the _ as well.

A_


Delete all lines that still have a _.

# Retina, 7471 70 bytes

0"
<$%"> }0' {$%"}
Lm^(.(?<=(?=\3)(<.*>|{.*}))(?<-3>)|(.))+(?(3)_)$ Try it online! Explanation: The first two stages are as above. The third stage directly prints the result of matching two sets of matched brackets. This uses .NET's balancing groups. At each stage in the match, the regex tries to match a character, then look back for a pair of matching brackets, then check that the top of the stack matches the open bracket. If it can do this, it means that the bracket balances, and the open bracket gets popped from the stack. Otherwise, the assumption is that we're at an open bracket that needs to be pushed to the stack. If these assumptions don't hold then the stack will not be empty at the end and the match will fail. Alternative approach, also 74 71 bytes: Lm^((?=(<.*>|{.*})(?<=(.))).|\3(?<-3>))+(?(3)_)$


Here, we look ahead for either <...> or {...}, then look behind to push the closing bracket on to the stack. Otherwise, we need to match and pop the closing bracket that we captured earlier. In this version the regex might not even make it to the end of the string, but some strings such as <<<> would slip through the net if we didn't check for an empty stack.

• You can save some bytes on escaping by using different characters Feb 4, 2018 at 23:46
• @H.PWiz Ah, I must have overlooked that bit about using alternative bracket pairs, thanks!
– Neil
Feb 5, 2018 at 1:06
• You can also change | in the input Feb 5, 2018 at 6:32

# Husk, 19 bytes

fo¬ωḞoΣx½¨÷₂¨ΠmSe→


Try it online! Uses the characters ds in the input, and the corresponding bracket pairs de and st in the output.

## Explanation

The idea is to generate all possible bracketings of the input and keep those that reduce to the empty string when we repeatedly remove adjacent brackets. The ¨÷₂¨ is a compressed string that expands into "dest", which was chosen because it has a short compressed form and consists of character pairs with adjacent codepoints. Thus the program is equivalent to the following.

fo¬ωḞoΣx½"dest"ΠmSe→  Implicit input, say "ddssdd".
m     Map over the string:
Se    pair character with
→   its successor.
Result: ["de","de","st","st","de","de"]
Π      Cartesian product: ["ddssdd","ddssde",..,"eettee"]
f                      Keep those strings that satisfy this:
Consider argument x = "ddsted".
ω                    Iterate on x until fixed:
½"dest"         Split "dest" into two: ["de","st"]
Ḟ                   Thread through this list (call the element y):
x                 Split x on occurrences of y,
oΣ                  then concatenate.
This is done for both "de" and "st" in order.
Result is "dd".
o¬                    Is it empty? No, so "ddsted" is not kept.
Result is ["destde","ddstee"], print implicitly on separate lines.


# Perl, 5655 53 bytes

Includes +1 for n

uses [ for [] and { for {}

perl -nE 's%.%"#1$&,+\\$&}"^Xm.v6%eg;eval&&y/+//d+say for< $_>' <<< "[{[[{{[[{["  Generates all 2^N possibilities, then uses perl eval to check if a string like '+[+{}]' is valid code and if so removes the + and prints the result # APL (Dyalog Classic), 55 53 bytes {a/⍨~×≢¨'|\[]'⎕r''⍣≡a←⊃∘'()[]'¨¨(⊂'".'⍳⍵)+,⍳2⊣¨⍵}  Try it online! # Clean, 203186 179 bytes ?['(':l][')':t]= ?l t ?['[':l][']':t]= ?l t ?l[h:t]= ?[h:l]t ?[][]=True ?_ _=False @['"']=[['('],[')']] @['|']=[['['],[']']] @[h:t]=[[p:s]\\[p]<- @[h],s<- @t]$s=[k\\k<- @s| ?[]k]


Try it online!

Uses only pattern-matching and comprehensions.

# Perl, 56 bytes

Includes + for n

Uses input [ for output [ or ]

Uses input { for output { or }

perl -nE '/^((.)(?{$^R.$2})(?1)*\2(?{$^R.=$2^v6}))*$(?{say$^R})^/' <<< "[{[[{{[[{["


Uses a perl extended regex to match braces while keeping track of the choices made during backtracking. This can be much more efficient than generating all 2^N candidates since it already rejects many impossible assignments while partway through the input string

# Kotlin, 240236 234 bytes

fold(listOf("")){r,c->r.flatMap{i->when(c){'"'->"()".map{i+it}
else->"[]".map{i+it}}}}.filter{val d=ArrayList<Char>()
it.all{fun f(c:Any)=d.size>1&&d.removeAt(0)==c
when(it){')'->f('(')
']'->f('[')


## Beautified

    fold(listOf("")) {r,c ->
r.flatMap {i-> when(c) {
'"'-> "()".map {i+it}
else -> "[]".map {i+it}
}}
}.filter {
val d = ArrayList<Char>()
it.all {
fun f(c:Any)=d.size>1&&d.removeAt(0)==c
when(it) {
')' -> f('(')
']' -> f('[')
}
} && d.size<1
}


## Test

private fun String.f(): List<String> =
fold(listOf("")){r,c->r.flatMap{i->when(c){'"'->"()".map{i+it}
else->"[]".map{i+it}}}}.filter{val d=ArrayList<Char>()
it.all{fun f(c:Any)=d.size>1&&d.removeAt(0)==c
when(it){')'->f('(')
']'->f('[')

data class Test(val input: String, val outputs: List<String>)

val tests = listOf(
Test("""""""", listOf("()")),
Test(""""|"|""", listOf()),
Test("""|||""", listOf()),
Test("""""""""", listOf("(())","()()")),
Test("""""||""", listOf("()[]")),
Test(""""|"||"|"""", listOf("([([])])")),
Test(""""|""||""|"""", listOf("([(([]))])","([()[]()])","([()][()])"))
)

fun main(args: Array<String>) {
for ((input, output) in tests) {
val actual = input.f().sorted()
val expected = output.sorted()
if (actual != expected) {
throw AssertionError("Wrong answer: $input ->$actual | \$expected")
}
}


## Edits

• -4 jrtapsell - Reworked checking predicate
• -2 jrtapsell - true -> 1>0 and == 0 -> < 1

# C (gcc), 315 bytes

j,b;B(char*S){char*s=calloc(strlen(S)+2,b=1)+1;for(j=0;S[j];b*=(S[j]<62||*--s==60)*(S[j++]-41||*--s==40))S[j]==60?*s++=60:0,S[j]<41?*s++=40:0;return*s>0&*--s<1&b;}f(S,n,k)char*S;{if(n<strlen(S))for(k=2;k--;)S[n]==46-k-k?S[n]=40+k*20,f(S,n+1),S[n]=41+k*21,f(S,-~n),S[n]=46-k-k:0;else B(S)&&puts(S);}F(int*S){f(S,0);}


Try it online!

# C (gcc), 334 bytes (old version)

j,b;B(char*S){char*s=calloc(strlen(S)+2,1)+1;for(b=1,j=0;S[j];j++){if(S[j]==60)*s++=60;if(S[j]<41)*s++=40;b*=!(S[j]>61&&*--s!=60)*!(S[j]==41&&*--s!=40);}return*s>0&*--s<1&b;}f(S,n,k)char*S;{if(n>=strlen(S))return B(S)&&puts(S);for(k=0;k<2;k++)S[n]==46-k-k&&(S[n]=40+k*20,f(S,n+1),S[n]=41+k*21,f(S,-~n),S[n]=46-k-k);}F(char*S){f(S,0);}


Try it online!

# Explanation (old version)

j,b;B(char*S){                   // determine if string is balanced
char*s=calloc(strlen(S)+2,1)+1; // array to store matching brackets
for(b=1,j=0;S[j];j++){          // loop through string (character array)
if(S[j]==60)*s++=60;           // 60 == '<', opening bracket
if(S[j]<41)*s++=40;            // 40 == '(', opening bracket
b*=!(S[j]>61&&*--s!=60)*       // 62 == '>', closing bracket
!(S[j]==41&&*--s!=40);}       // 41 == ')', closing bracket
return*s>0&*--s<1&b;}           // no unmatched brackets and no brackets left to match
f(S,n,k)char*S;{                 // helper function, recursively guesses brackets
if(n>=strlen(S))                // string replaced by possible bracket layout
return B(S)&&puts(S);          // print if balanced, return in all cases
for(k=0;k<2;k++)                // 46 == '.', guess 40 == '(',
S[n]==46-k-k&&(S[n]=40+k*20,   //  guess 41 == '(', restore
f(S,n+1),S[n]=41+k*21,        // 44 == ',', guess 60 == '<',
f(S,-~n),S[n]=46-k-k);}       //  guess 62 == '>', restore
F(char*S){f(S,0);}               // main function, call helper function


Try it online!

• Can't you use GCC variable length arrays to get rid of the calloc ? Feb 3, 2018 at 20:15
• @TonHospel I would then, however, either need to convert the array to a pointer or introduce another index variable, which I do not know if it is worth it, since I am using *s++ at a few places. Feb 3, 2018 at 20:24
• char S[n],*s=S is still shorter than chars*s=calloc(n,1)` Feb 3, 2018 at 20:43
• @TonHospel I do not really know why, though it does not seem to work. Feb 3, 2018 at 20:53
• @ceilingcat Thank you. Aug 6, 2019 at 19:52