Turunkan versi ke Palindrome

47

Diberikan string s, kembalikan substring bersebelahan terkecil yang dapat Anda hapus untuk membuat palindrome.


Contoh:

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

Saran kasus uji dari pengguna (jika Anda menemukan kasus tepi tidak terdaftar, silakan kirim komentar):

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

Aturan

  • Hanya karakter ASCII yang dapat dicetak yang akan muncul di input (tidak ada baris baru, buat tetap sederhana).
  • Tidak benar-benar aturan, tapi catatan <>, /\, (), []dan {}tidak palindrom.

Ini adalah , kemenangan byte-count terkecil.


+100 karunia telah diklaim oleh Adnan

Guci Gurita Ajaib
sumber
3
Kasing tesf:aabaab
Zgarb
14
Saya pikir itu akan membantu menjaga pertanyaan dapat diakses oleh lebih banyak pengunjung jika jargon ingroup seperti "CMC" dihindari (mencarinya, tampaknya berdiri untuk "obrolan mini tantangan", yang saya bayangkan berarti sebuah tantangan kecil yang diposting di ruang obrolan yang terkait dengan situs ini).
ShreevatsaR
Bukankah [[]]palindrome?
Carl
4
@Carl Ini mungkin terlihat seperti satu, tetapi ketika Anda membalik karakter, Anda mendapatkan ]][[. Anggap itu aabbhal yang sama, hanya karakter yang berbeda.
Conor O'Brien
1
" (akan diberikan 7/12) " ya?
Erik the Outgolfer

Jawaban:

8

Jelly , 16 byte

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

Cobalah online!

Bagaimana itu bekerja

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
sumber
10

J , 24 byte

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

Cobalah online!

Penjelasan

(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
mil
sumber
Mungkin Anda mungkin ingin memilih (;&quote f)&>sebagai kata kerja test harness?
Conor O'Brien
7

Bahasa Wolfram (Mathematica) , 53 51 byte

Hitungan byte mengasumsikan pengkodean CP-1252.

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

Cobalah online!

Menentukan operator unary ±(atau fungsi PlusMinus). Input dan output adalah daftar karakter. Test suite melakukan konversi dari dan ke string aktual untuk kenyamanan.

Martin Ender
sumber
Apakah Reversekemudian membandingkan yang terbalik dengan yang asli lebih pendek dari PalindromeQ? Saya tidak tahu Mathematica, jadi tidak tahu.
Magic Gurita Guci
Jawaban yang bagus, tetapi bukankah seharusnya satu akun untuk pemisahan string dan bergabung kembali bersama dalam hitungan karakter Anda? Characters@#/.{a___,Shortest@b___,c___}/;PalindromeQ[a<>c]:>b~~""&
Kelly Lowder
@MagicOctopusUrn Reverse[x={a,c}]==xlebih panjang dua byte. Saya tidak tahu apakah ada alternatif yang lebih pendek.
Martin Ender
@KellyLowder Daftar karakter adalah representasi string yang valid pada PPCG. Agak canggung di Mathematica, di mana Anda biasanya tidak menggunakan representasi itu, tetapi masih valid. Saya akan menggali postingan meta.
Martin Ender
1
@KellyLowder Saya pikir ini adalah kebijakan yang diterima . Alasan utama mengapa itu canggung dalam Mathematica adalah bahwa Mathematica tidak memiliki tipe karakter yang sebenarnya, sehingga karakter akhirnya menjadi string tunggal.
Martin Ender
5

Jelly , 20 byte

ŒḂ⁹Ƥ
çЀJN$Ẏi1ịẆẋ⁻Ṛ$

Cobalah online!

Erik the Outgolfer
sumber
5

05AB1E , 18 byte

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

Menggunakan penyandian 05AB1E . Cobalah online!

Adnan
sumber
Penggunaan filter yang menarik di sana ... Kami mencoba melakukan jenis transaksi "a tanpa b", tetapi jika ada dua contoh substring, kami akan mendapatkan negatif palsu. Rasanya kita terlalu rumit sekarang karena saya melihat lol ini. Noice, aku akan memberimu hadiah 100 dalam 2 hari.
Magic Gurita Guci
ǝmeskipun serius jenius.
Magic Gurita Guci
4

Python 3 , 97 byte

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)

Cobalah online!

Dennis
sumber
3

Python 2 , 116 byte

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)

Cobalah online!

Menyimpan beberapa byte dengan bantuan dari Halvard Hummel !

Tuan Xcoder
sumber
117 byte
Halvard Hummel
@HalvardHummel Terima kasih, saya berencana untuk mengubahnya juga tetapi tidak memiliki koneksi internet selama 2 jam terakhir.
Tn. Xcoder
2

Japt , 26 22 byte

¬£¬ËUjEY ꬩUtEY
c æ+0

Uji secara online! Mencoba mencari cara memetakan falsesesuatu yang palsu dan string apa pun ke sesuatu yang benar dalam satu byte. Saat ini saya menggunakan +0...

Produksi ETH
sumber
2

Bash , 108 byte

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

Mengambil input sebagai argumen baris perintah.

Cobalah online! dengan kutipan dicetak di sekitar output untuk melihat spasi terdepan / tertinggal.

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

Pada titik tertentu saya menyadari ini akan menjadi besar dengan standar kode-golf, jadi saya menyimpan beberapa ruang kosong tambahan untuk menjaga kemiripan dengan versi yang tidak dikaburkan. Tapi saya masih berpikir itu mungkin menarik karena ini pendekatan yang berbeda untuk masalah ini.

Versi yang tidak dikaburkan:

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
sumber
2

C ++, 254 248 246 byte

-6 byte terima kasih kepada Zacharý -2 byte terima kasih kepada 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"";}

