# Can you perform swaps?

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.

• Can we use true and false in stead of ( and )? Commented Jul 29, 2023 at 13:18
• Or even better 1 and -1 Commented Jul 29, 2023 at 13:35
• You can represent the open and close parentheses as anything you want. Commented Jul 29, 2023 at 13:57
• By "a few" do you mean "any number of" or 3 or less? Commented Jul 29, 2023 at 21:01
• How do you define "Balanced" ? Commented Jul 30, 2023 at 8:48

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

# JavaScript, 109107 ... 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!

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

• Half the mismatches must go each way. From any balanced (A,B), we can do two swaps, get closer to (C,...), and stay balanced. Commented Jul 30, 2023 at 13:39

# 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)}")
}
}
}

• My rust answer now uses a radically different algorithm, adapting it may save you some bytes :) Commented Jul 29, 2023 at 18:21
• 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)==) Commented Jul 29, 2023 at 19:51

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

# C (gcc), 9291 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

• the code should be self-contained, that is, you should reset c, n, i and r in the function
– c--
Commented Jul 29, 2023 at 20:55
• Oh, I misinterpreted "Use global variables to initialize things to zero" on the tips page. Commented Jul 29, 2023 at 21:01
• also, should t>=0 be n>=0?
– c--
Commented Jul 29, 2023 at 21:04
• 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.
– c--
Commented Jul 29, 2023 at 21:09
• Counterexample: ())()) (()(() Commented Jul 31, 2023 at 2:53

# 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)
Ṫ       -   tail
Ṃ         -   minimum (of the rest)
ȯ        -   {minimum} logical OR {tail}
$- last two links as a monad: Ṛ - reverse o - logical OR (vectorises) Ạ - all? # 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. • You might as well replace o a b= with a#b= to save a few cheap bytes. – lynn Commented Jul 31, 2023 at 10:30 ## C89, 7977 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 • Welcome to Code Golf, and nice first answer! Commented Aug 1, 2023 at 6:05 • 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 Commented Aug 2, 2023 at 5:35 • @mousetail Thanks for pointing it out; I edited it. I respectfully did not use the tip you linked since it's non-standard c89 Commented Aug 2, 2023 at 8:41 # 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! # 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)? # 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.

# 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

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

# 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!

• that "hypothesis" is wrong now Commented Jul 31, 2023 at 3:25

# 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

# Haskell + hgl, 41 bytes

mx<(zWn~<rv)<(no lt0*^*q0<gj)<<scp<<sQ<tx

Attempt This Online!

Takes the input as a list of length 2 with 1 representing ( and -1 representing ).

I'm not convinced this is as short as possible. It does outperform a naïve conversion of the shortest pure Haskell answer. I will come back to this later and try again.

## Explanation

• tx transpose the input.
• sQ perform the cartesian product.
• scp scan each element with addition to get the cumulative sums.
• no lt0 check elements have no negative values ...
• *^* ... and ...
• gj ... end in ...
• q0 ... zero.
• zWn~<rv zip the result with its reverse using logical and.
• mx determine if any result is true.

# Reflection

I'm a bit annoyed by how long this is. I also don't like the input format and feel like it's indicative of a weakness. I'd prefer to take it as two separate arguments.

• This feels like not the first time I've used sQ<tx. It will probably be useful and should have a builtin.
• There should be a builtin to determine if a string is balanced. We could do this as:
mx<(zWn~<rv)<blp<<sQ<tx

if such a builtin existed. (Input format would be a list of two strings.)
• For all the zW variants we already have, there could be versions that apply a function to each element before combining them with the fixed function. This would save a little plumbing here.
• I'm debating whether there should be a mx<<zWn and mn<<zWX, we use the former here and the latter here. It seems like it might be a recurring pattern.