Zmień na Palindrom

47

Podany ciąg szwraca najmniejszy ciągły podciąg, który można usunąć, aby utworzyć palindrom.


Przykłady:

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

Sugestie dotyczące przypadków testowych od użytkowników (jeśli znajdziesz przypadek krawędzi nie wymieniony na liście, opublikuj komentarz):

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

Zasady

  • Na wejściu pojawią się tylko drukowalne znaki ASCII (bez nowych linii, uprość to).
  • Naprawdę nie jest regułą, ale uwaga <>, /\, (), []i {}nie są palindromy.

To jest , najmniejsze wygrane w liczbie bajtów.


Adnan odebrał +100 nagród

Urna Magicznej Ośmiornicy
źródło
3
Sprawa Tesf:aabaab
Zgarb,
14
Myślę, że pomoże to w zapewnieniu dostępu do pytań większej liczbie odwiedzających, jeśli uniknie się żargonu w grupie, takiego jak „CMC” (patrząc na to, wygląda na to, że oznacza „mini-wyzwanie czatu”, co, jak sądzę, oznacza małe wyzwanie opublikowane w pokoju czatu związane z ta strona).
ShreevatsaR
Czy to nie [[]]jest palindrom?
Carl
4
@ Carl Może to wyglądać jak jeden, ale kiedy odwrócisz postacie, otrzymasz ]][[. Pomyśl, że aabbto to samo, tylko różne postacie.
Conor O'Brien
1
(otrzyma 7/12) ”, co?
Erik the Outgolfer,

Odpowiedzi:

8

Galaretka , 16 bajtów

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

Wypróbuj online!

Jak to działa

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
źródło
10

J , 24 bajty

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

Wypróbuj online!

Wyjaśnienie

(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
mile
źródło
Być może możesz chcieć wybrać (;&quote f)&>czasownik testowy?
Conor O'Brien
7

Wolfram Language (Mathematica) , 53 51 bajtów

Liczba bajtów zakłada kodowanie CP-1252.

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

Wypróbuj online!

Definiuje jednoargumentowy operator ±(lub funkcję PlusMinus). Dane wejściowe i wyjściowe są listami znaków. Dla wygody zestaw testów wykonuje konwersję zi na rzeczywiste ciągi.

Martin Ender
źródło
Czy Reversezatem porównanie tego odwrotności do oryginału jest krótsze niż PalindromeQ? Nie znam Mathematiki, więc nie mam pojęcia.
Magic Octopus Urn
Dobra odpowiedź, ale czy nie powinno się brać pod uwagę dzielenia łańcuchów i łączenia ich z powrotem w twojej postaci? Characters@#/.{a___,Shortest@b___,c___}/;PalindromeQ[a<>c]:>b~~""&
Kelly Lowder,
@MagicOctopusUrn Reverse[x={a,c}]==xma dwa bajty dłużej. Nie wiem, czy jest jakaś krótsza alternatywa.
Martin Ender,
@ KellyLowder Listy znaków są prawidłowymi reprezentacjami ciągów w PPCG. Jest to trochę niewygodne w Mathematica, gdzie normalnie nie użyłbyś tej reprezentacji, ale nadal jest ważna. Wykopię meta post.
Martin Ender,
1
@KellyLowder Myślę, że to zaakceptowana polityka . Głównym powodem, dla którego w Mathematica jest niezręcznie, jest to, że Mathematica nie ma rzeczywistego typu znaków, więc znaki są w końcu łańcuchami singletonowymi.
Martin Ender,
5

05AB1E , 18 bajtów

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

Wykorzystuje kodowanie 05AB1E . Wypróbuj online!

Adnan
źródło
Interesujące użycie filtra ... Próbowaliśmy zrobić transakcję typu „a bez b”, ale gdyby były dwa wystąpienia podłańcucha, otrzymalibyśmy fałszywe negatywy. Wydaje mi się, że nadmiernie komplikowaliśmy to teraz, gdy widzę ten lol. Noise, dam ci 100 nagród za 2 dni.
Magic Octopus Urn
ǝbył jednak naprawdę genialny.
Magic Octopus Urn
4

Python 3 , 97 bajtów

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)

Wypróbuj online!

Dennis
źródło
3

Python 2 , 116 bajtów

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)

Wypróbuj online!

Zaoszczędził kilka bajtów z pomocą Halvarda Hummela !

Pan Xcoder
źródło
117 bajtów
Halvard Hummel
@HalvardHummel Dzięki, również planowałem to zmienić, ale przez ostatnie 2 godziny nie miałem połączenia z Internetem.
Pan Xcoder,
2

Japt , 26 22 bajtów

¬£¬ËUjEY ꬩUtEY
c æ+0

Przetestuj online! Próbuję wymyślić, jak zamapować falsena coś fałszywego, a dowolny ciąg znaków na coś prawdziwego w jednym bajcie. Obecnie używam +0...

ETHprodukcje
źródło
2

Bash , 108 bajtów

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

Pobiera dane wejściowe jako argument wiersza polecenia.

Wypróbuj online! z cytatami wydrukowanymi wokół wyjścia, aby wyświetlić wiodące / końcowe spacje.

Justin Mariner
źródło
2

Prolog , 271 bajtów

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]|_]).

W pewnym momencie zdałem sobie sprawę, że będzie to ogromne według standardów golfa kodowego, więc zachowałem kilka dodatkowych pustych miejsc, aby zachować podobieństwo do wersji nie zaciemnionej. Ale nadal uważam, że może to być interesujące, ponieważ jest to inne podejście do problemu.

