Neste desafio, você receberá uma sequência alfabética como entrada. Definiremos o "anti-string" de uma determinada entrada como a string com o caso de todas as letras invertidas. Por exemplo

AaBbbUy -> aAbBBuY

Você deve escrever um programa que use uma string como entrada e procure a substring contígua mais longa cuja anti-string também seja uma substring contígua. As duas substrings não devem se sobrepor.

Como exemplo, se você recebeu a string

fAbbAcGfaBBagF

As partes em negrito seriam o par anti-corda mais longo.

Seu programa deve, uma vez encontrado o par, recolhê-los em um único caractere cada. Isso deve ser feito removendo todos, exceto o primeiro caractere de cada substring. Por exemplo, a sequência acima

fAbbAcGfaBBagF

se tornaria

fAcGfagF

Seu programa deve repetir o processo até que o par mais longo de cadeia de caracteres seja um único caractere ou menor.

Por exemplo, trabalhando com a mesma string, o novo par mais longo após o colapso é

fAcGfagF

Então, cortamos a corda novamente

fAcGag

Agora, a string não pode ser recolhida ainda mais, portanto devemos produzi-la.

No caso de empate entre pares candidatos (exemplo AvaVA), você pode fazer uma redução ( AaAou AvV, mas não Aa).

Isso é código-golfe, então as respostas serão pontuadas em bytes, com menos bytes sendo melhores.

Casos de teste

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

Motivações

Embora esse problema possa parecer arbitrário, é realmente um problema que encontrei ao criar código para processar polígonos fundamentais. Esse processo pode ser usado para reduzir um polígono fundamental a um n- polígono menor . Depois que eu tentei, pensei que seria um bom pequeno golfe.

Perl, 64 bytes

Inclui +1parap

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

JavaScript (ES6), 200 bytes

Usa matrizes 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

Experimente online!

Retina , 119 bytes

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

Experimente online! O link inclui casos de teste. Explicação:

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

Duplique a entrada e vire a caixa da primeira cópia.

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

Se não houver anti-strings, exclua a duplicada invertida.

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

Liste todos os possíveis anti-strings recolhidos.

N$`
$.&
}0G`

Classifique-os em ordem de comprimento, pegue o menor (ou seja, o maior anti-fio) e repita até que todos os anti-fios tenham sido recolhidos.

Python 3 , 189 181 bytes

Agradecemos a Jonathan Frech por torná-lo puro 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

Experimente online!

Minha própria versão, agora 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

Experimente online!

any()romper loops aninhados cedo e set()para objetos globais mutáveis ​​que possam ser utilizados na compreensão. O resto é apenas a implementação direta dos requisitos usando 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

Experimente online!

Acontece que o loop aninhado regular com quebra antecipada returné bem mais curto do que o truque "inteligente" any.

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

• Salvou dois bytes; removeu uma definição de variável dispersa.
• Salvou onze treze bytes; jogou golfe b|=S[p+m]!=S[q+m]+32-(S[q+m]>90)*64para b|=abs(S[p+m]-S[q+m])-32a b|=32-S[p+m]+S[q+m]&63.
• Salva três bytes; jogou golfe for(...;...;p++)S[p+1]=S[p+L];para for(...;...;S[++p]=S[p+L]);.
• Economizou seis bytes graças ao 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;}

Experimente online!

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

Experimente online!

Stax , 30 bytes

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

Execute e depure

A representação ascii correspondente do mesmo programa é essa.

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

Ele usa uma abordagem regex. Regex repetidamente substituição de string. Ele os cria a partir de cada substring contíguo do valor atual. Por exemplo, para a entrada fAbbAcGfaBBagF, uma das substrings é AbbA, nesse caso a regex AbbA(.*)aBBaserá substituída 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]]&

Experimente online!

Japonês -h , 33 bytes

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

Tente

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