27
\$\begingroup\$

There are a few questions on this site about balancing brackets, and checking whether brackets are balanced. I propose it's now time to use those balanced brackets for something!

In mathematics and programming, brackets are like bubbles, isolating everything inside form everything outside so that whatever's inside can do its thing in peace and whatever's outside only sees one object. However, a string of brackets is one-dimensional, while bubbles usually are at least two dimensional. That means that bubbles are free to move around one another as long as they never touch each other or cross between the inside and the outside of any other bubbles.

Challenge

The input is a string of matched brackets of a single type, either round (), square [], curly {} or angle <>. It's up to you what kind you want your program to accept, and a program that only accepts a single kind of brackets is accepted. (Imaginary bonus if your program can handle any of them, massive imaginary bonus points if it can handle all of them in the same input.) The input cannot contain anything between the brackets, although trailing whitespaces are allowed.

The output is all possible reorganisations (in arbitrary order, and including the original input) of those brackets that yields the same configuration of bubbles, with no two identical strings. That means that with an input of ()(), the output is also just ()(), even though it's technically two bubbles that could swap places. For the massive imaginary bonus, an input of {}[]() will of course lead to an output of 6 different elements / strings / lines.

Two configurations of bubbles are "the same" if you can make one into the other by moving bubbles around, without letting any bubble cross from inside another bubble to outside it, or from outside to inside. If you liken nested parentheses to trees (each matched pair is one node, and every matched pair within is a subnode, and each matched pair within there is a subnode of those again, and so on) where the subnodes of any given node are ordered, then a single configuration of bubbles is a tree where the nodes are unordered.

Any reasonable output format will do, like returning a list of strings or a list of list of single characters or a single string with some kind of whitespace, or printing to stdoutor stderr with some form of visible whitespace character (most commonly newline or space) between each reorganisation.

Trailing spaces for each reorganisation and trailing and preceeding newlines / empty list elements before and after the actual output is allowed. You should use the same kind of brackets in your output as you accept in your input. Apart from the brackets, newlines and spaces as specified here, and whatever separator you use, nothing should be printed (including invisible / zero-width characters).

The score is the number of bytes in the code; lowest count for each language wins. You may note whether you get an imaginary bonus, either regular or massive, but it doesn't affect your score. Actual bonuses are too hard to balance right.

Input-output examples

Example 1:

Input:

()(())

Output:

()(())
(())()

Example 2:

Input:

(()())()()

Output:

(()())()()
()(()())()
()()(()())

Example 3:

Input:

(()(()))()

Output:

((())())()
()((())())
(()(()))()
()(()(()))
\$\endgroup\$
  • \$\begingroup\$ Why can't we get ((())) in example 1? or ()()()? It seems like you are missing permutations for each input. \$\endgroup\$ – Sriotchilism O'Zaic Aug 10 '17 at 13:27
  • \$\begingroup\$ @WheatWizard That wouldn't give the same configuration of bubbles: one large bubble with two empty bubbles inside. \$\endgroup\$ – Arthur Aug 10 '17 at 13:28
  • \$\begingroup\$ @WheatWizard as far as I understand, you can't take a bubble from inside another bubble to the outside, or vice versa. \$\endgroup\$ – Grzegorz Puławski Aug 10 '17 at 13:35
  • \$\begingroup\$ @WheatWizard I added a small explanation. \$\endgroup\$ – Arthur Aug 10 '17 at 13:36
  • 7
    \$\begingroup\$ Btw, Welcome to PPCG! Nice first challenge! \$\endgroup\$ – Mr. Xcoder Aug 10 '17 at 14:08
4
\$\begingroup\$

CJam, 18 bytes

{~{_{{B}%e!}&}:B~}

Try it online!

-2 thanks to Business Cat.

