13
\$\begingroup\$

Today's problem is easy. You're given two strings A and B of equal length consisting of only the characters ( and ). Check whether after any number of operations you can make both strings balanced or not. The only operation allowed is swapping A[i] and B[i], where i is an arbitrary index.

Here is the definition of a balanced string.

  • An empty string is a balanced string.
  • If s is a balanced string, "(" + s + ")" is a balanced string.
  • If x and y are balanced, x + y is balanced.

Tests:

( ) -> false
() () -> true
((())) ()()() -> true
()())) ((()() -> true
)))((( ((())) -> false
)))))) )))))) -> false
))))))) ))))))) -> false
()))))) (((((() -> false

Shortest code wins.

Improve this question
\$\endgroup\$
6
  • 2
    \$\begingroup\$ Can we use true and false in stead of ( and )? \$\endgroup\$
    – mousetail
    Jul 29 at 13:18
  • 1
    \$\begingroup\$ Or even better 1 and -1 \$\endgroup\$
    – mousetail
    Jul 29 at 13:35
  • 4
    \$\begingroup\$ You can represent the open and close parentheses as anything you want. \$\endgroup\$
    – Huỳnh Trần Khanh
    Jul 29 at 13:57
  • 5
    \$\begingroup\$ By "a few" do you mean "any number of" or 3 or less? \$\endgroup\$
    – Jonah
    Jul 29 at 21:01
  • \$\begingroup\$ How do you define "Balanced" ? \$\endgroup\$
    – roblogic
    Jul 30 at 8:48

15 Answers 15

Reset to default
9
\$\begingroup\$

Rust, 204 179 147 132 123 98 90 80 bytes

|a,b|a.iter().zip(b).fold([0;3],|[c,d,f],(&e,g)|[c+e+g,d^e^g,f.min(c+d)])==[0;3]

Attempt This Online!

Radically new algorithm. We know the only possible failure case is if:

  • We get 2 simultaneous closing parenthesis when the nesting level is 0
  • We get 2 different closing parenthesis when the nesting level is 0

We use d to store if there currently is an odd or even number of unequal pairs. If the nesting level c-d is negative, we fail. If the nesting level is not 0 or the number of unequal pairs is not even at the end we fail.

d^((e^!g)+1)/2 should be 1 if e=g and 0 otherwise.

Uses 1 to represent an opening parenthesis and -1 for closing.

Improve this answer
\$\endgroup\$
5
6
\$\begingroup\$

JavaScript, 109 107 ... 95 bytes

Thanks to @Arnauld for saving 2 bytes

b=(x,k=0n)=>k<0?0:x?b(x/4n,k+x%4n-2n):!k
f=(l,r,k=0n,x=k&(r^l))=>b(l^x)&b(r^x)||k<l&&f(l,r,++k)

returns false (for false) or 1 (for true).

Encodes expressions as base four numbers with 3 for ( and 1 for )

Helper functions for converting strings to the corresponding base 4 numbers

e=(s)=>s?4n*e(s.slice(1))+(s[0]=='('?3n:1n):0n
h=(x,y)=>f(e(x),e(y))

h(")))(((","((()))") // -> false

Attempt This Online!

I was unable to verify the last two Test-cases, as the function exceeded the maximum recursion depth (which as far as I known is allowed for code-golf)

Explanation

b checks if a the expression encoded by the given number is balanced, by counting the difference of 3 digits minus 1 digits and returning 0 if the intermediate count goes below zero, or if the final count is not exactly zero.

f checks for all binary numbers k less than l (swapping the outer brackets cannot balance the expression) if swapping the bits of the two inputs at the positions that are one in k will result in a pair of balanced strings. Swapping a bit has no effect if it is the low bit of a base 4 digit where both numbers have a 1 bit, if it is the high bit it will swap the characters that the given positions in the strings.

JavaScript, 108 bytes

b=(x,k=0n)=>k<0?0:x?b(x/4n,k+x%4n-2n):!k
f=l=>r=>eval("for(v=0,k=0n;k<l;k++)v|=b(l^k&(r^l))&b(r^k&(r^l));v")

uses for-loop to prevent crash due to recursion limit

Attempt This Online!

Improve this answer
\$\endgroup\$
0
6
\$\begingroup\$

JavaScript (Node.js), 59 bytes

a=>b=>(h=u=>u<d|!a[i]?u|d:h(u+=p=a[i]+b[i++],d^=!p))(i=d=0)

Try it online!

Input arrays of numbers: 0.5 for (, -0.5 for ). Output falsy (0) for "can be balanced", truthy (non-zero) for "cannot be balanced".

Construct a string c using inputs a and b by:

  • if the i-th characters match, aka. a[i]==b[i], then c[i]=a[i]
  • Otherwise, they mismatch. For the k-th mismatch (1-indexed), c[i]=')' when k is odd, and c[i]='(' when k is even.

Test if c is balanced and there are even number of mismatching.

In above code, u-d is how many unclosed "(" in string c. d is a boolean, truthy when next mismatch should be "(".

I’m feeling its correctness. Although I don’t have a mathematical proof to it. However, at least no testcase rejects it currently.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Half the mismatches must go each way. From any balanced (A,B), we can do two swaps, get closer to (C,...), and stay balanced. \$\endgroup\$
    – Gurkenglas
    Jul 30 at 13:39
5
\$\begingroup\$

Scala, 165 136 bytes

Port of @mousetail's Rust answer in Scala.

Golfed version. Try it online!

Saved 29 bytes thanks to the comment of @corvus_192

(a,b)=>(a zip b)./:(Seq((0,0))){case(c,(z,y))=>c.flatMap{case(f,v)=>Seq((f+z,v+y),(f+y,v+z))}filter(g=>g._1>=0&&g._2>=0)}exists((0,0)==)

Ungolfed version. Try it online!

object Main {
  def main(args: Array[String]): Unit = {
    val f: (Seq[Byte], Seq[Byte]) => Boolean = (a, b) => {
      a.zip(b).foldLeft(Seq[(Int, Int)]((0,0))) { (c, de) =>
        c.flatMap { f => 
          Seq((f._1 + de._1, f._2 + de._2), (f._1 + de._2, f._2 + de._1))
        }.filter(g => g._1 >= 0 && g._2 >= 0)
      }.exists(_ == (0, 0))
    }

    val testCases = Seq(
      (Seq(1.toByte), Seq((-1).toByte), false),
      (Seq(1.toByte, (-1).toByte), Seq(1.toByte, (-1).toByte), true),
      (Seq(1.toByte, 1.toByte, 1.toByte, (-1).toByte, (-1).toByte, (-1).toByte), Seq(1.toByte, (-1).toByte, 1.toByte, (-1).toByte, 1.toByte, (-1).toByte), true),
      (Seq(1.toByte, (-1).toByte, 1.toByte, (-1).toByte, (-1).toByte, (-1).toByte), Seq(1.toByte, 1.toByte, 1.toByte, (-1).toByte, 1.toByte, (-1).toByte), true),
      (Seq((-1).toByte, (-1).toByte, (-1).toByte, 1.toByte, 1.toByte, 1.toByte), Seq(1.toByte, 1.toByte, 1.toByte, (-1).toByte, (-1).toByte, (-1).toByte), false),
      (Seq.fill(6)((-1).toByte), Seq.fill(6)((-1).toByte), false),
      (Seq.fill(7)((-1).toByte), Seq.fill(7)((-1).toByte), false),
      (Seq(1.toByte) ++ Seq.fill(6)((-1).toByte), Seq.fill(6)(1.toByte) ++ Seq((-1).toByte), false)
    )

    for (testCase <- testCases) {
      println(s"${testCase._1} ${testCase._2} expected: ${testCase._3}, got: ${f(testCase._1, testCase._2)}")
    }
  }
}
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ My rust answer now uses a radically different algorithm, adapting it may save you some bytes :) \$\endgroup\$
    – mousetail
    Jul 29 at 18:21
  • 1
    \$\begingroup\$ 131 bytes: b=>_.zip(b)./:(Seq((0,0))){case(c,(z,y))=>c.flatMap{case(f,v)=>Seq((f+z,v+y),(f+y,v+z))}filter(g=>g._1>=0&&g._2>=0)}exists((0,0)==) \$\endgroup\$
    – corvus_192
    Jul 29 at 19:51
5
\$\begingroup\$

Oops, this doesn't work. Currently being kept as a placeholder.

C (gcc), 92 91 90 bytes

c;i;r;t(a,b,l)int*a,*b;{for(c=i=0,r=!(l&1);i<l;c+=a[i]+b[i++])r&=c>0|a[i]>0&b[i]>0;r&=!c;}

Try it online!

Returns in boolean r, takes the length and arrays where ( is 1 and ) is -1.

Less golfed variation:

int retFlag;
int test (int* a, int* b, int length) {
    int counter = 0;
    retFlag = !(length & 1);
    for (int i = 0; i < length; i++) {
        retFlag &= counter > 0 || (a[i] > 0 && b[i] > 0);
        counter += a[i] + b[i];
    }
    retFlag &= !counter;
}

C (gcc), 73 71 bytes by @c--

c;r;t(a,b,l)int*a,*b;{for(c=r=l&1;l--;c+=*b+++*a++)r|=c<-*b**a;r=r<!c;}

Try it online!

=======================

Operating hypothesis (WRONG): The strings can be swapped into both being balanced if and only if their length is even and both F(A, B) and F(B, A) are balanced, where F(X, Y) := {X[0], Y[0], X[1], Y[1], X[2], Y[2], ...}.

Reset edit: Previous program relied on caller manually setting internal variables. 3 bytes saved by @c--

Edit R+1: -1 byte from moving stuff into the conveniently empty for loop declaration.

Edit R+2: -1 byte from moving stuff into the empty for loop body. Thanks @c--

Edit R+3: c-- saved two bytes

Improve this answer
\$\endgroup\$
7
  • 1
    \$\begingroup\$ the code should be self-contained, that is, you should reset c, n, i and r in the function \$\endgroup\$
    – c--
    Jul 29 at 20:55
  • \$\begingroup\$ Oh, I misinterpreted "Use global variables to initialize things to zero" on the tips page. \$\endgroup\$
    – SNBeast
    Jul 29 at 21:01
  • 1
    \$\begingroup\$ also, should t>=0 be n>=0? \$\endgroup\$
    – c--
    Jul 29 at 21:04
  • 3
    \$\begingroup\$ yeah, that tip is meant for full programs, you can use it in a function, but you can't rely on the caller setting up the environment for you. \$\endgroup\$
    – c--
    Jul 29 at 21:09
  • 4
    \$\begingroup\$ Counterexample: ())()) (()(() \$\endgroup\$
    – Huỳnh Trần Khanh
    Jul 31 at 2:53
3
\$\begingroup\$

Jelly, 13 bytes

ZŒpÄṂȯṪƊ€oṚ$Ạ

A monadic Link that accepts a pair of lists of \$\{1,-1\}\$ representing ( and ) respectively and yields \$0\$ if balancable or \$1\$ if not (i.e. outputs the inverse).

Try it online! Or see the test-suite.

How?

ZŒpÄṂȯṪƊ€oṚ$Ạ - Link: pair of lists of -1 and 1 := ) and ( respectively
Z             - transpose
 Œp           - Cartesian product
   Ä          - cumulative sums (vectorises)
       Ɗ€     - for each: last three links as a monad:
      Ṫ       -   tail
    Ṃ         -   minimum (of the rest)
     ȯ        -   {minimum} logical OR {tail}
           $  - last two links as a monad:
          Ṛ   -   reverse
         o    -   logical OR (vectorises)
            Ạ - all?
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

C89, 79 77 69 bytes

r,c;f(*a,*b){for(c=r=1;*a&0<c;++a)c+=*a^*b++?r=-r:*a;return c==1==r;}

Using (int)1 as '(' and (int)-1 as ')'

int diff;
int count;
int check(int *a, int *b)
{
    for ( c=1, r=1; *a!=0 && 0<c; ++a, ++b )
    {
        c += (*a != *b) ? (r=-r) : *a;
    }
    return (c==1) == r;
}

The logic is based on the consideration that if a solution exists, it will get a count on the nodes of different values lower than what it would get by alternating between '(' and ')', so that would also be a solution

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Welcome to Code Golf, and nice first answer! \$\endgroup\$
    – The Thonnu
    Aug 1 at 6:05
  • 1
    \$\begingroup\$ Unfortunately, output via assigning to a global variable is not allowed. Thankfully using this tip you can just assign to a instead and it will still work \$\endgroup\$
    – mousetail
    Aug 2 at 5:35
  • 1
    \$\begingroup\$ @mousetail Thanks for pointing it out; I edited it. I respectfully did not use the tip you linked since it's non-standard c89 \$\endgroup\$
    – Pignotto
    Aug 2 at 8:41
2
\$\begingroup\$

Haskell, 139 bytes

g=(\c->all(>=0) c&&last c==0).scanl(+)0
o j k=any(\(d,e)->g d&&g e).foldr(\(x,y)h->concat[[(x:a,y:b),(y:a,x:b)]|(a,b)<-h])[([],[])]$zip j k

foldr(\(x,y)h->concat[[(x:a,y:b),(y:a,x:b)]|(a,b)<-h])[([],[])]$zip j k gives a list of all possible pairs. o then uses g, which determines if a string is balanced, to get the final result. Input is taken as a sequence, with 1 representing '(' and −1 representing ')'.

Attempt This Online!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Haskell, 77 73 bytes

o a b=all(<1)$scanr(%)0$3:zipWith(+)a b
3%c= -c
0%c=c+1-2*mod c 2
n%c=c+n

Attempt This Online!

The other Haskell entry sets the precedent that (=1 and )=-1. The right-to-left running totals of A and B are to stay <1 (and end >-1, as checked by 3%). A+B has all information we need. Wlog the running total of A-B stays in [0,2]. scanr(%)0 maps A+B to the running total of A+B + (A-B)/2.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ You might as well replace o a b= with a#b= to save a few cheap bytes. \$\endgroup\$
    – Lynn
    Jul 31 at 10:30
2
\$\begingroup\$

Nekomata + -e, 8 bytes

Ťᵐ↕∫Ɔž∑≤

Attempt This Online!

Takes input as a list of lists of -1 and 1 representing ( and ) respectively. For example, [[-1,1,1,1],[-1,-1,-1,1]] represents ())) ((().

Ťᵐ↕∫Ɔž∑≤
Ť           Transpose
 ᵐ↕         Non-deterministically permute each inner list
   ∫        Cumulative sum
    Ɔ       Split into the last element and the rest
     ž      Check if the last element is all 0s
      ∑     Sum; since the last element is all 0s, this will be 0
       ≤    Is the rest less than or equal to this sum (0)?
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Retina 0.8.2, 144 bytes

 |^
$&#
+%`^(((\()|(?<-3>\)))*)#(.)(.* ((\()|(?<-7>\)))*)#(.)
$1$4#$5$8#$'¶$1$8#$5$4#
G`^((\()|(?<-2>\)))*(?(2)$)# ((\()|(?<-4>\)))*(?(4)$)#$
^.

Try it online! Link includes test cases. Explanation:

 |^
$&#

Place markers at the start of each string to determine progress through them.

^(((\()|(?<-3>\)))*)#(.)(.* ((\()|(?<-7>\)))*)#(.)
$1$4#$5$8#$'¶$1$8#$5$4#

If the current prefix of both strings is a validly balanced prefix, then progress through the string, generating results with and without a swap of the next character. Testing of balanced prefixes is unsurprisingly performed using .NET's balancing groups.

+%`

Repeat the above separately on each intermediate result until no new results can be obtained.

G`^((\()|(?<-2>\)))*(?(2)$)# ((\()|(?<-4>\)))*(?(4)$)#$

Keep only those results that progressed through the whole string and also are completely balanced rather than simply a balanced prefix (using conditional regex to enforce that the balancing group is now empty).

^.

Check that we had at least one result.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 26 bytes

∧⁼№⁺θη(Ｌθ⬤θ›№⁺…θ⊕κ…η⊕κ(｜κ¹

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - for balanced, nothing if not. Explanation:

    θ                       First input
   ⁺                        Concatenated with
     η                      Second input
  №                         Count of
      )                     Literal string `)`
 ⁼                          Equals
        θ                   First input
       Ｌ                    Length
∧                           Logical And
          θ                 First input
         ⬤                  All characters satisfy
               θ            First input
              …             Truncated to length
                 κ          Current index
                ⊕           Incremented
             ⁺              Concatenated with
                   η        Second input
                  …         Truncated to length
                     κ      Current index
                    ⊕       Incremented
            №               Count of
                      (     Literal string `(`
           ›                Is greater than
                        κ   Current index
                       ｜    Bitwise Or
                         ¹  Literal integer `1`

The idea here is that the strings can be balanced if the following two conditions hold:

  1. Exactly half of all of the characters are (s.
  2. For each prefix of both strings, there are more (s than the 0-indexed position of the last character of the prefix, plus 1 if that is even.

Examples:

1st  2nd  (s   Needed

Valid:

(    (    2    >1
()   ((   3    >1
())  (((  4    >3
())) ((() 4    >3

Invalid:

(    (    2    >1
((   ()   3    >1
(()  ())  3    >3
(()) ())( 4    >3
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Perl 5, 53 bytes

sub{y/(/#/for@_;((pop)&pop)=~/^(#((!?)(?1)*\3)\))+$/}

Try it online!

First (wrong) version is in editing history, this one seems to pass. Please tell if it fails some test.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Ruby, 108 bytes

Brute forces all combinations of the two inputs until it finds one that is balanced. Input is an array containing two arrays of integers, where 1 represents ( and -1 represents ).

->a{(v=0,1).product(*[v]*~-a[0].size).any?{i=-1;j=k=0;_1.all?{|n|(j+=a[n][i+=1])|(k+=a[1-n][i])>=0}&&j|k<1}}

Attempt This Online!

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ that "hypothesis" is wrong now \$\endgroup\$
    – Huỳnh Trần Khanh
    Jul 31 at 3:25
0
\$\begingroup\$

JavaScript (Node.js), 47 bytes

Input: array, 2([), -2(])

Output: integer, 0(balanced), truthy(not)

a=>b=>a.some((v,i)=>0<(S=v-b[i]?S^1:S-v),S=0)|S

Try it online!

JavaScript (Node.js), 52 bytes

a=>b=>!a.some((v,i)=>1<(S-=v-b[i]?j^=-2:v),S=j=1)==S

Try it online!

      1 if true
      0 if some ")" mismatched, in which case S>1 so S!=0
      |
a=>b=>!a.some((v,i)=>1<(S-=v-b[i]?j^=-2:v),S=j=1)==S
                     |
                     '-- If more ")" appeared
Improve this answer
\$\endgroup\$

Your Answer

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

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