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

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

Can we use integers instead of strings? What about lists of digits or integers? — Zgarb, Feb 3, 2018 at 18:46

Lynn · Accepted Answer · 2018-02-02 21:38:35Z

7

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:

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

edited Feb 2, 2018 at 21:38

answered Feb 2, 2018 at 21:20

Lynn

68.1k11 gold badges130 silver badges279 bronze badges

Add a comment |

Neil · Accepted Answer · 2018-02-05 08:43:33Z

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.

You can save some bytes on escaping by using different characters — H.PWiz, 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

Zgarb · Accepted Answer · 2018-02-03 19:30:42Z

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.

Ton Hospel · Accepted Answer · 2018-02-03 20:30:59Z

2

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

edited Feb 3, 2018 at 20:30

answered Feb 3, 2018 at 13:00

Ton Hospel

14.8k1 gold badge21 silver badges45 bronze badges

Add a comment |

ngn · Accepted Answer · 2018-02-02 23:16:43Z

1

APL (Dyalog Classic), 55 53 bytes

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

Try it online!

edited Feb 2, 2018 at 23:16

answered Feb 2, 2018 at 22:55

ngn

15.2k2 gold badges42 silver badges87 bronze badges

Add a comment |

Οurous · Accepted Answer · 2018-02-03 02:03:40Z

1

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.

edited Feb 3, 2018 at 2:03

answered Feb 3, 2018 at 1:27

Οurous

8,0961 gold badge15 silver badges37 bronze badges

Add a comment |

Ton Hospel · Accepted Answer · 2018-02-03 13:07:48Z

1

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

answered Feb 3, 2018 at 13:07

Ton Hospel

14.8k1 gold badge21 silver badges45 bronze badges

Add a comment |

jrtapsell · Accepted Answer · 2018-02-04 22:18:27Z

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

Community · Accepted Answer · 2020-06-17 09:04:33Z

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!

Can't you use GCC variable length arrays to get rid of the calloc ? — Ton Hospel, 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. — Jonathan Frech, Feb 3, 2018 at 20:24
char S[n],*s=S is still shorter than chars*s=calloc(n,1) — Ton Hospel, Feb 3, 2018 at 20:43
@TonHospel I do not really know why, though it does not seem to work. — Jonathan Frech, Feb 3, 2018 at 20:53

Stack Exchange Network

Fill in the Bracks

Task

IO

Scoring

Test cases

9 Answers 9

Python 2, 135 bytes

Retina, 59 56 55 bytes

Retina, 74 71 70 bytes

Husk, 19 bytes

Explanation

Perl, 56 55 53 bytes

APL (Dyalog Classic), 55 53 bytes

Clean, 203 186 179 bytes

Perl, 56 bytes

Kotlin, 240 236 234 bytes

Beautified

Test

Edits

C (gcc), 315 bytes

C (gcc), 334 bytes (old version)

Explanation (old version)

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
string
balanced-string
or ask your own question.

Hot Network Questions

Fill in the Bracks

Task

IO

Scoring

Test cases

9 Answers 9

Python 2, 135 bytes

Retina, 59 56 55 bytes

Retina, 74 71 70 bytes

Husk, 19 bytes

Explanation

Perl, 56 55 53 bytes

APL (Dyalog Classic), 55 53 bytes

Clean, 203 186 179 bytes

Perl, 56 bytes

Kotlin, 240 236 234 bytes

Beautified

Test

Edits

C (gcc), 315 bytes

C (gcc), 334 bytes (old version)

Explanation (old version)

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golfstringbalanced-string or ask your own question.

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
code-golf
string
balanced-string
or ask your own question.