Collapse the antistring

Question

In this challenge you will be given an alphabetic string as input. We will define the "anti-string" of a given input to be the string with the case of all the letters inverted. For example

AaBbbUy -> aAbBBuY

You should write a program that takes a string as input and searches for the longest contiguous substring whose anti-string is also a contiguous substring. The two substrings should not overlap.

As an example if you were given the string

fAbbAcGfaBBagF

The bolded portions would be the longest string anti-string pair.

Your program should, once it has found the pair, collapse them into a single character each. It should do this by removing all but the first character of each substring. For example the string above

fAbbAcGfaBBagF

would become

fAcGfagF

Your program should then repeat the process until the longest string anti-string pair is a single character or shorter.

For example working with the same string the new longest pair after the collapse is

fAcGfagF

So we collapse the string again

fAcGag

Now the string cannot be collapsed further so we should output it.

In the case of a tie between candidate pairs (example AvaVA) you may make either reduction (AaA or AvV, but not Aa).

This is code-golf so answers will be scored in bytes with fewer bytes being better.

Test Cases

fAbbAcGfaBBagF  ->  fAcGag
AvaVA ->  AaA / AvV
QQQQQQQ -> QQQQQQQ
fAbbAcQQQQaBBacqqqqA -> fAbcQBcq
gaq -> gaq
fAbbAcGfaBBagFaBBa -> fcGaBBag

Motivations

While this problem may seem arbitrary it is actually a problem I encountered while making code to process fundamental polygons. This process can be used to reduce a fundamental polygon to a smaller n-gon. After I tried it I thought it would make a nice little golf.

Answer 1

Perl, 64 61 bytes

Includes +1 for p

perl -pE 's/(.\K.{$%})(.*)(?=(.))(??{$1^$"x$%.$"})/$2$3/ while$%=--pos' <<< fAbbAcGfaBBagFaBBa

Answer 2

JavaScript (ES6), 200 bytes

Uses arrays of characters for I/O.

f=a=>(m=M=C=>a.map((_,i)=>a.map((_,j)=>C(i,j-i+1))))(I=>M((i,j)=>a.slice(i,i+j).some((n,k)=>n[c='charCodeAt']()^(a[I+k]||'')[c]()^32)|I+j>i|j<m||(x=[i,I],m=j)))&&m-->1?f(a,x.map(p=>a.splice(p+1,m))):a

Try it online!

Answer 3

C (gcc), 240 238 227 225 222 216 bytes

• Saved two bytes; removed a stray variable definition.
• Saved eleven thirteen bytes; golfed b|=S[p+m]!=S[q+m]+32-(S[q+m]>90)*64 to b|=abs(S[p+m]-S[q+m])-32 to b|=32-S[p+m]+S[q+m]&63.
• Saved three bytes; golfed for(...;...;p++)S[p+1]=S[p+L]; to for(...;...;S[++p]=S[p+L]);.
• Saved six bytes thanks to ceilingcat.

p,P,q,Q,l,L,b,m;f(char*S){for(p=0;S[p];p++)for(l=0;S[l+++p];)for(q=0;b=S[q+~-l];!b&p+l<=q&l>L?L=l,P=p,Q=q:0,q++)for(b=0,m=l;m--;)b|=32-S[p+m]+S[q+m]&63;for(;b-2;)for(p=b++?-~Q-L:P;S[p];S[++p]=S[L+p]);~-L?L=0,f(S):0;}

Try it online!

Answer 4

Python 3, 189 181 bytes

Credit to Jonathan Frech for making it pure one-liner.

f=lambda s,x=set():any(u in s[j+i:]and(x.add(s[:j+1]+s[j+i:].replace(u,u[0],1))or 1)for i in range(len(s),1,-1)for j in range(len(s))for u in[s[j:j+i].swapcase()])and f(x.pop())or s

Try it online!

My own version, now obsolete (189 bytes):

x=set()
def f(s):
 while any(u in s[j+i:]and(x.add(s[:j+1]+s[j+i:].replace(u,u[0],1))or 1)for i in range(len(s),1,-1)for j in range(len(s))for u in[s[j:j+i].swapcase()]):s=x.pop()
 return s

Try it online!

