28
\$\begingroup\$

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

\$\endgroup\$
13
  • 1
    \$\begingroup\$ Can I return all valid answers? \$\endgroup\$
    – hyper-neutrino
    Mar 25, 2021 at 3:01
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Wheat Wizard
    Mar 25, 2021 at 12:15
  • 6
    \$\begingroup\$ @WheatWizard "Rotation" seems to be a pretty common name for this, although I'll add an explanation of what I mean. \$\endgroup\$ Mar 25, 2021 at 13:25
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ Mar 25, 2021 at 13:26
  • 13
    \$\begingroup\$ 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. \$\endgroup\$
    – Wheat Wizard
    Mar 25, 2021 at 14:19

34 Answers 34

1
2
1
\$\begingroup\$

Charcoal, 25 bytes

≔Eθ⁻№…θκ[№…θκ]η⭆θ§θ⁺κ⌕η⌊η

Try it online! Link is to verbose version of code. Explanation:

≔Eθ⁻№…θκ[№…θκ]η

Calculate the imbalance between [s and ]s for every prefix.

⭆θ§θ⁺κ⌕η⌊η

Switch the prefix with the greatest imbalance with its suffix.

\$\endgroup\$
1
\$\begingroup\$

Excel, 131 bytes

=LET(s,LEN(A1),x,SEQUENCE(s),y,INDEX(SORTBY(MOD(x,s),MMULT((x>=TRANSPOSE(x))*1,(MID(A1,x,1)="[")*2-1)),1),MID(A1,y+1,s)&LEFT(A1,y))

Converts brackets to 1, -1; finds the minimum cumulative sum y; then moves the first y characters to the end.

\$\endgroup\$
1
\$\begingroup\$

Python 3, 123 bytes

[n:=range(l:=len(s)),next(r for i in n if [r:=(2*s)[i:i+l],min(sum("]-[".index(c)-1 for c in r[:p]) for p in n)][1]>=0)][1]

Takes in string of square brackets. Should return first valid rotation:

>>> s="]][][["
>>> [n:=range(l:=len(s)),next(r for i in n if [r:=(2*s)[i:i+l],min(sum("]-[".index(c)-1 for c in r[:p]) for p in n)][1]>=0)][1]
'[][[]]'
\$\endgroup\$
1
\$\begingroup\$

Japt v2.0a0, 11 8 bytes

Uses 1 for [ & 0 for ].

ÈeA}f@éY

Try it - header converts input from brackets and footer converts back to brackets.

ÈeA}f@éY     :Implicit input of string U
È            :Left function taking a string as argument
 e           :Recursively replace
  A          : "10"
   }         :End function
    f        :Return the first result of the right function that returns falsey (empty string) when passed through the left function
     @       :Right function with argument Y, 0-based Iteration index
      éY     :  Rotate U right Y times
\$\endgroup\$
1
2

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.