27

In dieser Herausforderung erhalten Sie eine alphabetische Zeichenfolge als Eingabe. Wir definieren den "Anti-String" einer bestimmten Eingabe als String, wobei alle Buchstaben invertiert sind. Beispielsweise

AaBbbUy -> aAbBBuY

Sie sollten ein Programm schreiben, das eine Zeichenfolge als Eingabe verwendet und nach der längsten zusammenhängenden Teilzeichenfolge sucht, deren Anti-Zeichenfolge ebenfalls eine zusammenhängende Teilzeichenfolge ist. Die beiden Teilzeichenfolgen sollten sich nicht überlappen.

Als Beispiel, wenn Sie die Zeichenfolge erhalten haben

fAbbAcGfaBBagF

Die fettgedruckten Teile wären das längste String-Anti-String-Paar.

Ihr Programm sollte, sobald es das Paar gefunden hat, diese zu jeweils einem Zeichen zusammenfassen. Dies sollte durch Entfernen aller Zeichen außer dem ersten Zeichen jeder Teilzeichenfolge erreicht werden. Zum Beispiel die obige Zeichenfolge

fAbbAcGfaBBagF

würde werden

fAcGfagF

Ihr Programm sollte dann den Vorgang wiederholen, bis das längste String-Anti-String-Paar ein einzelnes Zeichen oder kürzer ist.

Wenn Sie beispielsweise mit derselben Zeichenfolge arbeiten, ist das neue Paar nach dem Zusammenbruch das längste

fAcGfagF

Also brechen wir die Saite wieder zusammen

fAcGag

Jetzt kann der String nicht mehr weiter reduziert werden, daher sollten wir ihn ausgeben.

Im Falle eines Gleichstands zwischen Kandidatenpaaren (Beispiel AvaVA) können Sie entweder eine Reduzierung vornehmen ( AaAoder AvVaber nicht Aa).

Dies ist Codegolf, daher werden die Antworten in Bytes bewertet, wobei weniger Bytes besser sind.

Testfälle

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

Motivationen

Obwohl dieses Problem willkürlich erscheint, ist es tatsächlich ein Problem, auf das ich beim Erstellen von Code zur Verarbeitung grundlegender Polygone gestoßen bin. Dieser Prozess kann verwendet werden, um ein Grundpolygon auf ein kleineres n -gon zu reduzieren . Nachdem ich es ausprobiert hatte, dachte ich, dass es ein schönes kleines Golfspiel werden würde.

code-golf string subsequence Weizen-Assistent
quelle

Wenn die größte Teilzeichenfolge mit Anti-String-Teilzeichenfolgen mehr als eine Anti-String-Teilzeichenfolge enthält, sollten dann alle Teilzeichenfolgen reduziert werden oder nur die ersten beiden?

Jonathan Frech

@ JonathanFrech Irgendwelche zwei. Das ist ein Fall, in dem es ein Unentschieden zwischen Kandidatenpaaren gibt.

Wheat Wizard

Also aaaAAAaaa -> aAaaa?

Jonathan Frech

Etwas an einer Untergruppe dieses Problems schreit laut, aber ich kann es nicht genau sagen.

Magic Octopus Urn

1

@MagicOctopusUrn So etwas wie Zwei-Zyklen-Quine schreiben, bei der die Programmausgabe das Antistring ist ?

Jonathan Frech

8

Perl, 64 61 Bytes

Enthält +1fürp

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

Tonne Hospel
quelle

6

JavaScript (ES6), 200 Byte

Verwendet Arrays von Zeichen für E / A.

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

Probieren Sie es online!

Arnauld
quelle

3

Netzhaut , 119 Bytes

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

Probieren Sie es online! Link enthält Testfälle. Erläuterung:

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

Duplizieren Sie die Eingabe und drehen Sie die Groß- / Kleinschreibung der ersten Kopie um.

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

Wenn überhaupt keine Anti-Strings vorhanden sind, löschen Sie das gespiegelte Duplikat.

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

Listen Sie alle möglichen reduzierten Anti-Strings auf.