Receives input as a string containing only []. Returns a list of permutations (empty lists are the same as empty strings in CJam, so instead of [] you'll be getting "").

\$\endgroup\$
  • \$\begingroup\$ Why is the output for [][] just ""? - Should the input be enclosed in an extra set of []? If so why is there an extra set of [] around what (maybe?) is the output for the aforementioned example? Also the question states "You should use the same kind of brackets in your output as you accept in your input. Apart from the brackets, newlines and spaces as specified here, and whatever separator you use, nothing should be printed", so I'm not sure a mix of [] and "" is acceptable. \$\endgroup\$ – Jonathan Allan Aug 11 '17 at 0:02
  • \$\begingroup\$ @JonathanAllan Yes I think you need to enclose [][] in an extra pair of []. For the others I'm not really sure they're invalid. \$\endgroup\$ – Erik the Outgolfer Aug 11 '17 at 8:35
  • \$\begingroup\$ I think you can do _{{B}%e!}& instead of _!!{{B}%e!}* \$\endgroup\$ – Business Cat Aug 15 '17 at 15:00
  • \$\begingroup\$ @BusinessCat Does & short-circuit or something? \$\endgroup\$ – Erik the Outgolfer Aug 15 '17 at 15:02
  • \$\begingroup\$ & runs the block only if the other value is truthy \$\endgroup\$ – Business Cat Aug 15 '17 at 15:04
4
\$\begingroup\$

Haskell, 227 210 208 205 bytes

import Data.List
l=last
a!x=init a++[l a++[x]]
h[]=[""]
h(x:y)=["("++z++")"++t|z<-v x,t<-h y]
g(a,r)x|x=='('=(a+1,l$(r++h[]):[r!x|a>0])|1>0=(a-1,l$r:[r!x|a>1])
v s=nub$h=<<(permutations.snd$foldl g(0,[])s)

Try it online!

This one was tough!

Golfed a little bit

Saved two bytes thanks to Laikoni

Save two bytes thanks to Bruce Forte

I'm not sure this works in every case. Some explanations:

  • a!x add the String x to the last list of String in a (a is of type [[String]])

  • snd$foldl(\(a,r)x->if x=='('then(a+1,last$(r++[[]]):[r!x|a>0])else(a-1,last$r:[r!x|a>1]) uses the shorter conditional to express the simple idea: split a String on root )(s. E.g. "(()(()))()" gives ["()(())", ""].

  • We need to process each part of the split, then to gather and join all the strings to get the correct output:

    1. h processs a list of parts: it applies v to the first part and combines the result to the process of the remaining parts.

    2. v aggregates the results for each permutation of the parts, and remove the duplicates.

To add a broader view: you have basically a tree (not a binary one) with empty nodes. Leave are (). You have to produce all the permutations of the branches for each node, but you may not take a branch from a node and put it on another node. I did a kind of depth first search.

\$\endgroup\$
  • \$\begingroup\$ You can drop the parentheses around init a. \$\endgroup\$ – Laikoni Aug 15 '17 at 19:06
2
\$\begingroup\$

Python 2, 353 350 331 Bytes

s=input()
f=lambda i,t=0:i+1if t<0else f(i+1,t-1)if"("<s[i+1]else f(i+1,t+1)
c=[(x,f(x))for x in range(len(s))if")">s[x]]
p=lambda l:[[]]if len(l)<1else[x for y in p(l[1:])for x in[y[:i]+[l[0]]+y[i:]for i in range(len(y)+1)]]
print[''.join(x)for x in p([s[c[x][0]:c[x][1]]for x in range(len(c))if all(c[x][1]>y[1]for y in c[:x])])]

Receives string of () as input and prints the result.

Try it here!

I avoided using itertools.permutations with help from Paolo's answer to this question.

Thank you to Business Cat for finding 3 bytes, and thank you to Mr. Xcoder for an incredible 19 bytes!

Explanation

  1. Create a list of tuples of the indices of each () pair in the input string.
  2. Drop any tuples from the list that are surrounded by another () pair.
  3. Slice the string at the indices of the remaining tuples.
  4. Make a list of each permutation of the list of slices.
  5. Join the list with a new line for printing.
\$\endgroup\$
  • \$\begingroup\$ I see a few bytes that could be shaved. You have some whitespace that can be removed, namely after print and at spots like i+1 if (could be i+1if). Also at one spot you have y[0:i], you can omit the 0. \$\endgroup\$ – Business Cat Aug 15 '17 at 22:39
  • \$\begingroup\$ Thank you, @BusinessCat! My IDE complains on a few of those, so I'm still learning some of the code golf tricks. \$\endgroup\$ – Solvation Aug 16 '17 at 14:20
  • \$\begingroup\$ 342 bytes (-8 bytes) by reordering some conditionals in order to remove whitespace. \$\endgroup\$ – Mr. Xcoder Aug 29 '17 at 9:27
  • \$\begingroup\$ 340 bytes (-10 bytes) by using lexicographical comparison over equality checking. \$\endgroup\$ – Mr. Xcoder Aug 29 '17 at 9:29
  • \$\begingroup\$ 331 bytes (-19 bytes) because the challenge allows returning a list of Strings. yay, we beat Mathematica :-) \$\endgroup\$ – Mr. Xcoder Aug 29 '17 at 9:31
2
\$\begingroup\$

JavaScript (Firefox 30-57), 222 bytes

s=>(g=a=>a+a?[for(x of g(a[0]))for(y of a.keys())for(z of g(a.slice(1)))(z.splice(y,0,x),z)]:[a])(eval(`[${s.replace(/]\[/g,`],[`)}]`)).map(g=a=>`[`+a.map(g).join``+`]`).sort().filter(s=>t<(t=s),t=``).map(s=>s.slice(1,-1))

Takes [] strings. Explanation:

s=>(                                Inner function to permute an array
 g=a=>a+a?[                         If array is not empty
  for(x of g(a[0]))                 Permute the first element of the array
  for(y of a.keys())                Generate a list of insertion points
  for(z of g(a.slice(1)))           Permute the rest of the array
  (z.splice(y,0,x),z)]:             Make all possible permutations
  [a]                               Otherwise return a list of an empty array
)(eval(`[${                         Convert the string to a nested array
   s.replace(/]\[/g,`],[`)}]`)      ... inserting commas where necessary
).map(                              Process the results
 g=a=>`[`+a.map(g).join``+`]`       Recursively convert back to string
).sort().filter(s=>t<(t=s),t=``     Check for duplicates
).map(s=>s.slice(1,-1))             Remove outer `[]`s
\$\endgroup\$
0
\$\begingroup\$

Mathematica, 337 bytes

Not to get code-golf points, but to show the usage of Permutations and Distribute in this problem. There may be better approaches, though.

(seq : sequence, alt : alternatives)

SetAttributes[alt, {Flat, OneIdentity}]
StringTake[
  StringReplace[ToString[
    ToExpression["{" <> StringReplace[#, "}{" -> "},{"] <> "}"]
        /. List -> Permutations@*seq
       /. List -> alt
      /. seq -> (Distribute[seq@##, alt] &)
     /. {seq -> List, alt -> Alternatives}],
   {", " -> "", "} | {" -> "\n"}],
  {2, -2}] &

Take input as a string, using curly brackets { and }. Output a multi-line string.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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