Contraer el antistring

27

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

Asistente de trigo
fuente
Si la subcadena más grande con subcadenas anti-cadena tiene más de una subcadena anit-string, ¿deberían colapsarse todas las subcadenas o solo las dos primeras?
Jonathan Frech
@ JonathanFrech Cualquiera dos. Ese es un caso donde hay un empate entre pares candidatos.
Wheat Wizard
Entonces aaaAAAaaa -> aAaaa?
Jonathan Frech
Algo sobre un subconjunto de este problema grita quine pero no puedo señalarlo.
Urna mágica del pulpo
1
@MagicOctopusUrn ¿Algo así como escribir una quine de dos ciclos donde la salida del programa es su antistring ?
Jonathan Frech

Respuestas:

8

Perl, 64 61 bytes

Incluye +1parap

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

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!

Arnauld
fuente
3

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.

Neil
fuente
3

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.

Bubbler
fuente
181 bytes ; Enfoque recursivo. El mutable setcomo función predeterminada no colisionará con más llamadas, ya que creo que su código muestra completamente el conjunto como vacío.
Jonathan Frech
Lo siento, pensé que xse quedaría sin estar vacío. Como lo tienes, creo que cumple.
Jonathan Frech
Eso está bien, y gracias por la mejora.
Bubbler
3

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!

Jonathan Frech
fuente
@ceilingcat Gracias.
Jonathan Frech
0

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!

Chas Brown
fuente
0

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
recursivo
fuente
0

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
Lanudo
fuente