Fill in the Bracks

Question

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

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

Task

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 code-golf so answers will be scored in bytes with fewer bytes being better.

Test cases

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

Answer 1

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 2^N 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:

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

Answer 2

Retina, 59 56 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, 74 71 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.

Answer 3

Perl, 56 55 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

Answer 4

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.

Answer 5

APL (Dyalog Classic), 55 53 bytes

{a/⍨~×≢¨'\(\)|\[]'⎕r''⍣≡a←⊃∘'()[]'¨¨(⊂'".'⍳⍵)+,⍳2⊣¨⍵}

Try it online!

Answer 6

Clean, 203 186 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.

Answer 7

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

Answer 8

Kotlin, 240 236 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('[')
else->{d.add(0,it);1>0}}}&&d.size<1}

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('[')
                else -> {d.add(0,it);1>0}
            }
        } && 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('[')
else->{d.add(0,it);1>0}}}&&d.size<1}

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

Answer 9

C (gcc), 315 bytes

• Thanks to ceilingcat for 19 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!