Rotate brackets until they're balanced

Take the string of brackets ]][][[. When you rotate it to the right once, you get []][][. If you rotate it again, you get [[]][]. All brackets in this string are balanced.

Your program (or function) will be given a string of brackets, represented in any reasonable format (including using other things in place of the brackets, like -1 and 1). The numbers of opening and closing brackets will always be equal, so [ or ][] won't be given as inputs.

Output should be a rotation of those brackets which is balanced. You can check this by repeatedly removing pairs of brackets ([]). With a balanced string of brackets, none will be left over.

Rotating a string to the right involves taking the last character, and moving it to the beginning. For example, 01234567 rotated right 3 times would be 56701234. The direction of rotation doesn't matter, but no brackets should be added, discarded, mirrored, etc. If multiple solutions are possible, such as [][[]] or [[]][], you can return any of them.

Test Cases:

[]          ->  []
]][[        ->  [[]]
[][]][      ->  [[][]]
][][[]      ->  [[]][] OR [][[]]
[[[][][]]]  ->  [[[][][]]]
]]][][][[[  ->  [[[]]][][] OR [][[[]]][] OR [][][[[]]]


Other:

This is , so shortest answer in bytes per language wins!

• Can I return all valid answers? Commented Mar 25, 2021 at 3:01
• It took me a while to figure out what on earth "rotation" meant. And I still don't get why you call this operation rotation. You really should explain what this means. Commented Mar 25, 2021 at 12:15
• @WheatWizard "Rotation" seems to be a pretty common name for this, although I'll add an explanation of what I mean. Commented Mar 25, 2021 at 13:25
• @xigoi I'm 99% sure all inputs can be solved. For any input, imagine replacing any already balanced parts with a .. The example input would become ]].[[. You'll always end up with /]*[*/, with some dots interwoven occasionally. You can always then rotate that to be /[*]*/, which is balanced. Commented Mar 25, 2021 at 13:26
• Here's a proof: Replace [ with +1 and ] with -1. Consider instead of a string as a ring of these integers. Choose an arbitrary point and starting with zero pass around the ring adding each integer to the sum. (this will return to zero). If the sum never goes below 0 you are fine, if it does choose the minimum point and start from there instead. Now it will never go below zero, so that is where you begin / end the string. Commented Mar 25, 2021 at 14:19

Husk, 7 5 bytes

ṙ¹η◄∫


Try it online!

No loops, no recursion, just a straightforward simple operation. Encodes [ as 1 and ] as -1.

ṙ¹η◄∫
ṙ¹       Rotate the list left by
η        the (1-based) index
◄         of the minimum
∫      in the list of cumulative sums



This comes from observing that the list of cumulative sums will have a minimum at the point where the most closed brackets are preceding open brackets. By moving all the previous brackets to the end, we can guarantee that there won't be any prefix containing more closed than open brackets.

Ωȯ¬▼∫ṙ1


Try it online!

Encodes [ as 1 and ] as -1, following HyperNeutrino's idea to use the cumulative sum, but then uses an additional observation:

Since we are working with an equal number of open and closed brackets, the total sum will always be 0. If at any point the string is unbalanced, the cumulative sum at that point will be negative. From this, we can say that a string will be balanced if the minimum of its cumulative sum is exactly 0.

Ω(¬▼∫)ṙ1
ṙ1    Rotate by 1
Ω           until
▼         the minimum
∫        of the cumulative sums
¬          is 0

• A similar approach in Jelly comes out at 4 bytes as Jelly has a builtin for "Index of maximal elements" Commented Mar 25, 2021 at 5:01

Raku, 42 34 bytes

{({S/.//~$/}...{try !.EVAL}).tail}  Try it online! In Raku, a set of balanced square brackets is entirely valid syntax, so we can simply rotate the string until it EVALs successfully, and take the last element. Explanation { } # Anonymous codeblock taking a string {S/.// } # Remove the first character ~$/                         # And add it to the end
(          ...            )        # Repeat until
{try !.EVAL}            # The program can be eval'd
# This returns ![] (true) if successful
.tail   # Return the last element


$1 by 1  The drop<>take rotates by using <> to concatenate the list with elements dropped from the start and the list with that many elements taken from the start. The (<>) is imported in the TIO link but is available in base starting with 8.4.1; see this tip. We could also do tail<>take 1 for the same length. Jelly, 8 bytes ṙJÄ-eƊÐḟ  Try it online! -2 bytes thanks to ChartZ Belatedly + 1 byte saved from being allowed to return all valid configurations instead of just one Explanation ṙJÄ-eƊÐḟ Main Link ṙ Rotate by J [1, 2, ..., len(input)] Ðḟ Filter: keep all elements where the following is falsy (in this case, a list of all zeroes): Ä Cumulative Sum e equal to (vectorize) - -1  Basically, keep all arrangements where the cumulative sum is never equal to -1 (clever observation from ChartZ that since the cumsum changes by 1 each time and starts at 0, if any value is negative, then there must be a -1 somewhere, so rather than doing <0$ we can do -e. and then also that the filter quick accepts a list of zeroes as falsy so I don't have to use the any atom)

• I've tried golfing this myself but I don't know Jelly well enough: isn't it possible (and wouldn't it be shorter) to code it like while(any of the cumulative sum is negative)(rotate by 1)?
– Leo
Commented Mar 25, 2021 at 3:34
• @Leo Probably not; the way Jelly handles while loops, and the value that each part of the loop handles, is often difficult to make short Commented Mar 25, 2021 at 3:55
• @Leo Your idea saved me 10 bytes in my J answer. Commented Mar 25, 2021 at 3:58
• 8 bytes Commented Mar 25, 2021 at 4:04
• Also 8 bytes, porting @Jonah's J answer (uses -1 for open brackets) Commented Mar 25, 2021 at 4:24

Python 3.8, 57 bytes

f=lambda s,t=1:s*all((t:=t+n)for n in s)or f(s[1:]+s[:1])


Try it online!

Takes in a list of 1's and -1's.

• Oh, this newly introduced me to the ":=" syntax. Very useful for some code golfing tasks.
– Emil
Commented Mar 26, 2021 at 10:22
• @Emil Yup, see this tip for some more ideas on using it.
– xnor
Commented Mar 26, 2021 at 10:27

APL (Dyalog Unicode), 11 bytes

(⊢⌽⍨1∊+\)⍣≡


Try it online!

An APL port of Jonah's golfed answer, which in turn uses Leo's observation. Like Jonah's, the input is -1 for [ and 1 for ].

How it works

(⊢⌽⍨1∊+\)⍣≡  ⍝ Input: a vector of -1s and 1s, -1 for open and 1 for close
(...)⍣≡  ⍝ Repeat until it does not change...
1∊+\     ⍝   1 if cumulative sum has a 1, 0 otherwise
⊢⌽⍨      ⍝   Rotate left ^ times (so it stops when the above result is zero)

• See my last idea which shaved off 2 more bytes for me, and may help your APL answer too. (EDIT: looks like some of the other answers had this idea too...) Commented Mar 25, 2021 at 10:44

Scratch 3.0, 49 blocks/407 bytes

As SB Syntax:

define C
set[T v]to(0
set[i v]to(1
set[Y v]to(1
repeat(length of[S v
if<(item(i)of[S v])=[a]>then
set[T v]to((T)+(1
else
set[T v]to((T)-(1
end
if<(T)<(0)>then
set[Y v]to(0)
end
set[i v]to((i)+(1
define(s
set[i v]to(1
repeat(length of(s
set[i v]to((i)+(1
end
C
repeat until<(Y)=(1
set[t v]to(item(length of[S v])of[S v]
delete(length of[S v])of[S v
insert(t)at(1)of[S v
C
end
say(S


Because rotating a string in Scratch/bracket matching is a really good idea. Use a for opening brackets and b for closing brackets.

Explained

define C -- Helper function used for checking if the brackets are balanced
set[T v]to(0
set[i v]to(1 --- T = running tally, i = string index, Y = return value
set[Y v]to(1
repeat(length of[S v
if<(item(i)of[S v])=[a]>then
set[T v]to((T)+(1
else                 ---- Opening brackets (a) increment the tally by 1. Closing brackets (b) decrement the tally by 1. If the brackets are balanced, this tally will never go below 0, as the brackets will cancel each other out
set[T v]to((T)-(1
end
if<(T)<(0)>then
set[Y v]to(0)
end
set[i v]to((i)+(1

define(s --- Main function
set[i v]to(1
repeat(length of(s
add(letter(i)of(s))to[S v] --- Place every character of the input into a list
set[i v]to((i)+(1
end
C ---- Check if the inital input is balanced
repeat until<(Y)=(1
set[t v]to(item(length of[S v])of[S v]  --- Rotate the string once
delete(length of[S v])of[S v
insert(t)at(1)of[S v
C   ---------- And check each rotation
end
say(S


J, 40 29 19 18 15 14 13 bytes

|.~1+0{&\:+/\


Try it online!

-11 after applying HyperNeutrino's scan sum idea

-10 after reading Leo's comment to HyperNeutrino: while(any of the cumulative sum is negative)(rotate by 1)

-3 thanks to a clever observation by Bubbler

Takes input as a list of integers, where [ = _1 and ] = 1 -- reversing the more natural order saves 1 byte.

how

• |.~ Rotate by...
• 1+ 1 plus...
• 0{ the first element of...
• \: the grade down of...
• +/\ the scan sum.

That is, take the index of the max element of the scan sum, add one to it, and rotate by that amount.

• -1 with repeat-bind trick: Try it online! Commented Mar 25, 2021 at 4:01
• Actually you can just use the test itself as the rotate count, so it is 15 bytes. Commented Mar 25, 2021 at 4:02

Perl 5, 30 bytes

$_=chop.$_ while s/<(?R)*>//gr


Try it online!

Uses <> as the bracket delimiters.

The regex s/<(?R)*>//gr recursively substitutes bracket patterns with the empty string, and instead of mutating the string returns the final value. If this is empty, then all our brackets are fully matched and since the empty string is falsy, the loop stops. Else we rotate the string one using the construction $_=chop.$_.

-1 thanks to Dom Hastings by replacing the ugly s/.//,$_.=$& with the much more elegant $_=chop.$_.

• Nice! I was hoping to find a way to use while!eval but I can't come up with a combination of chars that works... You can save 1 byte though, using $_=chop.$_: Try it online! Commented Mar 25, 2021 at 10:26
• @DomHastings That's a nice improvement! Commented Mar 25, 2021 at 11:55

JavaScript (Node.js), 53 bytes

f=a=>([c,...r]=a).some(v=>(c+=v)>=0)?f([...r,a[0]]):a


Try it online!

Input array of $$\\pm 1$/extract_tex], output rotated array. Thanks user81655 for -1 byte. • 53 bytes Commented Mar 25, 2021 at 7:03 Javascript, 52 bytes (Sorry if i formatted my answer wrong, i'm brand new here.) Golf version a=>{while(t=0,a.some(v=>(t+=v)<0))a.push(a.shift())}  More readable version (and you can try it out) function rotateArrayUntilBalanced(array) { var total; // Create a total variable while (total=0,array.some(value => (total += value) < 0)) { // This tests if the array is still unbalanced array.push(array.shift()); // Shift array right } } button.onclick = function () { const array = input.value.split('').map(value => (value == '[' ? 1 : -1)); rotateArrayUntilBalanced(array); resultArea.innerText = array.map(value => (value == 1 ? '[' : ']')).join(''); } <input id="input" placeholder="brackets go here"> <button id="button">Go</button> <div id="resultArea"></div> • try it online says Unexpected token while here:Try it online! Commented Mar 25, 2021 at 14:39 • Welcome to Code Golf! Your ungolfed version looks cool, but the golfed version doesn't seem to work. I think you need some curly brackets around it. Commented Mar 25, 2021 at 14:44 • Thank you. I fixed the problem, and i'ts now 52 bytes. BTW, bytes is just the number of characters, right? Commented Mar 25, 2021 at 15:48 • @asdf3.14159 In most cases, yes. If you're using non-ASCII characters (things you can't type on a US keyboard), there might be extra bytes (for example, £ (2 bytes) or ™ (3 bytes)) Commented Mar 26, 2021 at 0:18 • Also, some golfing languages have their own code pages, known as SBCS's (Single Byte Character System). Basically, this means that any character that would be used in a program is encoded as a single byte - with the drawback that characters outside of the code page cannot be encoded, and including them would mean you would have to score your answer based on a code page that can encode them, like Unicode, possibly adding bytes. Commented Mar 26, 2021 at 1:07 R, 80 bytes function(x){while(min(cumsum(92-(y=utf8ToInt(x)))))x=intToUtf8(c(y[-1],y[1]));x}  Try it online! Input is string of square-brackets. Alternatively, a port of Leo's Husk answer using a vector of 1s & -1s as input is only 48 bytes. JavaScript (Node.js), 74 bytes a=>eval("try{Function(a.replace(/]/g,'-1]'));a}catch{f(a.slice(1)+a[0])}")  Try it online! Convert each ] to -1], and try to check if there are any syntax error... This is ES2019. Python 3, 74 72 bytes f=lambda a:min(sum(a[:i])for i in range(len(a)))<0and f([a.pop()]+a)or a  Try it online! Takes input as a list of 1s and -1s, with 1 denoting [ and -1 denoting ]. For a valid bracket sequence, no prefix of the array will have a sum less than 0, so if the current array is not a valid bracket sequence, rotate it by 1 and try again. -2 bytes thanks to tsh • [:i+1] -> [:i] – tsh Commented Mar 25, 2021 at 6:19 Python 3, 63 bytes lambda a:min((sum(a[:i]),a[i:]+a[:i])for i in range(len(a)))[1]  Try it online! JavaScript (Node.js), 76 bytes a=>a.map(v=>(++i,c+=v)<m?0:o=[...a.slice(i),...a.slice(0,i,m=c)],i=c=m=0)&&o  Try it online! Input an array of $$\\pm 1$$/extract_tex]. Count each [ as $$\-1\$$, each ] as $$\+1\$$. Find out the position $$\p\$$ where $$\\sum_{i=0}^{p}a_i\$$ has max value. And rotate it there. I believe this approach may be golfed more bytes, but I didn't find out an obvious way. • Sorry that I had to split my previous submission into two post... – tsh Commented Mar 25, 2021 at 6:40 Red, 50 bytes func[s][while[error? try[load s]][move s tail s]s]  Try it online! Explanation Red uses brackets for its block! datatype so every set of balanced brackets is a valid value. That's why I'm trying to load the string holding the brackets (that is to convert the string to a Red value) and if this throws an error, I move the leading character of the string at the tail. 05AB1E, 9 7 bytes -2 thanks to @Command Master. ηOWk>._  Try it online! Takes input as a list, with 1 for [ and -1 for ]. ηOWk>._ # full program ._ # rotate... # implicit input... ._ # left... > # 1... k # -based index of... W # maximum... η # cumulative... O # sum... η # of... # implicit input... k # in... η # cumulative... O # sums... η # of... # implicit input... ._ # times # implicit output  >._ can also be ._À with no change in functionality. As a bonus, this works too! ηOWk> ._.  • Å»+} -> ηO for -2 Commented Mar 26, 2021 at 9:22 • @CommandMaster Oh yeah! However, shouldn't that be a 4 byte save since ηO code should be put in its place? :P Commented Mar 26, 2021 at 16:53 JavaScript (Node.js), 110 108 bytes x=>{for(s=x,i=0;++i<x.length;s=s.slice(1)+s[0])for(y=0,h=s;++y<s.length;h=h.replace('[]',''))if(!h)return s}  Try it online! This was very tricky, but I managed to abuse for loops a lot. Explained: x=>{ // declare function for( //repeat: s=x,i=0; //initiate string and looper to 0 ++i<x.length; //repeat while i+1 is less than string length, and increment i at the same time s=s.slice(1)+s[0] // loop string along by 1 ) for( //repeat: y=0,h=s; //initiate looper, and string to use to check if matching ++y<s.length; //repeat while incremented y is less than string length (since there are only so many brackets) h=h.replace('[]','')// remove a single occurrence of [] from h - if this is repeated enough and brackets match, it will eventually be empty. ) if(!h)return s // if h is an empty string, this means s's brackets match, so return s. No point in dealing with invalid input since it will always be valid. }  Ruby, 47 bytes ->s{s.rotate (0..s.size).min_by{|r|s[0,r].sum}}  Try it online! K (Kona), 13 bytes {(1+*>+\x)!x}  Try it online! Uses -1 for [ and 1 for ]. A port of Adám's APL answer Retina 0.8.2, 28 bytes (.*?)(((<)|(?<-4>>))+) 21  Try it online! Takes input as a string of <s and >s but link includes test suite which maps [ and ] for convenience. Explanation: This is a fairly direct application of .NET balancing groups. The < character is captured into group 4, which works like a stack. Meanwhile, > characters can only be matched by popping <s from the 4 stack. This ensures that we take the first suffix of the input that does not contain a mismatched >. (It can of course have a mismatched < but that will be matched by a > in the prefix.) It then remains to exchange the prefix with the suffix. PHP < 7 -F, 59 bytes for(a=argn;eval(a)!==null;)a=substr(a,1).a[0];echoa;  Try it online! (not working, PHP 7) Try with onlinephpfunctions (working PHP 5.6) Inspired by Jo King's answer. Works with {} braces instead of square ones. eval() returns null unless return is called in the evaluated code, in which case the value passed to return is returned. As of PHP 7, if there is a parse error in the evaluated code, eval() throws a ParseError exception. Before PHP 7, in this case eval() returned false and execution of the following code continued normally. PowerShell, 89 bytes This solution uses parenthesis rather than brackets. for(n=args){try{n-replace"\(",",@("|iex *>0;break}catch{n=-joinn[1..n.Length+0]}}n  Try it online! Bonus PowerShell, Regex-Based 129 127 bytes Sure, the other way is shorter, but how often do I get a chance to use my balanced-bracket-matching regex?? Almost never! for(n=args;!(n-match'((\[(?=[^$]*(?<s>$$))|\k<s>(?<-s>))+?(?(s)(?!)))*'-and$n-eq$Matches[0])){$n=-join$n[1..$n.Length+0]}$n


Try it online!

• Your regex is much longer than it needs to be: for($n=$args;$n-notmatch'^((\[)|(?<-2>]))*$'){$n=-join$n[1..$n.Length+0]}$n suffices. $args-match'((\[)|(?<-2>]))*$' actually returns the longest suffix, but I don't know enough PowerShell to append the prefix.
– Neil
Commented Mar 25, 2021 at 13:20
• nice *>0. Very smart with splatting! Commented Mar 26, 2021 at 6:43
• nice $n-replace *>0. but $e=$n-replace is shorter :) Commented Mar 26, 2021 at 7:13 JavaScript, 56 bytes q=>q.map(async _=>q.push(q.shift())|eval(q+'')|alert(q))  Try it online! PowerShell, 87 86 bytes Inspired by Zaelin Goodman param($n)$n|% t*y|%{($n=($n|% S*g 1)+$n[0])}|?{try{\$_-replace'\(',',(0'|iex;1}catch{}}


Try it online!

The script returns all solutions.

Vyxal, 8 bytes

{:k[øo|Ǔ


Try it Online!

Takes as a string of [].

{        # While...
øo   # Removing until no change...
k[     # The string []
:       # From the top of stack
øo   # Eventually yields a truthy value (i.e. non-balanced)
|Ǔ # Rotate left.


Python 2, 147 bytes

def f(u):
k=set()
for x in permutations(u):
s=''.join(x)
try:eval(s)
except:pass