W tym wyzwaniu otrzymasz ciąg alfabetyczny jako dane wejściowe. Zdefiniujemy „anti-string” danego wejścia, który będzie łańcuchem, a wielkość liter wszystkich liter będzie odwrócona. Na przykład

AaBbbUy -> aAbBBuY

Powinieneś napisać program, który pobiera ciąg jako dane wejściowe i szuka najdłuższego ciągłego podciągu, którego anty-ciąg jest również ciągłym podciągiem. Dwa podciągi nie powinny się pokrywać.

Jako przykład, jeśli podano ci ciąg

fAbbAcGfaBBagF

Pogrubione fragmenty byłyby najdłuższą parą anty-sznurkową.

Twój program powinien po znalezieniu pary zwinąć je w osobne znaki. Powinien to zrobić, usuwając wszystkie oprócz pierwszego znaku każdego podłańcucha. Na przykład ciąg powyżej

fAbbAcGfaBBagF

stanie się

fAcGfagF

Twój program powinien następnie powtarzać ten proces, aż najdłuższa para przeciwdziałająca strunom będzie miała jeden znak lub będzie krótsza.

Na przykład praca z tym samym łańcuchem to nowa najdłuższa para po zwinięciu

fAcGfagF

Więc ponownie zwiniemy ciąg

fAcGag

Teraz łańcuch nie może być dalej zwinięty, więc powinniśmy go wyprowadzić.

W przypadku remisu między parami kandydatów (przykład AvaVA) możesz dokonać redukcji ( AaAlub AvV, ale nie Aa).

To jest golf golfowy, więc odpowiedzi będą liczone w bajtach, przy czym mniej bajtów będzie lepszych.

Przypadki testowe

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

Motywacje

Chociaż ten problem może wydawać się arbitralny, w rzeczywistości jest to problem, który napotkałem podczas tworzenia kodu do przetwarzania podstawowych wielokątów. Ten proces można wykorzystać do zredukowania podstawowego wielokąta do mniejszego n- gona. Po wypróbowaniu pomyślałem, że będzie to fajny mały golf.

Perl, 64 61 bajtów

Obejmuje +1dlap

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

JavaScript (ES6), 200 bajtów

Wykorzystuje tablice znaków dla 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

Wypróbuj online!

Siatkówka , 119 bajtów

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

Wypróbuj online! Link zawiera przypadki testowe. Wyjaśnienie:

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

Zduplikuj dane wejściowe i odwróć obudowę pierwszej kopii.

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

Jeśli w ogóle nie ma żadnych napisów, usuń odwrócony duplikat.

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

Wymień wszystkie możliwe zwinięte anty-stringi.

N$`
$.&
}0G`

Posortuj je według długości, wybierz najkrótszą (tj. Najdłuższą anty-strunę) i powtarzaj, aż wszystkie anty-struny zostaną zwinięte.

Python 3 , 189 181 bajtów

Podziękowania dla Jonathana Frecha za uczynienie go czystym jedno-liniowym.

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

Wypróbuj online!

Moja własna wersja, teraz przestarzała (189 bajtów):

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

Wypróbuj online!

any()wczesne wykrywanie zagnieżdżonych pętli i set()modyfikowalny globalny obiekt użyteczny w zrozumieniu. Reszta to po prostu prosta implementacja wymagań str.swapcase.

Python 2 , 160 bajtów

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

Wypróbuj online!

Okazuje się, że regularne zagnieżdżanie dla pętli z wczesnym przełamywaniem returnjest znacznie krótsze niż „sprytna” sztuczka any.

C (gcc) , 240 238 227 225 222 216 bajtów

• Zapisano dwa bajty; usunięto definicję zmiennej zbłąkanej.
• Zapisano jedenaście trzynaście bajtów; grał b|=S[p+m]!=S[q+m]+32-(S[q+m]>90)*64w golfa b|=abs(S[p+m]-S[q+m])-32dob|=32-S[p+m]+S[q+m]&63 .
• Zapisano trzy bajty; grał for(...;...;p++)S[p+1]=S[p+L];w golfafor(...;...;S[++p]=S[p+L]); .
• Oszczędność sześciu bajtów dzięki pułapowi cat .

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;}

Wypróbuj online!

Python 2 , 180 bajtów

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

Wypróbuj online!

Stax , 30 bajtów

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

Uruchom i debuguj

Odpowiada to reprezentacji ascii tego samego programu.

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

Wykorzystuje podejście wyrażenia regularnego. Wielokrotnie zastępuje ciąg znaków regularnych. Buduje je z każdego ciągłego podciągu bieżącej wartości. Na przykład dla danych wejściowych fAbbAcGfaBBagFjednym z podciągów jest AbbA, w którym to przypadku wyrażenie regularne AbbA(.*)aBBazostanie zastąpione przez 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 bajtów

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

Wypróbuj online!

Japt -h , 33 bajty

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

Spróbuj

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