Dies wurde durch eine jetzt entfernte CS.SE-Frage inspiriert .
Aufgabe
Geben Sie bei zwei nicht leeren Eingabezeichenfolgen A und B den kleinsten Abstand von A zu einem Palindrom aus, das B als Teilzeichenfolge enthält. Die Entfernung wird durch die Anzahl der Zeichenersetzungen ( Hamming-Entfernung ) definiert.
Beschränkungen
- Sinnvolle Eingabe: Ein Palindrom existiert. Dies bedeutet | A | ≥ | B |.
- A und B enthalten nur kleinere ASCII-Zeichen. Kleinbuchstaben und Großbuchstaben sind unterschiedlich (wie alle anderen Zeichen auch).
- Wenn Ihre Sprache keine ASCII-Zeichen verarbeiten kann, können Sie auch Ganzzahlen (oder einen anderen sinnvollen Datentyp) verwenden und den Bereich auf 128 Elemente beschränken.
- Sie können Eingaben über stdin, Funktionsargumente, Befehlszeilenargumente usw. vornehmen.
- Sie können das Ergebnis auf stdout, Rückgabewert usw. angeben.
- Sie müssen kein funktionierendes Palindrom angeben, der kleinste Abstand zu einem ist ausreichend.
Beispiele
A B Output
thilloaoyreot hello 4 (thelloaolleht)
benjonson stack 9 (stackcats)
neversaynever! odd 9 (neveroddoreven)
ppcggcpp gg 0 (ppcggcpp)
stars tat 1 (stats)
Wertung
Dies ist Code Golf, der kürzeste Code in Bytes gewinnt.
code-golf
string
palindrome
Gemeinschaft
quelle
quelle
Pyth, 45 Bytes
Probieren Sie es online aus. Testsuite.
Ich bin immer noch nicht ganz zufrieden mit dem Ergebnis. Aber zumindest ist es jetzt ohne Erklärung ziemlich schwer zu verstehen. (Erfolg, denke ich?)
Erläuterung
Q
und B als aufz
.m
…_BQ
Berechnen Sie für A und seine Umkehrung Folgendesd
:m
…h-ldlz
Berechnen Sie für alle Wertek
von 0 bislen(A) - len(B)
einschließlich Folgendes :+Bklz
Holen Sie sich das Paark, k + len(B)
.cd
Splitd
an diesen Indizes.X
…1z
Ersetzen Sie den zweiten (mittleren) Teil durch B.Ks
Verketten Sie die Teile und speichern Sie sie inK
. B wird jetzt an der Positionk
in A oder umgekehrt eingefügt .hc2
Teilen Sie die resultierende Saite in zwei Teile und behalten Sie das erste Stück. Dies ergibt die Hälfte der Zeichenkette mit dem möglichen mittleren Zeichen.hc2PK
Entfernen Sie das letzte Zeichen und teilen Sie es auf, wobei Sie das erste Stück behalten. Dies ergibt die Hälfte der Zeichenkette ohne das mögliche mittlere Zeichen.+
…_
Fügen Sie die Rückseite des kürzeren Stücks zum längeren Stück hinzu. Wir haben jetzt ein Palindrom.s
Verketten Sie die Ergebnisse für A und seine Umkehrung.f}zT
Entfernen Sie alle Zeichenfolgen, die B nicht enthalten.m
Berechnen Sie für alle resultierenden Zeichenfolgen Folgendesd
:nVQd
Ermitteln Sie die paarweise Ungleichung mit A. Dies ergibt True für Paare, die geändert werden müssen.s
Summiere die Liste. Dies gibt die Hamming-Distanz an.hS
Nimm das minimale Ergebnis.quelle
JavaScript (Firefox 30+),
152146 BytesBrute-Force-Ansatz: Generieren Sie jede mögliche Überlappung von A und B, machen Sie aus jeder ein Palindrom, berechnen Sie Hamming-Abstände von A und nehmen Sie den kleinsten der resultierenden Abstände.
Könnte wohl etwas mehr golfen werden ...
Testschnipsel
Code-Snippet anzeigen
quelle