Begitu...

  • Saya menggunakan Tdefinisi makro karena melakukan R""sebagai efek lain pada string literal (ini adalah awalan yang digunakan untuk mendefinisikan literal string mentah, lihat cppreference untuk informasi lebih lanjut) yang tidak ada ketika saya melakukanT""
  • Definisi preprosesor tidak boleh berada di baris yang sama, dan harus memiliki setidaknya satu ruang antara nama dan konten dalam definisi
  • 2 fungsi: p(std::string)untuk menguji apakah string adalah palindrome. Jika ya, ia mengembalikan 1yang dilemparkan ke true, yang lain mengembalikan 0, yang dilemparkan kefalse
  • Algoritma loop atas seluruh pengujian string jika itu adalah palindrome ketika menghapus setiap elemen 1 kali, kemudian uji menghapus 2 elemen (loop atas itu ke ukuran maksimum string), dari indeks pertama ke the last index - number of erased char. Jika ternyata menghapus sebagian adalah palindrom, maka, ia kembali. Misalnya, ketika meneruskan string "aabcdbaa"sebagai parameter, keduanya cdan dmerupakan jawaban yang valid, tetapi kode ini akan kembali ckarena menghapusnya dan menguji apakah palindrom datang sebelum menguji jika menghapus ddan menguji apakah itu palindrom
  • Berikut adalah kode untuk diuji:

    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
sumber
Apakah ini akan berhasil untuk baris terakhir? 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ý
Bisakah ini /2dihilangkan? Berulang-ulang sepanjang hanya akan mengulangi tes yang telah kami lakukan, yang seharusnya tidak berbahaya. Anda mungkin ingin memperluas apa yang Anda maksud dengan "efek lain" dari R""(yaitu itu diuraikan sebagai string string literal).
Toby Speight
Saya telah memodifikasi ini dan menambahkan hasilnya sebagai jawaban saya sendiri .
Toby Speight
1

Jelly , 33 byte

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

Cobalah online!

HyperNeutrino
sumber
1

PHP 104 +1 byte

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

Jalankan sebagai pipa dengan -nRatau coba online .

Titus
sumber
1

Haskell , 109 105 byte

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

Cobalah online!

EDIT: Terima kasih @ H.PWiz untuk melepas 4 byte! Saya perlu lebih baik dengan monad!

pengguna1472751
sumber
1

JavaScript, 90 byte

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

Cobalah online!


sumber
1

Perl 5, 72 +1 (-p) byte

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

Cobalah online

Nahuel Fouilleul
sumber
1

JavaScript (ES6), 91 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)

Input dan output adalah daftar karakter.

Secara rekursif menghilangkan irisan yang lebih besar dan lebih besar dari input sampai palindrom ditemukan.

Potongan:

Rick Hitchcock
sumber
1

TSQL (2016) 349B

Bukan solusi yang paling ringkas tetapi langsung:

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
sumber
Anda dapat menggunakan @sebagai variabel untuk beberapa byte. Dalam CTE Anda dapat menggunakan yang where''=value)lain dan Anda tidak perlu mengembalikan Chasilnya.
MickyT
1

Sekam , 18 byte

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

Cobalah online!

Penjelasan

◄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
sumber
1

Haskell , 98 94 81 80 byte

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

Cobalah online! Contoh penggunaan: ""#0 $ "aabaab"hasil "b".

Sunting: -1 byte berkat Ørjan Johansen.

Laikoni
sumber
1
Anda dapat mengganti yang terakhir ""dengan t.
Ørjan Johansen
1

C ++, 189 186 176 167 byte

Saya mulai dengan jawaban HatsuPointerKun , mengubah tes untuk hanya membandingkan kesetaraan dengan string terbalik; lalu saya mengubah cara kami menyebutkan string kandidat. Setelah ini, makro hanya digunakan satu atau dua kali masing-masing, dan lebih pendek untuk menyelaraskannya.

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

Penjelasan

Kode yang dapat dibaca setara:

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

Penghitungan calon dimulai dengan menginisialisasi string dengan wkarakter pertama dihilangkan, dan kemudian menyalin karakter berturut-turut dari aslinya untuk memindahkan celah. Misalnya, dengan string foobardan w== 2:

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

Pass pertama (dengan w== 0) adalah no-op, jadi string penuh akan dipertimbangkan berulang kali. Tidak apa-apa - efisiensi golf truf! Iterasi terakhir dari loop ini akan mengakses indeks one-past-the-end; Saya sepertinya lolos dengan GCC, tapi sebenarnya, itu Perilaku Tidak Terdefinisi.

Program uji

Pengangkatan langsung dari jawaban 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
sumber
0

REXX, 132 byte

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
sumber
0

Ruby , 86 84 byte

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

Cobalah online!

  • Disimpan 2 byte berkat Cyoce
iamnotmaynard
sumber
Anda tidak membutuhkan tanda kurung di sekitarnya z=s.size-l+1.
Cyoce
@Cyoce Terima kasih. Saya kesulitan mengingat semua prioritas operator.
iamnotmaynard
0

C (gcc) , 307 byte

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

Cobalah online!

R. Kap
sumber