Wersja nie zaciemniona:

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
źródło
2

C ++, 254 248 246 bajtów

-6 bajtów dzięki Zacharýowi -2 bajty dzięki Toby Speightowi

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

Więc...

  • Użyłem Tjako definicji makra, ponieważ działając R""jako kolejny efekt na literał łańcuchowy (jest to prefiks używany do definiowania literałów łańcuchowych, zobacz cppreference, aby uzyskać więcej informacji), którego nie ma, kiedy to robięT""
  • Definicje preprocesora nie mogą znajdować się w tym samym wierszu i muszą zawierać co najmniej jedną spację między nazwą a treścią w definicji
  • 2 funkcje: p(std::string)sprawdzanie, czy łańcuch jest palindromem. Jeśli tak, zwraca, 1który rzutuje true, w przeciwnym razie zwraca 0, który rzutujefalse
  • Algorytm zapętla się podczas całego łańcucha, sprawdzając, czy jest to palindrom podczas kasowania za każdym razem 1 element, a następnie testuj kasowanie 2 elementów (zapętla się do maksymalnego rozmiaru łańcucha), od pierwszego indeksu do the last index - number of erased char. Jeśli stwierdzi, że wymazanie jakiejś części jest palindromem, wówczas powraca. Na przykład, podczas przechodzenia ciąg "aabcdbaa"jako parametr, jak ci dważne są odpowiedzi, ale ten kod powróci cponieważ jego usuwanie i testowanie czy to palindrom pochodzi przed sprawdzeniem czy kasowanie di testowania, czy to palindrom
  • Oto kod do przetestowania:

    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
źródło
Czy to zadziała w przypadku ostatniej linii? 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ý
Czy /2można to pominąć? Iteracja na całej długości po prostu powtórzy nasze testy, które powinny być nieszkodliwe. Możesz rozwinąć to, co rozumiesz przez „inny efekt” R""(tzn. Jest on analizowany jako dosłowny ciąg znaków).
Toby Speight
Zmodyfikowałem to i dodałem wynik jako własną odpowiedź .
Toby Speight
1

Galaretka , 33 bajty

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

Wypróbuj online!

HyperNeutrino
źródło
1

PHP 104 + 1 bajty

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

Uruchom jako potok z -nRlub spróbuj online .

Tytus
źródło
1

Haskell , 109 105 bajtów

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

Wypróbuj online!

EDYCJA: Dzięki @ H.PWiz za zdjęcie 4 bajtów! Muszę być lepszy z tymi monadami!

użytkownik 1472751
źródło
1

JavaScript, 90 bajtów

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

Wypróbuj online!


źródło
1

Perl 5, 72 +1 (-p) bajtów

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

Wypróbuj online

Nahuel Fouilleul
źródło
1

JavaScript (ES6), 91 78 bajtów

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

Dane wejściowe i wyjściowe są listami znaków.

Rekurencyjnie usuwa coraz większy wycinek z danych wejściowych, aż do znalezienia palindromu.

Skrawek:

Rick Hitchcock
źródło
1

TSQL (2016) 349B

Nie jest to najbardziej kompaktowe, ale proste rozwiązanie:

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
źródło
Możesz użyć @jako zmiennej dla kilku bajtów. W CTE możesz użyć where''=value)innego i nie musisz zwracać Cwyniku.
MickyT,
1

Łuska , 18 bajtów

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

Wypróbuj online!

Wyjaśnienie

◄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
źródło
1

Haskell , 98 94 81 80 bajtów

""#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

Wypróbuj online! Przykładowe użycie: ""#0 $ "aabaab"daje "b".

Edycja: -1 bajt dzięki Ørjan Johansen.

Laikoni
źródło
1
Można zastąpić ostatni ""przez t.
Ørjan Johansen
1

C ++, 189 186 176 167 bajtów

Zacząłem od odpowiedzi HatsuPointerKun , zmieniając test, aby po prostu porównać równość z odwróconym łańcuchem; potem zmieniłem sposób liczenia łańcuchów kandydujących. Następnie makra były używane tylko raz lub dwa razy, a wstawianie ich było krótsze.

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

Wyjaśnienie

Równoważny czytelny kod:

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

Wyliczenie kandydatów rozpoczyna się od zainicjowania ciągu znaków z wpominięciem pierwszych znaków, a następnie skopiowania kolejnych znaków z oryginału w celu przesunięcia odstępu. Na przykład za pomocą ciągu foobari w== 2:

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

Pierwszy przebieg (z w== 0) to brak operacji, więc pełny ciąg będzie rozpatrywany w kółko. W porządku - wydajność golfa przewyższa wydajność! Ostatnia iteracja tej pętli uzyska dostęp do indeksu jeden-do-końca; Wydaje mi się, że to mi się nie podoba z GCC, ale ściśle, to jest Niezdefiniowane Zachowanie.

Program testowy

Bezpośrednie odejście od odpowiedzi 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
źródło
0

REXX, 132 bajty

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
źródło
0

Rubin , 86 84 bajtów

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

Wypróbuj online!

  • Zaoszczędzono 2 bajty dzięki Cyoce
iamnotmaynard
źródło
Nie potrzebujesz nawiasów w pobliżu z=s.size-l+1.
Cyoce,
@Cyoce Dziękujemy. Trudno mi zapamiętać wszystkie priorytety operatorów.
iamnotmaynard
0

C (gcc) , 307 bajtów

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

Wypróbuj online!

R. Kap
źródło