any() to break out nested loops early, and set() for mutable global object usable in the comprehension. The rest is just the straightforward implementation of the requirements using str.swapcase.

Python 2, 160 bytes

def f(s):
 for i in range(len(s),1,-1):
	for j in range(len(s)):
	 u=s[j:j+i].swapcase()
	 if u in s[j+i:]:return f(s[:j+1]+s[j+i:].replace(u,u[0],1))
 return s

Try it online!

Turns out that regular nested for loop with early breaking through return is way shorter than the "clever" trick with any.

Answer 5

Retina, 119 bytes

.+
$&¶$&
T`Ll`lL`.*¶
/(.).*¶.*\1/^&0A`
¶&Lv$`(?<=(.)*)((.)(.)*).*¶(?>((?<-1>.)*.)(?<-4>.)*)(.*)\2
$5$6$3$'
N$`
$.&
}0G`

Try it online! Link includes test cases. Explanation:

.+
$&¶$&
T`Ll`lL`.*¶

Duplicate the input and flip the case of the first copy.

/(.).*¶.*\1/^&0A`

If there are no anti-strings at all then delete the flipped duplicate.

¶&Lv$`(?<=(.)*)((.)(.)*).*¶(?>((?<-1>.)*.)(?<-4>.)*)(.*)\2
$5$6$3$'

List all the possible collapsed anti-strings.

N$`
$.&
}0G`

Sort them in order of length, take the shortest (i.e. longest anti-string), and repeat until all the anti-strings have been collapsed.

Answer 6

Python 2, 180 bytes

def f(s):
 L=len(s)
 for x,y in[(i,i+j)for j in range(L,1,-1)for i in range(L-j)]:
	t=s[x:y];T=t.swapcase()
	if T in s[y:]:return f(s.replace(t,t[0],1).replace(T,T[0],1))
 return s

Try it online!

Answer 7

Stax, 30 bytes

î☼fúΩ§☺æ╒ºê@Ñ▀'╫Iqa{d]∟Sa5♦⌂─╚

Run and debug it

The corresponding ascii representation of the same program is this.

c%Dc:e{%orF..*:{_{32|^mY++_h.$1yh++R

It uses a regex approach. It repeatedly regex string replacement. It builds these from each contiguous substring of the current value. For instance for the input fAbbAcGfaBBagF, one of the substrings is AbbA, in which case the regex AbbA(.*)aBBa will be replaced with A$1a.

c                                       get number of characters
 %D                                     repeat rest of program that many times
   c:e                                  get all substrings
      {%or                              order substrings longest to shortest
          F                             for each substring, execute the rest
           ..*:{                        build the string "(.*)"
                _{32|^m                 current substring with case inverted
                       Y                save the inverted case in register y
                        ++              concatenate search regex together
                                            e.g. "aBc(.*)AbC"
                          _h            first character of substring
                            .$1         "$1"
                               yh       first character of inverted case
                                 ++     concatenate replacement regex together
                                            e.g. "a$1A"
                                   R    do regex replacement

Answer 8

Wolfram Language (Mathematica), 148 bytes

#//.s_:>MinimalBy[StringReplaceList[s,a:(p_~~__)~~x___~~b:(q_~~__)/;(32==##&@@Abs[(t=ToCharacterCode)@a-t@b]):>p<>x<>q]/.{}->{s},StringLength][[1]]&

Try it online!

Answer 9

Japt -h, 33 bytes

à ñÊÅÔ£=rX+"(.*)"+Xc^H ÈÎ+Y+XÎc^H

Try it

à ñÊÅÔ£=rX+"(.*)"+Xc^H ÈÎ+Y+XÎc^H     :Implicit input of string U
à                                     :Combinations
  ñ                                   :Sort by
   Ê                                  :  Length
    Å                                 :Remove first element (the empty string)
     Ô                                :Reverse
      £                               :Map each X
       =                              :  Reassign to U
        r                             :  Global replacement
         X+"(.*)"+                    :  Append "(.*)" to X and then append
                  Xc                  :    Charcodes of X
                    ^H                :    XORed with 32
                      È               :  Pass each match X, with captured group Y, through the following function
                       Î+Y+           :    Append Y to the first character of X and then append
                           XÎc^H      :      The charcode of the first character of X XORed with 32