En este desafío, se le dará una cadena alfabética como entrada. Definiremos el "anti-string" de una entrada dada para que sea el string con el caso de todas las letras invertidas. Por ejemplo

AaBbbUy -> aAbBBuY

Debe escribir un programa que tome una cadena como entrada y busque la subcadena contigua más larga cuyo anti-cadena también sea una subcadena contigua. Las dos subcadenas no deben superponerse.

Como ejemplo si te dieron la cadena

fAbbAcGfaBBagF

Las partes en negrita serían el par de cuerdas anti-cuerda más largo.

Su programa debe, una vez que ha encontrado el par, colapsarlos en un solo carácter cada uno. Debería hacer esto eliminando todos menos el primer carácter de cada subcadena. Por ejemplo, la cadena de arriba

fAbbAcGfaBBagF

se convertiría

fAcGfagF

Luego, su programa debe repetir el proceso hasta que el par más largo de cadena anti-cadena sea un solo carácter o más corto.

Por ejemplo, trabajando con la misma cadena, el nuevo par más largo después del colapso es

fAcGfagF

Entonces colapsamos la cuerda nuevamente

fAcGag

Ahora la cadena no se puede contraer más, por lo que deberíamos generarla.

En el caso de un empate entre pares candidatos (ejemplo AvaVA) puede hacer una reducción ( AaAo AvV, pero no Aa).

Este es el código de golf, por lo que las respuestas se puntuarán en bytes, con menos bytes mejor.

Casos de prueba

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

Motivaciones

Si bien este problema puede parecer arbitrario, en realidad es un problema que encontré al hacer el código para procesar polígonos fundamentales. Este proceso puede usarse para reducir un polígono fundamental a un n -gon más pequeño. Después de que lo probé, pensé que sería un bonito y pequeño golf.

Perl, 64 61 bytes

Incluye +1parap

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

JavaScript (ES6), 200 bytes

Utiliza matrices de caracteres para E / S.

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

Pruébalo en línea!

Retina , 119 bytes

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

Pruébalo en línea! El enlace incluye casos de prueba. Explicación:

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

Duplique la entrada y voltee el caso de la primera copia.

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

Si no hay anti-cadenas en absoluto, elimine el duplicado invertido.

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

Enumere todas las posibles cadenas de caracteres contraídas.

N$`
$.&
}0G`

Ordénelos en orden de longitud, tome el anti-string más corto (es decir, el anti-string más largo) y repita hasta que todos los anti-string se hayan colapsado.

Python 3 , 189181 bytes

Gracias a Jonathan Frech por hacerlo puro de una sola línea.

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

Pruébalo en línea!

Mi propia versión, ahora obsoleta (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

Pruébalo en línea!

any()para romper los bucles anidados temprano, y set()para el objeto global mutable utilizable en la comprensión. El resto es solo la implementación directa de los requisitos 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

Pruébalo en línea!

Resulta que el bucle for anidado regular con ruptura temprana returnes mucho más corto que el truco "inteligente" any.

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

• Guardado dos bytes; eliminó una definición de variable perdida.
• Salvó once trece bytes; golf b|=S[p+m]!=S[q+m]+32-(S[q+m]>90)*64a b|=abs(S[p+m]-S[q+m])-32a b|=32-S[p+m]+S[q+m]&63.
• Guardado tres bytes; golf for(...;...;p++)S[p+1]=S[p+L];a for(...;...;S[++p]=S[p+L]);.
• Guardado seis bytes gracias a 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;}

Pruébalo en línea!

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

Pruébalo en línea!

Stax , 30 bytes

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

Ejecutar y depurarlo

La representación ascii correspondiente del mismo programa es esta.

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

Utiliza un enfoque regex. Regex repetidamente reemplazo de cadena. Los construye a partir de cada subcadena contigua del valor actual. Por ejemplo, para la entrada fAbbAcGfaBBagF, una de las subcadenas es AbbA, en cuyo caso la expresión regular AbbA(.*)aBBase reemplazará por 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

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]]&

Pruébalo en línea!

Japt -h , 33 bytes

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

Intentalo

à ñÊÅÔ£=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