N$`
$.&
}0G`

Sortieren Sie sie nach Länge, nehmen Sie die kürzeste (dh längste Anti-String) und wiederholen Sie, bis alle Anti-Strings zusammengebrochen sind.

Neil
quelle

3

Python 3 , 189 181 Bytes

Dank an Jonathan Frech, der es zu einem reinen Einzeiler gemacht hat.

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

Probieren Sie es online!

Meine eigene Version, jetzt veraltet (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

Probieren Sie es online!

any()geschachtelte Schleifen frühzeitig ausbrechen und set()für veränderbare globale Objekte im Verständnis verwendbar. Der Rest ist nur die unkomplizierte Umsetzung der Anforderungen mit 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

Probieren Sie es online!

Es stellt sich heraus, dass reguläre verschachtelte for-Schleifen mit frühem Durchbruch returnviel kürzer sind als der "clevere" Trick mit any.

Bubbler
quelle

181 Bytes ; rekursiver Ansatz. Die setals Funktion voreingestellte Variable wird nicht mit weiteren Aufrufen kollidieren, da ich denke, dass Ihr Code die Menge vollständig als leer markiert.

Jonathan Frech

Entschuldigung, ich dachte, das xwäre nicht leer. Wie Sie es haben, denke ich, entspricht es.

Jonathan Frech

Das ist in Ordnung und danke für die Verbesserung.

Bubbler

3

C (GCC) , 240 238 227 225 222 216 Bytes

Zwei Bytes gespeichert; streunende Variablendefinition entfernt.
~~Elf~~ dreizehn Bytes gespeichert ; golfed b|=S[p+m]!=S[q+m]+32-(S[q+m]>90)*64bis b|=abs(S[p+m]-S[q+m])-32zu b|=32-S[p+m]+S[q+m]&63.
Drei Bytes gespeichert; golfen for(...;...;p++)S[p+1]=S[p+L];zu for(...;...;S[++p]=S[p+L]);.
Dank ceilingcat sechs Bytes gespart .

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

Probieren Sie es online!

Jonathan Frech
quelle

@ceilingcat Vielen Dank.

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

Probieren Sie es online!

Chas Brown
quelle

0

Stax , 30 Bytes

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

Führen Sie es aus und debuggen Sie es

Dies ist die entsprechende ASCII-Darstellung desselben Programms.

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

Es wird ein regulärer Ansatz verwendet. Ersetzt wiederholt reguläre Zeichenfolgen. Diese werden aus jeder zusammenhängenden Teilzeichenfolge des aktuellen Werts erstellt. Zum Beispiel für die Eingabe fAbbAcGfaBBagFist einer der Teilstrings AbbA. In diesem Fall wird der reguläre Ausdruck AbbA(.*)aBBadurch ersetzt 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

rekursiv
quelle

0

Wolfram-Sprache (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]]&

Probieren Sie es online!

Alephalpha
quelle

0

Japt `-h` , 33 Bytes

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

Versuch es

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

Zottelig
quelle

Reduzieren Sie das Antistring

Testfälle

Motivationen

Antworten:

Perl, 64 61 Bytes

JavaScript (ES6), 200 Byte

Netzhaut , 119 Bytes

Python 3 , 189 181 Bytes

Python 2 , 160 Bytes

C (GCC) , 240 238 227 225 222 216 Bytes

Python 2 , 180 Bytes

Stax , 30 Bytes

Wolfram-Sprache (Mathematica) , 148 Bytes

Japt `-h` , 33 Bytes

Reduzieren Sie das Antistring

Testfälle

Motivationen

Antworten:

Perl, 64 61 Bytes

JavaScript (ES6), 200 Byte

Netzhaut , 119 Bytes

Python 3 , 189 181 Bytes

Python 2 , 160 Bytes

C (GCC) , 240 238 227 225 222 216 Bytes

Python 2 , 180 Bytes

Stax , 30 Bytes

Wolfram-Sprache (Mathematica) , 148 Bytes

Japt -h , 33 Bytes

Japt `-h` , 33 Bytes