Herabstufung zu einem Palindrom

47

Geben Sie bei einer gegebenen Zeichenfolge sdie kleinste zusammenhängende Teilzeichenfolge zurück, die Sie entfernen können, um ein Palindrom zu erstellen.


Beispiele:

800233008   -> 2
racecarFOOL -> FOOL
abcdedcba   -> (empty string)
ngryL Myrgn -> "L " (or " M")
123456789   -> 12345678 (or 23456789)
aabcdbaa    -> c (or d)
[[]]        -> [[ (or ]])
a           -> (empty string)

Testfallvorschläge von Benutzern (wenn Sie einen Randfall finden, der nicht aufgeführt ist, senden Sie bitte einen Kommentar):

aabaab      -> b    | Suggested by Zgarb, some returned "aa".

Regeln

  • In der Eingabe werden nur druckbare ASCII-Zeichen angezeigt (keine Zeilenumbrüche, halten Sie es einfach).
  • Nicht wirklich eine Regel, aber beachten Sie <>, /\, (), []und {}sind nicht Palindrome.

Dies ist , die kleinste Anzahl an Bytes gewinnt.


+100 Kopfgeld wurde von Adnan beansprucht

Magische Kraken-Urne
quelle
3
Tesf Fall:aabaab
Zgarb
14
Ich denke, es wird helfen, Fragen für mehr Besucher zugänglich zu halten, wenn Ingroup-Jargon wie „CMC“ vermieden wird (nachschlagen steht es anscheinend für „Chat Mini Challenge“, was meiner Meinung nach eine kleine Herausforderung bedeutet, die im Chatroom gepostet wird, der mit verknüpft ist Diese Seite).
ShreevatsaR
Ist das nicht [[]]ein Palindrom?
Carl
4
@Carl Es mag so aussehen, aber wenn Sie die Zeichen umkehren, erhalten Sie ]][[. Betrachten Sie das aabbist das gleiche, nur verschiedene Charaktere.
Conor O'Brien
1
" (wird 7/12 vergeben) " huh?
Erik der Outgolfer

Antworten:

8

Gelee , 16 Bytes

Ḣ;Ṫµ=Ṛ
0,0jŒṖÇÞṪ

Probieren Sie es online!

Wie es funktioniert

0,0jŒṖÇÞṪ  Main link. Argument: s (string)

0,0j       Join [0, 0], separating by s. This prepends and appends a 0 to s.
    ŒṖ     Build all partitions of the resulting array.
      ÇÞ   Sort the partitions by the helper link.
           As a side effect, this will remove the first and last element of each
           partition. The 0's make sure that not removing any characters from s
           will still remove [0] from both sides.
        Ṫ  Tail; extract the last one.


Ḣ;Ṫµ=Ṛ     Helper link. Argument: A (array/partition)

Ḣ          Head; yield and remove the first chunk of A.
  Ṫ        Tail; yield and remove the last chunk of A.
 ;         Concatenate head and tail.
   µ=Ṛ     Compare the result, character by character, with its reverse.
           A palindrome of length l will yield an array of l 1's, while a
           non-palindrome of length l will yield an array with at least one 0 among
           the first l/2 Booleans. The lexicographically largest result is the one
           with the longest prefix of 1's, which corresponds to the longest
           palindrome among the outfixes.
Dennis
quelle
10

J , 24 Bytes

(0{::(-:|.)\.#&,<\)~i.@#

Probieren Sie es online!

Erläuterung

(0{::(-:|.)\.#&,<\)~i.@#  Input: array of chars S
                       #  Length of S
                    i.@   Range, [0, 1, ..., len(S)-1]
(                 )~      Dyadic verb on range and S
           \.               For each outfix of S of size x in range
        |.                    Reverse
      -:                      Matches input (is palindrome)
                <\          Box each infix of S of size x in range
             #&,            Flatten each and copy the ones that match
 0{::                       Fetch the result and index 0 and return
Meilen
quelle
Vielleicht möchten Sie (;&quote f)&>als Testgeschirr Verb wählen ?
Conor O'Brien
7

Wolfram Language (Mathematica) , 53 51 Bytes

Die Byteanzahl setzt die CP-1252-Codierung voraus.

±{a___,Shortest@b___,c___}/;PalindromeQ[a<>c]:={b}

Probieren Sie es online!

Definiert einen unären Operator ±(oder eine Funktion PlusMinus). Eingabe und Ausgabe sind Listen von Zeichen. Die Testsuite führt die Konvertierung von und zu tatsächlichen Zeichenfolgen aus.

Martin Ender
quelle
Ist der ReverseVergleich mit dem Original dann kürzer als bei PalindromeQ? Ich kenne Mathematica nicht, also keine Ahnung.
Magic Octopus Urn
Gute Antwort, aber sollte man nicht die Aufteilung der Zeichenfolgen und deren Zusammenführung in der Anzahl der Zeichen berücksichtigen? Characters@#/.{a___,Shortest@b___,c___}/;PalindromeQ[a<>c]:>b~~""&
Kelly Lowder
@MagicOctopusUrn Reverse[x={a,c}]==xist zwei Bytes länger. Ich weiß nicht, ob es eine kürzere Alternative gibt.
Martin Ender
@KellyLowder Zeichenlisten sind gültige Darstellungen von Zeichenfolgen in PPCG. In Mathematica ist es etwas umständlich, wenn Sie diese Darstellung normalerweise nicht verwenden, sie jedoch weiterhin gültig ist. Ich werde einen Metapost ausgraben.
Martin Ender
1
@ KellyLowder Ich denke, das ist die akzeptierte Politik . Der Hauptgrund, warum es in Mathematica umständlich ist, ist, dass Mathematica keinen tatsächlichen Zeichentyp hat, sodass die Zeichen Singleton-Zeichenfolgen sind.
Martin Ender
5

05AB1E , 18 Bytes

ā<Œ¯¸«ʒRõsǝÂQ}éнèJ

Verwendet die 05AB1E- Codierung. Probieren Sie es online!

Adnan
quelle
Interessante Verwendung von Filtern dort ... Wir haben versucht, einen Deal vom Typ "a ohne b" zu machen, aber wenn es zwei Instanzen der Teilzeichenfolge gäbe, würden wir falsche Negative erhalten. Es fühlt sich so an, als ob wir es jetzt, da ich das sehe, zu kompliziert hätten. Noice, ich werde dir in 2 Tagen ein Kopfgeld von 100 geben.
Magic Octopus Urn
ǝwar ernsthaft genial.
Magic Octopus Urn
4

Python 3 , 97 Bytes

f=lambda s,p='	':min([s][:p[::-1]in p+p]+(s and[f(s[1:],p+s[0]),f(s[:-1],s[-1]+p)]or[p]),key=len)

Probieren Sie es online!

Dennis
quelle
3

Python 2 , 116 Bytes

def f(i):R=range(len(i)+1);print min([i[y:k+1]for y in R for k in R if(i[:y]+i[k+1:])[::-1]==i[:y]+i[k+1:]],key=len)

Probieren Sie es online!

Mit Hilfe von Halvard Hummel ein paar Bytes gerettet !

Mr. Xcoder
quelle
117 Bytes
Halvard Hummel
@HalvardHummel Danke, ich wollte das auch ändern, hatte aber in den letzten 2 Stunden keine Internetverbindung.
Mr. Xcoder
2

Japt , 26 22 Bytes

¬£¬ËUjEY ꬩUtEY
c æ+0

Online testen! Ich versuche herauszufinden, wie falseich etwas Falsches und eine Zeichenfolge etwas Wahres in einem Byte zuordnen kann. Zur Zeit benutze ich +0...

ETHproductions
quelle
2

Bash , 108 Bytes

for((j=0;;j++)){
for((i=0;i<${#1};i++)){
r=${1:0:i}${1:j+i}
[[ $r = `rev<<<$r` ]]&&echo "${1:i:j}"&&exit
}
}

Übernimmt die Eingabe als Befehlszeilenargument.

Probieren Sie es online! mit Anführungszeichen, die um die Ausgabe gedruckt werden, um führende / nachfolgende Leerzeichen anzuzeigen.

Justin Mariner
quelle
2

Prolog , 271 Byte

p([_]).
p([X,X]).
p([X|Y]):-append([P,[X]],Y),p(P).

s(P,M,S,R,N):-p(P),append([M,S],N).
s(P,M,S,S,N):-p(S),append([P,M],N).
s(P,M,S,P,M):-append([P,S],X),p(X).

d(Y,P,N):-
    findall([A,B,C],(append([R,M,X],Y),s(R,M,X,B,C),length(B,A)),S),
    sort(1,@>,S,[[_,P,N]|_]).

Irgendwann wurde mir klar, dass dies für Code-Golf-Verhältnisse enorm sein wird. Deshalb habe ich ein paar zusätzliche Leerzeichen gelassen, um die Ähnlichkeit mit der nicht verschleierten Version zu bewahren. Aber ich denke immer noch, dass es interessant sein könnte, da es eine andere Herangehensweise an das Problem ist.

Die nicht verschleierte Version:

palindrome([_]).
palindrome([X, X]).
palindrome([X | Xs]) :-
    append([Prefix, [X]], Xs),
    palindrome(Prefix).

palindrome_split(Prefix, Mid, Suffix, Prefix, N) :-
    palindrome(Prefix),
    append([Mid, Suffix], N).
palindrome_split(Prefix, Mid, Suffix, Suffix, N) :-
    palindrome(Suffix),
    append([Prefix, Mid], N).
palindrome_split(Prefix, Mid, Suffix, P, Mid) :-
    append([Prefix, Suffix], P),
    palindrome(P).

palindrome_downgrade(NP, P, N):-
    findall(
        [La, Pa, Na],
        (append([Prefix, Mid, Suffix], NP),
         palindrome_split(Prefix, Mid, Suffix, Pa, Na),
         length(Pa, La)),
        Palindromes),
    sort(1, @>, Palindromes, [[_, P, N] | _]).
wvxvw
quelle
2

C ++, 254 248 246 Bytes

-6 Bytes dank Zacharý -2 Bytes dank Toby Speight

#include<string>
#define S size()
#define T return
using s=std::string;int p(s t){for(int i=0;i<t.S;++i)if(t[i]!=t[t.S-i-1])T 0;T 1;}s d(s e){if(!p(e))for(int i,w=1;w<e.S;++w)for(i=0;i<=e.S-w;++i){s t=e;t.erase(i,w);if(p(t))T e.substr(i,w);}T"";}

Damit...

  • Ich habe es Tals Makrodefinition verwendet, weil es einen R""weiteren Effekt auf das Stringliteral hat (es ist ein Präfix, das verwendet wird, um unformatierte Stringliterale zu definieren, siehe cppreference für weitere Informationen), der nicht vorhanden ist, wenn ich es tueT""
  • Präprozessordefinitionen dürfen nicht in derselben Zeile stehen und müssen mindestens ein Leerzeichen zwischen dem Namen und dem Inhalt der Definition enthalten
  • 2 Funktionen: um p(std::string)zu testen, ob die Zeichenfolge ein Palindrom ist. Wenn dies 1der Fall ist, wird zurückgegeben, wohin gewirkt wird true, andernfalls wird zurückgegeben 0, wohin gewirkt wirdfalse
  • Der Algorithmus durchläuft die gesamte Zeichenfolge und testet, ob es sich beim Löschen jedes Elements um ein Palindrom handelt. Anschließend testet er das Löschen von 2 Elementen (durchläuft die Schleife bis zur maximalen Größe der Zeichenfolge) vom ersten Index bis zum the last index - number of erased char. Wenn das Löschen eines Teils ein Palindrom ist, kehrt es zurück. Wenn Sie beispielsweise die Zeichenfolge "aabcdbaa"als Parameter übergeben, sind beide cund deine gültige Antwort. Dieser Code wird jedoch zurückgegeben, cda er gelöscht und geprüft wird, ob es sich um ein Palindrom handelt, bevor geprüft wird, ob er gelöscht dund ob es sich um ein Palindrom handelt
  • Hier ist der Code zum Testen:

    std::initializer_list<std::pair<std::string, std::string>> test{
        {"800233008","2"},
        { "racecarFOOL","FOOL" },
        { "abcdedcba","" },
        { "ngryL Myrgn","L " },
        { "123456789","12345678" },
        { "aabcdbaa","c" },
        { "[[]]","[[" },
        { "a","" },
        { "aabaab","b" }
    };
    
    for (const auto& a : test) {
        if (a.second != d(a.first)) {
            std::cout << "Error on : " << a.first << " - Answer : " << a.second  << " - Current : " << d(a.first) << '\n';
        }
    }
HatsuPointerKun
quelle
Würde das für die letzte Zeile funktionieren? using s=std::string;int p(s t){for(int i=0;i<t.S/2;++i)if(t[i]!=t[t.S-i-1])T 0;T 1;}s d(s e){if(!p(e))for(int i,w=1;w<e.S;++w)for(i=0;i<=e.S-w;++i){s t=e;t.erase(i,w);if(p(t))T e.substr(i,w);}T"";}
Zacharý
Kann das /2weggelassen werden? Wenn Sie über die gesamte Länge iterieren, wiederholen Sie einfach die von uns durchgeführten Tests, die harmlos sein sollten. Vielleicht möchten Sie erweitern, was Sie mit dem "anderen Effekt" von meinen R""(dh es wird als unformatiertes String-Literal analysiert).
Toby Speight
Ich habe dies geändert und das Ergebnis als eigene Antwort hinzugefügt .
Toby Speight
1

Gelee , 33 Bytes

r/ḟ@J}ị
“”µJp`ç³$ŒḂ$Ðfạ/ÞḢr/ịµŒḂ?

Probieren Sie es online!

HyperNeutrino
quelle
1

PHP 104 + 1 Bytes

while(~($s=$argn)[$e+$i++]?:++$e|$i=0)strrev($t=substr_replace($s,"",$i,$e))==$t&&die(substr($s,$i,$e));

Laufen Sie als Pipe mit -nRoder versuchen Sie es online .

Titus
quelle
1

Haskell , 109 105 Bytes

snd.minimum.([]#)
p#s@(a:b)=[(i,take i s)|i<-[0..length s],(==)<*>reverse$p++drop i s]++(p++[a])#b
p#_=[]

Probieren Sie es online!

EDIT: Danke @ H.PWiz für das Abheben von 4 Bytes! Ich muss mit diesen Monaden besser werden!

user1472751
quelle
1

JavaScript, 90 Bytes

a=>a.map((_,p)=>a.map((_,q)=>k||(t=(b=[...a]).splice(q,p),k=''+b==b.reverse()&&t)),k=0)&&k

Probieren Sie es online!


quelle
1

Perl 5, 72 + 1 (-p) Bytes

$\=$_;/.*(?{$,=$`.$';$\=$&if length$&<length$\&&$,eq reverse$,})(?!)/g}{

Probieren Sie es online aus

Nahuel Fouilleul
quelle
1

JavaScript (ES6), 91 bis 78 Byte

(s,i=0,j=0,S=[...s],b=S.splice(i,j))=>S+''==S.reverse()?b:f(s,s[++i]?i:!++j,j)

Eingabe und Ausgabe sind Listen von Zeichen.

Entfernt rekursiv einen immer größeren Ausschnitt aus der Eingabe, bis ein Palindrom gefunden wird.

Snippet:

Rick Hitchcock
quelle
1

TSQL (2016) 349B

Nicht die kompakteste, aber unkomplizierte Lösung:

DECLARE @i VARCHAR(255)='racecarFOOL'
;WITH DAT(v,i,l)AS(SELECT value,(ROW_NUMBER()OVER(ORDER BY value))-1,LEN(@i)FROM STRING_SPLIT(REPLICATE(@i+';',LEN(@i)+1),';')WHERE value<>'')
SELECT TOP 1C,S
FROM(SELECT LEFT(D.v, D.i)+SUBSTRING(D.v,D.i+E.i+1,D.l)C,SUBSTRING(D.v,D.i+1,E.i)S
FROM DAT D CROSS APPLY DAT E)C
WHERE C=REVERSE(C)
ORDER BY LEN(C)DESC
Jan Drozen
quelle
Sie können @als Variable für einige Bytes verwenden. In der CTE können Sie where''=value)für einen anderen verwenden und müssen nicht Cin das Ergebnis zurückkehren.
MickyT
1

Schale , 18 Bytes

◄LfmS=↔†!⁰ṠM-Qŀ⁰Q⁰

Probieren Sie es online!

Erläuterung

◄LfmS=↔†!⁰ṠM-Qŀ⁰Q⁰  Input is a string, say s="aab"
              ŀ⁰    Indices of s: x=[1,2,3]
             Q      Slices: [[],[1],[1,2],[2],[1,2,3],[2,3],[3]]
          ṠM-       Remove each from x: [[1,2,3],[2,3],[3],[1,3],[],[1],[1,2]]
       †!⁰          Index into s: ["aab","ab","b","ab","","a","aa"]
   mS=↔             Check which are palindromes: [0,0,1,0,1,1,1]
  f             Q⁰  Filter the slices of s by this list: ["aa","aab","ab","b"]
◄L                  Minimum on length: "b"
Zgarb
quelle
1

Haskell , 98 94 81 80 Bytes

""#0
(h#n)t|(==)=<<reverse$h++drop n t=take n t|x:r<-t=(h++[x])#n$r|m<-n+1=t#m$h

Probieren Sie es online! Anwendungsbeispiel: ""#0 $ "aabaab"Erträge "b".

Edit: -1 Byte danke an Ørjan Johansen.

Laikoni
quelle
1
Sie können den letzten ""durch ersetzen t.
Ørjan Johansen
1

C ++, 189 186 176 167 Bytes

Ich begann mit der Antwort von HatsuPointerKun und änderte den Test, um die Gleichheit einfach mit der umgekehrten Zeichenfolge zu vergleichen. dann habe ich geändert, wie wir die Kandidaten-Strings aufzählen. Danach wurden die Makros jeweils nur ein- oder zweimal verwendet, und es war kürzer, sie inline zu setzen.

#include<string>
using s=std::string;s d(s e){for(int i,w=0;;++w){s t=e.substr(w);for(i=-1;++i<=t.size();t[i]=e[i])if(t==s{t.rbegin(),t.rend()})return e.substr(i,w);}}

Erläuterung

Äquivalenter lesbarer Code:

std::string downgrade(std::string e)
{
    for (int w=0; ; ++w) {
        std::string t = e.substr(w);
        for (int i=0;  i<=t.size();  ++i) {
            if (t == std::string{t.rbegin(),t.rend()})
                // We made a palindrome by removing w chars beginning at i
                return e.substr(i,w);
            t[i] = e[i];  // next candidate
        }
    }
}

Die Aufzählung der Kandidaten beginnt mit der Initialisierung einer Zeichenfolge, wobei die ersten wZeichen weggelassen werden. Anschließend werden aufeinanderfolgende Zeichen aus dem Original kopiert, um die Lücke zu schließen. Zum Beispiel mit dem String foobarund w== 2:

foobar
  ↓↓↓↓
  obar
foobar
↓
fbar
foobar
 ↓
foar
foobar
  ↓
foor
foobar
   ↓
foob

Der erste Durchgang (mit w== 0) ist ein No-Op, daher wird der gesamte String immer wieder berücksichtigt. Das ist in Ordnung - Golfen übertrifft Effizienz! Die letzte Iteration dieser Schleife greift auf den One-Past-The-End-Index zu. Ich scheine mit GCC davonzukommen, aber genau genommen ist das Undefined Behaviour.

Testprogramm

Ein direkter Auszug aus der Antwort von HatsuPointerKun :

static const std::initializer_list<std::pair<std::string, std::string>> test{
    { "800233008", "2" },
    { "racecarFOOL", "FOOL" },
    { "abcdedcba", "" },
    { "ngryL Myrgn", "L " },
    { "123456789", "12345678" },
    { "aabcdbaa", "c" },
    { "[[]]", "[[" },
    { "a","" },
    { "aabaab", "b" }
};

#include <iostream>
int main()
{
    for (const auto& a : test) {
        if (a.second != d(a.first)) {
            std::cout << "Error on: " << a.first
                      << " - Expected: " << a.second
                      << " - Actual: " << d(a.first) << '\n';
        }
    }
}
Toby Speight
quelle
0

REXX, 132 Bytes

a=arg(1)
l=length(a)
do i=1 to l
  do j=0 to l-i+1
    b=delstr(a,i,j)
    if b=reverse(b) & m>j then do
      m=j
      s=substr(a,i,j)
      end
    end
  end
say s
idrougge
quelle
0

Ruby , 86 84 Bytes

->s{l=i=0
(l+=(i+=1)/z=s.size-l+1
i%=z)while(w=s[0,i]+s[i+l..-1])!=w.reverse
s[i,l]}

Probieren Sie es online!

  • 2 Bytes gespart dank Cyoce
iamnotmaynard
quelle
Die Klammern brauchen Sie nicht z=s.size-l+1.
Cyoce
@Cyoce Danke. Es fällt mir schwer, mich an die Rangfolge der Bediener zu erinnern.
iamnotmaynard
0

C (gcc) , 307 Bytes

#define T malloc(K)
P(S,i,y,z,k,u,L,K,V)char*S;{char*M,*R,*E;K=strlen(S);M=T;R=T;E=T;for(i=0;i<K;++i){for(y=0;y<=K-i;++y){strcpy(M,S);for(z=y;z<y+i;E[z-y]=M[z],++z);for(k=y;k+i<=K;M[k]=M[k+i],++k);V=strlen(M);strcpy(R,M);for(u=0;u<V/2;L=R[u],R[u]=R[V-u-1],R[V-u-1]=L,++u);if(!strcmp(M,R))puts(E),exit(0);}}}

Probieren Sie es online!

R. Kap
quelle