21
\$\begingroup\$

A balanced string is a string of parentheses () so that every parenthesis is can be matched with another one. More rigorously they are the strings spanned by this grammar:

S → (S)S | ε

We can turn a string "inside out" by:

  • Switching all occurrences of ( and ) with each other

  • Moving characters from the front of the string to the back until the string is balanced again.


Lets do an example.

We start with the balanced string:

(()(())())

We then switch the parens to make

))())(()((

Then move characters from the front of the string to the back of the string until the string is balanced.

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

Thats our result!


Note that some strings can be turned inside out in multiple ways, for example the string

(()())

When turned inside out can be either:

()(())

or

(())()

However every string has at least one solution.

Task

Write a program to take a balanced string as input and output that string turned inside out. In cases where there may be multiple valid outputs you need only output one of them. You may use a different brace type (<>,[] or {}) if you so wish.

This is a competition so you should aim to minimize your size of your source code, as measured by bytes.

Test Cases

(()())     -> ()(()), (())()
(()(())()) -> (()(())())
((())())() -> (()(()()))
\$\endgroup\$
4
  • \$\begingroup\$ Is it guaranteed that there is always a solution? \$\endgroup\$
    – Luis Mendo
    Jul 4, 2017 at 14:45
  • \$\begingroup\$ @LuisMendo Yes, I have proven this. If you would like to see the proof, feel free to ping me in chat. \$\endgroup\$
    – Wheat Wizard
    Jul 4, 2017 at 14:48
  • \$\begingroup\$ Thanks. It is sufficient for me to know that. Maybe you should write it into the challenge, otherwise you would need to define what to output if no solution \$\endgroup\$
    – Luis Mendo
    Jul 4, 2017 at 15:00
  • \$\begingroup\$ related \$\endgroup\$
    – 0xffcourse
    Jul 4, 2017 at 15:01

14 Answers 14

9
\$\begingroup\$

Haskell, 124 120 119 117 113 110 109 106 105 104 101 98 bytes

4 bytes saved thanks to bartavelle!

3 bytes saved thanks to Zgarb

1 byte saved thanks to Peter Taylor

Here's a solution I worked out in Haskell. Its ok right now pretty good thanks to some help I received, but I'm looking to make this shorter, so feedback/suggestions are appreciated.

until(!0)g.map d
_!1=1<0
('(':a)!x=a!(x-1)
(_:a)!x=a!(x+1)
_!_=1>0
g(a:b)=b++[a]
d '('=')'
d _='('

Try it online!

Explanation

This program defines 4 functions, the first (!) determines if a string is balanced. Its defined as follows:

_!1=1<0
('(':a)!x=a!(x-1)
(_:a)!x=a!(x+1)
_!_=1>0

This check assumes that the input has an equal number of open and close parens thanks to a suggestion from Peter Taylor.

The next g will rotate the string once.

g(a:b)=b++[a]

Then we have d which simply takes a paren and mirrors it

d '('=')'
d _='('

Finally we have the function we are concerned with. Here we use a pointfree representation of until(!0)g composed with map d, which maps d to the input and applies g until the result is balanced. This is the exact process described in the question.

until(!0)g.map d
\$\endgroup\$
10
  • 1
    \$\begingroup\$ You can scrap a few bytes with g x@(a:b)|x!0=x|1>0=g$b++[a] and removing the parens for d '('=')'. \$\endgroup\$
    – bartavelle
    Jul 4, 2017 at 15:35
  • \$\begingroup\$ @bartavelle Removing the parens for d causes a compiler error, believe me I've tried. But the first suggestion is welcome. Thanks! \$\endgroup\$
    – Wheat Wizard
    Jul 4, 2017 at 15:37
  • 1
    \$\begingroup\$ You can save another byte in ! because you don't need to handle cases where the string has an unequal number of open and close parentheses, so you can swap the first two cases and have _!1=1<0 []!_=0<1 \$\endgroup\$ Jul 4, 2017 at 15:48
  • 1
    \$\begingroup\$ Use until to shorten g: TIO \$\endgroup\$
    – Zgarb
    Jul 4, 2017 at 16:03
  • 2
    \$\begingroup\$ I think there should be a decent saving by making d map '(' to (-1) and anything else to 1, and then the two longest cases of ! can be combined to (i:a)!x=a!(x+i). The top level structure then needs reworking to push map d into the until condition, and I have to run so I haven't got time right now to figure out what combinators are required to glue it all together. \$\endgroup\$ Jul 4, 2017 at 16:29
7
\$\begingroup\$

SOGL V0.12, 12 11 bytes

↔]»:l{Ƨ()øŗ

Try it Here!

Explanation:

↔            mirror characters
 ]           do ... while the top of stack is truthy
  »            put the last letter at the start
   :           duplicate it
    l{         length times do
      Ƨ()        push "()"
         ø       push ""
          ŗ      replace ["()" with ""]
             if the string left on stack is empty (aka all matched parentheses could be removed), then stop the while loop

Note: l{ could be replaced with ( for 10 bytes, but, sadly, it isn't implemented.

\$\endgroup\$
2
  • \$\begingroup\$ Are you sure that mirroring the characters works? I don't know exactly what that means but my intuition tells me that it also reverses the order of the characters which, I don't think would work. \$\endgroup\$
    – Wheat Wizard
    Jul 4, 2017 at 15:04
  • 1
    \$\begingroup\$ @Olmman It was intended to reverse the characters, but doesn't (which saves a byte here!). It's on V0.13s line-up to change trough. Example \$\endgroup\$
    – dzaima
    Jul 4, 2017 at 15:04
5
\$\begingroup\$

CJam (20 chars)

q1f^0X${~_}%_:e>#)m<

Online demo

or for the same char count

q1f^_,,{0W$@<~}$W=m<

Online demo

Dissection

The two versions have a common header and footer

q1f^    e# Read input and toggle least significant bit of each character
        e# This effectively swaps ( and )

m<      e# Stack: swapped_string index
        e# Rotates the string to the left index characters

Then the bit in the middle obviously calculates how far it's necessary to rotate. Both of them use evaluation and rely on ( being the CJam decrement operator and ) being the increment operator.

0X$     e# Push 0 and a copy of the swapped string
{~_}%   e# Map: evaluate one character and duplicate top of stack
        e# The result is an array of the negated nesting depth after each character
_:e>    e# Copy that array and find its maximum value
#       e# Find the first index at which that value occurs
)       e# Increment

vs

_,,     e# Create array [0 1 ... len(swapped_string)-1]
{       e# Sort with mapping function:
  0W$@  e#   Rearrange stack to 0 swapped_string index
  <~    e#   Take first index chars of swapped_string and evaluate
}$      e# The result is an array of indices sorted by the negated nesting depth
W=      e# Take the last one
\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6), 111 105 bytes

(Saved 2 bytes thanks to @CraigAyre, 2 bytes thanks to @PeterTaylor, 2 bytes thanks to @Shaggy.)

s=>(r=[...s].map(c=>'()'[c<')'|0])).some(_=>r.push(r.shift(i=0))&&!r.some(c=>(i+=c<')'||-1)<0))&&r.join``

Ungolfed:

s=>(
  r=[...s].map(c=>'()'[c<')'|0]),  //switch "(" and ")"
  r.some(_=>(
    r.push(r.shift(i=0)),          //move last element to beginning of array, initialize i
    !r.some(c=>(i+=c<')'||-1)<0)   //check if balanced (i should never be less than 0)
  )),
  r.join``
)

Test cases:

let f=

s=>(r=[...s].map(c=>'()'[c<')'|0])).some(_=>r.push(r.shift(i=0))&&!r.some(c=>(i+=c<')'||-1)<0))&&r.join``

console.log(f('(()())'));      // ()(())
console.log(f('(()(())())'));  // (()(())())
console.log(f('((())())()'));  // (()(()()))

\$\endgroup\$
0
3
\$\begingroup\$

Retina, 46 38 bytes

T`()`)(
(.*?)(((\()|(?<-4>\)))+)$
$2$1

Try it online! Link includes test cases. Edit: Saved 8 bytes with help from @MartinEnder. The first stage simply transposes the parentheses, while the second stage looks for longest suffix that's a valid balanced prefix, which apparently is a sufficient condition for the rotation to be fully balanced. The balancing is detected using balancing groups. The construct ((\()|(?<-4>\)))+ matches any number of (s plus any number of )s as long as we have already (<-4>) seen as many (s. Since we're only looking for a valid prefix we don't have to match the remaining )s.

\$\endgroup\$
5
  • \$\begingroup\$ Normally, instead of repeating both parentheses, you just put them in an alternation, which saves a byte ((\()|(?<-2>\))). But your attempt just inspired me to find a completely new approach that saves another two: (?<-1>(\()*\))+. This will certainly come in handy in the future, so thank you. :) \$\endgroup\$ Jul 5, 2017 at 7:45
  • \$\begingroup\$ It's even shorter to determine the rotation by matching the first suffix through which you can reach the end of the string without getting a negative stack depth: tio.run/… \$\endgroup\$ Jul 5, 2017 at 7:53
  • \$\begingroup\$ @MartinEnder I originally tried an alternation but I couldn't get it to work at the time, but I fail to see how (?<-1>(\()*\))+ even works, since it seems to want to pop from the 1 stack before having actually matched anything... \$\endgroup\$
    – Neil
    Jul 5, 2017 at 8:44
  • \$\begingroup\$ @MartinEnder As it happens, the alternation version seems to be golfer when it comes to matching balanced prefixes. \$\endgroup\$
    – Neil
    Jul 5, 2017 at 8:55
  • 1
    \$\begingroup\$ The actual popping happens at the end of the group, not the beginning. Good point with the alternation to avoid the duplicate \(* though. \$\endgroup\$ Jul 5, 2017 at 8:59
2
\$\begingroup\$

PHP, 110 108 bytes

for($s=$argn;;$p?die(strtr($s,"()",")(")):$s=substr($s,1).$s[$i=0])for($p=1;$p&&$c=$s[$i++];)$p-=$c<")"?:-1;

Run as pipe with -nR or test it online.

breakdown

for($s=$argn;               # import input
    ;                       # infinite loop
    $p?die(strtr($s,"()",")(")) # 2. if balanced: invert, print and exit
    :$s=substr($s,1).$s[$i=0]   #    else: rotate string, reset $i to 0
)                               # 1. test balance:
    for($p=1;                   # init $p to 1
        $p&&$c=$s[$i++];)       # loop through string while $p is >0
        $p-=$c<")"?:-1;             # increment $p for ")", decrement else
\$\endgroup\$
2
\$\begingroup\$

Python 3, 112 103 101 bytes

-2 bytes thanks to @Mr.Xcoder

k=y=input().translate(' '*40+')(')
while k:
 k=y=y[1:]+y[0]
 for _ in y:k=k.replace('()','')
print(y)

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ 101 bytes? Not sure it works \$\endgroup\$
    – Mr. Xcoder
    Jul 4, 2017 at 17:54
2
\$\begingroup\$

Octave, 62 bytes

@(s)")("(x=hankel(s,shift(s,1))-39)(all(cumsum(2*x'-3)>=0)',:)

Try it online!

A function that takes the string as input and prints all results.

Explanation:

           hankel(a,shift(a,1))                                % generate a matrix of n*n where n= length(s) and its rows contain incresing circulraly shifted s
         x=...                 -39                             % convert matrix of "(" and ")" to a mtrix of 1 and 2
    ")("(x                        )                            % switch the parens
                                               2*x'-3          % convert [1 2] to [-1 1]
                                        cumsum(      )         % cumulative sum along the rows
                                    all(              >=0)'    % if all >=0
                                   (                       ,:) % extract the desired rows
\$\endgroup\$
2
\$\begingroup\$

Mathematica, 78 bytes

""<>{"(",")"}[[2ToCharacterCode@#-81//.x_/;Min@Accumulate@x<0:>RotateLeft@x]]&
\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6), 97 bytes

f=(s,t=s,u=t.replace(')(',''))=>u?t==u?f(s.slice(1)+s[0]):f(s,u):s.replace(/./g,c=>c<')'?')':'(')

Works by recursively rotating the input string until its transpose is balanced, then transposing it.

\$\endgroup\$
1
  • \$\begingroup\$ Simply beautiful. \$\endgroup\$ Jul 5, 2017 at 10:17
1
\$\begingroup\$

APL (Dyalog Unicode), 35 30 bytes

Golfed a new approach thanks to @Adám

1⌽⍣{2::0⋄1∊⍎⍕1,¨⍺}')('['()'⍳⎕]

Try it online!

Golfing is in progress.

Explanation

'()'⍳⎕              Find the index of each character of the input in the string '()'
                    (this is 1-indexed, so an input of '(())()' would give 1 1 2 2 1 2)
')('[...]           Find the index of the vector in the string ')('
                    This essentially swaps ')'s with '('s and vice versa
⍣                   On this new string, do:
 1⌽                   rotate it one to the left
                    Until this results in 1:
 1,¨⍺                 Concatenate each element of the argument with a 1
                      This inserts 1 one before each parenthesis
 ⍕                    Stringify it
 ⍎                    And evaluate it, if the parentheses are balanced, this produces no errors
 1∊                   Check if 1 belongs to evaluated value
                      If the parentheses were not matches during ⍎, this causes a syntax error
 2::0                 This catches a syntax error and returns 0
                      Essentially this code checks if the brackets are balanced or not
\$\endgroup\$
0
\$\begingroup\$

Python 2, 99 bytes

r=[0];S=''
for c in input():b=c>'(';r+=[r[-1]+2*b-1];S+=')('[b]
n=r.index(min(r))
print S[n:]+S[:n]

Try it online!

In function form for easy test cases:

Python 2, 108 bytes

def f(s):
 r=[0];S=''
 for c in s:b=c>'(';r+=[r[-1]+2*b-1];S+=')('[b]
 n=r.index(min(r))
 return S[n:]+S[:n]

Try it online!

This uses a slightly different approach - instead of recursively rotating the string, if we think of the parens as incrementing and decrementing some balance counter, then a balanced string must never have a total sum of increments - decrements that is less than 0.

So we take

(()(())())

invert the parens:

))())(()((

and convert it to a list of sums of increments/decrements:

[-1,-2,-1,-2,-3,-2,-1,-2,-1,0]

-3 is the minimum at index 4 (zero based); so we want to shift by that index+1. This guarantees that the cumulative increment/decrement will never be less than 0; and will sum to 0.

\$\endgroup\$
2
  • \$\begingroup\$ On my phone so I can't test, but could you do r=0, instead of r=[0]? \$\endgroup\$
    – Cyoce
    Jul 5, 2017 at 19:10
  • \$\begingroup\$ If you're going with @Cyoce's suggestion, you will need to replace r+=[r[-1]+2*b-1] with r+=r[-1]+2*b-1, as well \$\endgroup\$
    – ovs
    Jul 6, 2017 at 4:49
0
\$\begingroup\$

Clojure, 118 bytes

#(loop[s(map{\(\)\)\(}%)](let[s(conj(vec(rest s))(first s))](if(some neg?(reductions +(map{\( 1\) -1}s)))(recur s)s)))

Returns a sequence of characters, so I'd call it like this:

(apply str (f "(()(())())"))
; "(()(())())"

First flips brackets, then loops as long as the cumulative sum of bracket count goes negative at some point of the sequence.

\$\endgroup\$
0
\$\begingroup\$

brainfuck, 82 bytes

,[++[->->++<<]-[--->+>-<<]>-->+[-[-<<+>>>>+<<]],]+[<<]>>>[.[-]>>]<[<<]<[<<]>>[.>>]

Try it online!

Explanation

With each character read, a counter is modified as follows:

  • The counter starts at 0.
  • After each ), the counter increases by 1.
  • After each (, the counter decreases by 1, unless the counter was 0, in which case the counter is unchanged.

Each prefix is a valid suffix of a balanced string (after inversion) if and only if this counter is 0. This code uses the longest such prefix to form the output.

,[                   Take input and start main loop
                     The cell one space right is the output cell (0 at this point),
                     and two spaces right is a copy of the previous counter value
  ++                 Add 2 to input
  [->->++<<]         Negate into output cell, and add twice to counter
  -[--->+>-<<]       Add 85 to output cell, and subtract 85 from counter
  >-->+              Subtract 2 from output cell and add 1 to counter
                     The output cell now has (81-input), and the counter has been increased by (2*input-80)
  [-[-<<+>>>>+<<]]   If the counter is nonzero, decrement and copy
,]
+[<<]                Go to the last position at which the counter is zero
>>>                  Go to following output character
[.[-]>>]             Output from here to end, clearing everything on the way
                     (Only the first one needs to be cleared, but this way takes fewer bytes)
<[<<]                Return to the same zero
<[<<]>>              Go to beginning of string
[.>>]                Output remaining characters
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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