Rotate brackets until they're balanced

Question

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.

The Task:

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 code-golf, so shortest answer in bytes per language wins!

Answer 1

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.

---

Previous answer, 7 bytes

Ωȯ¬▼∫ṙ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

Answer 2

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

I thought this 31 byte program using the -p flag would work, but either TIO is too outdated or Raku has some sort of weird behaviour about until/while and $_. Until I can test it using the latest version, you can check it like so.

Answer 3

Jelly, 4 bytes

ÄMṙ@

Try it online!

Similar approach to Leo's answer, give that an upvote!

Uses -1 and 1 for [ and ] and returns all valid rotations

By swapping the signs from Leo's approach, we can operate on the maximal elements, rather than minimal, as Jelly has a builtin M to return the indices of maximal elements, thus saving a byte

How it works

ÄMṙ@ - Main link. Takes a list of 1 and -1, A
Ä    - Take the cumulative sums
 M   - Yield the indices of the maximal elements
  ṙ@ - Rotate A that many times for each index

Answer 4

Python 2, 74 72 69 bytes

def f(s):
 try:exec s.replace(')','),');print s
 except:f(s[1:]+s[0])

Try it online!

Tried a similar approach to Jo King's Raku answer by evaluating the bracket string, only difference being an added , after every ) so that the expression is valid.

Takes ( and ) instead of [ and ].

-2 bytes thanks to Sisyphus, -3 bytes thanks to dingledooper

51 bytes if it's allowed to take ( and ), instead of ( and ) 👀

Answer 5

APL (Dyalog Unicode), 10 bytes (SBCS)

This algorithm.

Anonymous prefix lambda, taking -1 for [ and 1 for ].

{⍵⌽⍨⊃⍒+\⍵}

Try it online! (This template)

{…} "dfn"; argument is ⍵:

 +\⍵ cumulative sum of the argument

 ⍒ indices that would sort that descending (i.e. index of the largest, index of the next-largest, etc.)

 ⊃ the first of that (i.e. the index of the largest)

 ⍵⌽⍨ use that to rotate the argument to the left

Answer 6

Haskell, 37 bytes

until(all(>0).scanl(+)1)$drop<>take$1

Try it online!

Saved 2 bytes using <>.

Takes in a list of 1's and -1's. Actually pretty readable:

until            until
 (all(>0).       we get all positive values from
  scanl(+)1)     the cumulative sums of the list starting from 1,
 $drop<>take     rotate the list
 $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.

Answer 7

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)

Answer 8

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.

Answer 9

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)

Answer 10

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
add(letter(i)of(s))to[S v]
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

Answer 11

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.

Answer 12

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.$_.

Answer 13

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\$, output rotated array.

Thanks user81655 for -1 byte.

Answer 14

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>

Answer 15

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.

Answer 16

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.

Answer 17

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

Answer 18

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\$.

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.

Answer 19

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.

Answer 20

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>

._.

Answer 21

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.
}

Answer 22

Ruby, 47 bytes

->s{s.rotate (0..s.size).min_by{|r|s[0,r].sum}}

Try it online!

Answer 23

K (Kona), 13 bytes

{(1+*>+\x)!x}

Try it online!

Uses -1 for [ and 1 for ].

A port of Adám's APL answer

Answer 24

Retina 0.8.2, 28 bytes

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

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.

Answer 25

PHP < 7 -F, 59 bytes

for($a=$argn;eval($a)!==null;)$a=substr($a,1).$a[0];echo$a;

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.

From the docs:

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.

Answer 26

PowerShell, 89 bytes

This solution uses parenthesis rather than brackets.

for($n=$args){try{$n-replace"\(",",@("|iex *>0;break}catch{$n=-join$n[1..$n.Length+0]}}$n

Try it online!

Bonus PowerShell, Regex-Based ¹²⁹ 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!

Answer 27

JavaScript, 56 bytes

q=>q.map(async _=>q.push(q.shift())|eval(q+'')|alert(q))

Try it online!

Answer 28

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.

Answer 29

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.

Answer 30

Python 2, 147 bytes

def f(u):
 k=set()
 for x in permutations(u):
  s=''.join(x)
  try:eval(s)
  except:pass
  else:k.add(s)
 print "\n".join(k)
from itertools import*

Try it online!

Slow, permutation based approach