Palindromabstand
Finden Sie heraus, wie weit eine bestimmte Saite von ihrem nächsten Palindrom gleicher Länge entfernt ist.
Für diese Aufgabe habe ich beschlossen, den Zeichen, die weiter von der Mitte der Saite entfernt sind, mehr Gewicht zu geben (denken Sie daran, dass sie mehr Drehmoment beitragen), proportional zu ihrem Abstand zur Mitte.
Definieren wir den Palindromabstand für einen String \$s\$ als die Summe aller Produkte der absoluten Differenz der entsprechenden Paare, die gleichmäßig von der Mitte der Saite beabstandet sind, und deren Abstand zur Mitte.
\.$D_p=\displaystyle\sum_{i=1}^{d}\left(d-i+1\right)|s_i-s_{l-i+1}|\$
wo \$l\$ist die Länge von \$s\$und \$d = \left\lfloor\frac{l}{2}\right\rfloor\$
Da das mittlere Zeichen nichts zur Summe beiträgt, \$d\$für Strings mit ungerader Länge \$l\$ist gleich \$d\$für Strings mit der Länge \$l-1\$.
Aufgabe
Gegebene Zeichenfolge \$s\$mit einer Länge> 1 find \$D_p(s)\$
Eingang
Einer der folgenden:
- ein Faden;
- eine Liste von Zeichen;
- eine Liste von Zahlen.
Ausgabe
Eine Ganzzahl - der Palindromabstand der Eingabezeichenfolge.
Testfälle
"aa" -> 0
"bab" -> 0
"abca" -> 1
"cbade" -> 6
"hello" -> 21
"code-golf" -> 45
"neveroddoreven" -> 0
"Neveroddoreven" -> 224
Gewinnkriterien
Der kürzeste Code in Bytes in jeder Sprache gewinnt.
Sandkasten
Antworten
Haskell , 50 Bytes
u#(a:b)|c:d<-reverse b=u+(abs(c-a)+u)#d
u#_=u
(0#)
Probieren Sie es online aus!
Schau ma! Keine Multiplikation! (oder Teilung)
Erläuterung
Anstatt zu erklären, was diese Antwort bewirkt, was meiner Meinung nach nur verwirrend wäre, werde ich eine kurze Erklärung geben, wie ich zu dieser Antwort gekommen bin.
Zunächst einmal ist Haskell eine rekursive Sprache, daher möchten wir dies rekursiv formulieren. Dies ist ziemlich einfach, wenn wir eine Liste haben
[ a , d... , c ]
Dann nehmen wir den "Palindromabstand" des mittleren Bits dund addieren ihn abs(a-c)*(div(length d)2). Wenn es etwas anderes ist, ist die Antwort Null.
Jetzt ist es in Haskell etwas schwierig, das letzte Element zu bekommen, aber das erste zu bekommen ist kinderleicht. Eine Möglichkeit, das letzte Element zu erhalten, besteht darin, die Liste umzukehren und das erste zu erhalten. Um die Mitte zu erhalten, müssen wir diese auf die ursprüngliche Reihenfolge zurücksetzen.
Unser erster Durchbruch besteht darin, zu erkennen, dass sich der "Palindromabstand" beim Umkehren einer Saite nicht ändert. Wir müssen also den Mittelteil nicht in seine ursprüngliche Reihenfolge zurückversetzen, da die Berechnung der umgekehrten Reihenfolge ohnehin das richtige Ergebnis liefert.
f(a:b)|c:d<-reverse b= ...
Alles in allem lautet unser Code also:
f(a:b)|c:d<-reverse b=f d+abs(a-c)*div(length d)2
f _=0
Ok aber lengthund divsind irgendwie teuer. Die Anzahl der verbleibenden Schritte ist wirklich genau das, wonach wir suchen. Was wäre, wenn wir das nutzen würden, um uns zu helfen?
f(a:b)|c:d<-reverse b,(k,n)=(k+abs(a-c)*n,n+1)
f _=(0,1)
g=fst.f
Nun, das hat nicht geholfen, aber wir sind hier auf etwas. Die Multiplikation ist nur eine wiederholte Addition. Wir möchten also wirklich abs(a-c)einmal für jede verbleibende Iteration addieren . Warum verfolgen wir also nicht die Zahlen, die wir hinzufügen möchten, und fügen sie einfach auf dem Weg nach unten hinzu?
u#(a:b)|c:d<-reverse b=sum u+(abs(c-a):u)#d
u#_=sum u
g=([]#)
Hier haben wir also dieses zusätzliche Argument, udas nur die Liste aller absoluten Unterschiede ist. Und bei jeder Iteration addieren wir die Summe davon zum Ergebnis der nächsten Iteration. Auf diese Weise wird jeder Unterschied um das Vielfache der Anzahl der Schritte vom Zentrum addiert, wobei er im Wesentlichen mit seinem Abstand vom Zentrum multipliziert wird.
Da wir immer nur unach seiner Summe fragen, müssen wir die Werte natürlich nicht trennen. Wir können einfach die laufende Summe verfolgen, um einige Bytes zu sparen.
u#(a:b)|c:d<-reverse b=u+(abs(c-a)+u)#d
u#_=u
g=(0#)
Und das gibt uns den endgültigen Code.
05AB1E , 8 Bytes
-1 Byte, danke an Kevin Cruijssen , der mich daran erinnert hat, dass Eingaben als Listen von ganzen Zahlen verwendet werden können.
Âα2äθā*O
Probieren Sie es online aus!
Kommentiert:
# implicit input: a list of codepoints
 # push codepoints and codepoints reversed
α # take the (element-wise) absolute difference
2ä # split into 2 pieces
# the last one will be shorter for odd lengths
θ # take the last piece
ā # length-range: [1, ..., length] (doesn't pop the TOS)
* # multiply element-wise
O # take the sum
R , 50 47 Bytes
Bearbeiten: -3 Bytes dank Giuseppe, indem der %*%Operator verwendet wird, um das innere Produkt von Vektoren zu berechnen, anstatt das Produkt von Elementen als separate Operationen zu summieren
abs((rev(x<-scan())-x)[(y=sum(x|1)/2):1])%*%1:y
Probieren Sie es online aus!
Akzeptiert die Liste der Nummern.
Code ohne Golf:
x=scan() # x is vector of numbers
y=sum(x|1)/2) # y is half the length of x
sum( # return the sum of...
abs( # the absolute values of...
(x-rev(x)) # the differences between each element of x
# and the same elements reversed...
[y:1] # at positions y..1
# (so only the first half, backwards)...
*1:y)) # multiplied by 1..y
C (gcc) , 74 \$\cdots\$ 52 51 Bytes
Gespeichert 6 7 Bytes dank AZTECCO !!! Dank Dominic van Essen 9 und 15 Bytes
gespart !!!
f(s,l)int*s;{l=l>1?l/2*abs(*s++-s[l-=2])+f(s,l):0;}
Probieren Sie es online aus!
Port meiner Python 3 Antwort .
JavaScript (ES6), 61 57 Byte
Erwartet eine Liste von ASCII-Codes.
f=a=>1/a?0:(a.length>>1)*Math.abs(a.shift()-a.pop())+f(a)
Probieren Sie es online aus!
Wie?
Dies ist eine ziemlich einfache rekursive Implementierung, die bei jeder Iteration den ersten und den letzten Eintrag aus der Liste entfernt, den absoluten Wert ihrer Differenz berechnet und das Gewicht \ anwendet$\lfloor L/2 \rfloor\$, wo \$L\$ ist die Länge der Liste, bevor die Elemente entfernt werden.
Das 1 / aStoppkriterium ist wahr, wenn entweder:
a[]ist in diesem Fall leer1 / a == Infinity. Dies geschieht, wenn die Länge der Eingabeliste gerade ist.Oder
a[]ist eine Singleton-Ganzzahl, die auftritt, wenn die Länge der Liste ungerade ist. Wir können die Rekursion ohne weitere Berechnung sicher stoppen, da ein einzelnes Zeichen ein Palindrom ist und wir zu diesem Zeitpunkt bereits das Endergebnis haben.
Python 2 , 57 54 Bytes
Eine rekursive Funktion, die Eingaben als Liste von Ganzzahlen verwendet.
f=lambda l:l>[]and len(l)/2*abs(l[0]-l[-1])+f(l[1:-1])
Probieren Sie es online aus!
Der letzte Teil könnte auch abs(l[0]-l.pop())+f(l[1:])gleich lang sein.
Python 2 , 57 Bytes
Ein etwas längerer Ansatz ohne Rekursion.
lambda l:eval(len(l)/2*'+len(l)/2*abs(l.pop(0)-l.pop())')
Probieren Sie es online aus!
Holzkohle , 22 Bytes
ＩΣＥ∕θ²×⁻Ｌ∕θ²κ↔⁻℅ι℅§⮌θκ
Probieren Sie es online aus! Der Link führt zur ausführlichen Version des Codes. Nimmt die Eingabe als Zeichenfolge vor (das Halbieren einer Zeichenfolge ist golfhafter als das Halbieren eines Arrays). Erläuterung:
θ Input string
∕ ² First half
Ｅ Map over characters
κ Current index
⁻ Subtracted from
Ｌ∕θ² Length of half of string
× Multiplied by
↔⁻ Absolute difference of
℅ ℅ Ordinals of
ι Current character and
§ Character at
κ Current index in
⮌ Reversed
θ Input string
Σ Take the sum
Ｉ Cast to string
Implicitly print
Alternativer Ansatz, auch 22 Bytes:
ＩΣＥ⮌∕⮌θ²×⊕κ↔⁻℅ι℅§⮌∕θ²κ
Probieren Sie es online aus! Der Link führt zur ausführlichen Version des Codes. Erläuterung:
θ Input string
⮌ Reversed
∕ ² "First" half
⮌ Reversed i.e. last "half"
Ｅ Map over characters
κ Current index
⊕ Incremented
× Multiplied by
↔⁻ Absolute difference of
℅ ℅ Ordinals of
ι Current character and
§ Character at
κ Current index in
⮌ Reversed
∕θ² First half of input string
Σ Take the sum
Ｉ Cast to string
Implicitly print
TECO , 53 Bytes
- Q-Register A hat den Initialisierungscode.
*:ga
$$ j0uaz-1ub0uu0uw$$*
- Q-Register M addiert alles. Das Ergebnis bleibt im Q-Register W.
:gm$$ z/2<0ua0a-(qba)%a"L-qaua'qa%u%w$c-2%b>$$*
- Ein Beispiel zur Berechnung von \ $ D_p \ $ von "Neveroddoreven": Töten Sie den gesamten Puffer, fügen Sie Ihr Wort ein, initialisieren Sie die Register A, B, U und W und springen Sie zum Anfang des Puffers. dann z / 2-mal iterieren und sich im Register W ansammeln; zeigen schließlich den numerischen Inhalt von Register W.
hkiNeveroddoreven$mamm$$ *qw=$$
224
*
- Das komplette Programm und seine Länge.
*ht$$ j0uaz-1ub0uu0uwz/2<0ua0a-(qba)%a"L-qaua'qa%u%w$c-2%b>*z=$$
53
- Die Testfälle.
"aa" -> 0
"bab" -> 0
"abca" -> 1
"cbade" -> 6
"hello" -> 21
"code-golf" -> 45
"neveroddoreven" -> 0
"Neveroddoreven" -> 224
Dies zeigt eine TECO-Sitzung, in der jedes Testwort in den leeren Bearbeitungspuffer eingefügt wird, dann die Makros der Q-Register A und M aufgerufen werden und schließlich das \ $ D_p \ $ angezeigt wird , das im numerischen Q-Register W akkumuliert wurde.
*hkiaa$mammqw=$$ 0 *hkibab$mammqw=$$ 0 *hkiabca$mammqw=$$ 1 *hkicbade$mammqw=$$ 6 *hkihello$mammqw=$$ 21 *hkicode-golf$mammqw=$$ 45 *hkineveroddoreven$mammqw=$$ 0 *hkiNeveroddoreven$mammqw=$$
224
APL (Dyalog Unicode) , 21 Bytes
{+/|⍵×⍳≢⍵}(⌈2÷⍨⍴)↓⊢-⌽
Probieren Sie es online aus!
C (gcc) , 55 52 Bytes
f(a,z)char*a;{z=z/2?z/2*abs(*a++-a[z-=2])+f(a,z):0;}
Probieren Sie es online aus!
- Ein bisschen Stehlen von @ Noodle9 und Neuanordnungen gespeichert
f (a, z) char * a; {z = - Funktion, die einen C-String-Zeiger und seine Länge anheftet
und Rückkehr durch jedes Register.
z / 2? - wenn nicht in der Mitte:
f (a + 1, z-2)> rekursiver Aufruf mit bewegtem Zeiger und verringerter Länge
+ abs (* aa [z-1]) * (z / 2)
- Mehrwert von Paaren
: 0;}> sonst initialisiere r auf 0
Gelee , 7 Bytes
ạṚŒHṪḋJ
Ein monadischer Link, der eine Liste von Ganzzahlen akzeptiert, die eine Ganzzahl ergibt.
Probieren Sie es online aus!
Wie?
ạṚŒHṪḋJ - Link: list of integers, A e.g. (Abracadabra) [65,98,114,97,99,97,100,97,98,114,97]
Ṛ - reverse (A) [97,114,98,97,100,97,99,97,114,98,65]
ạ - absolute difference (vectorises) [32,16,16,0,1,0,1,0,16,16,32]
ŒH - split in two (1st part longest, if any) [[32,16,16,0,1,0],[1,0,16,16,32]]
Ṫ - tail [1,0,16,16,32]
J - range of length (of A) [1,2,3,4,5,6,7,8,9,10,11]
ḋ - dot-product 273 (= 1×1+0×2+16×3+16×4+32×5+0×6+...0×11)
Schale , 14 12 11 Bytes
-2 Dank des Weizen-Assistenten können Sie Eingaben als Liste von Codepunkten verwenden
und -1 dank HP.Wiz, das zeigt, dass ≠ nicht nur Ungleichheit, sondern absoluten Unterschied macht
ΣFoz*ŀ½Sz≠↔
Probieren Sie es online aus!
Erläuterung
Sz≠ Zip absolute difference the list from
↔ The reverse of the list
½ Split the list into two halves (with the longer being the first)
F Reduce by
o ŀ Converting the first half to range(1, length)
z* And zip multiplying with the second half
Σ Finally sum the absolute values
Wolfram Language (Mathematica) , 53 Bytes
f@_:0=0
f[a_,b___,c_]:=Abs[a-c]⌈Length@a?b/2⌉+f@b
Probieren Sie es online aus!
Nimmt eine Liste von ganzen Zahlen.
Length@a?bspart ein Byte über Tr[1^{a,b}]/ Length[a.b]dank der PatternTesthohen Priorität.
Python 3 , 59 Bytes
f=lambda l:len(l)>1and len(l)//2*abs(l.pop(0)-l.pop())+f(l)
Probieren Sie es online aus!
J , 24 Bytes
+/@(#\.@]*|@-)&(,~inv)|.
Probieren Sie es online aus!
Übernimmt die Eingabe als Liste von Ganzzahlen.
Ein weiteres interessantes Problem, das in J. unerwartet schwer auszudrücken ist. Ich habe einige Ansätze ausprobiert, und dies ist mein bester Versuch.
Wie
(...)|.Die gesamte Phrase ist ein Hook, was bedeutet, dass die ursprüngliche Eingabe und die umgekehrte Eingabe|.als linkes bzw. rechtes Argument an die Phrase in Klammern übergeben werden.(...)&(,~inv)Die Compose-Konjunktion&transformiert in diesem Fall beide Argumente mit dem angegebenen Verb,~inv.,~invist die Umkehrung des Verbs, das eine Liste durch Selbstanhängen verdoppelt,~. Die Umkehrung dieser Operation besteht darin, die erste Hälfte der Liste zu nehmen, und sie wird für ungerade Listen "abgerundet", was wir hier wollen.
#\.@]*|@-#\.@]Elementweise mit multiplizieren|@-|@-subtrahieren Sie die beiden Listenargumente elementweise und nehmen Sie den absoluten Wert|. Dies sind die "Entfernungen".#\.@]erzeugt zB,4 3 2 1wenn die Listen die Länge 4 haben. Dazu werden die Suffixlängen#\.des richtigen Arguments verwendet]. Wir hätten das linke Argument hier genauso gut verwenden können.
+/@Summiere das Ergebnis
Zum Vergleich beträgt die in J konvertierte APL-Lösung 25 Byte:
>.@-:@#(1#.]*&|#\)@}.]-|.
Probieren Sie es online aus!