pengantar

Penutupan palindromik dari string input adalah palindrom terpendek yang dapat dibangun dari string input di mana palindrom akhir dimulai dengan string input.

Untuk tantangan ini, kami akan mempertimbangkan penutupan palindromik dua arah sedemikian rupa

• Kiri Palindromic Penutupan dari string input adalah palindrom terpendek yang dimulai dengan string input.
• Penutupan Palindromik Kanan dari string input adalah palindrom terpendek yang mungkin berakhir dengan string input.
• Penutupan Palindromik Dua Arah dari string input adalah yang lebih pendek baik dari Penutupan Palindromik Kiri atau Kanan dari string input.

Tugas

Tugas Anda sederhana. Diberikan string (hanya terdiri dari ASCII yang dapat dicetak, garis baru, dan spasi putih), menghasilkan penutupan palindromik dua arah dari string itu. Dalam hal pengikatan, salah satu dari penutupan palindromik kiri atau kanan adalah output yang valid.

Anda dapat menulis sebuah program atau fungsi, mengambil input melalui STDIN (atau alternatif terdekat), argumen baris perintah atau argumen fungsi, dan mencetak hasilnya ke STDOUT (atau alternatif terdekat) atau mengembalikannya sebagai string.

Anda dapat mengasumsikan bahwa input tidak akan pernah menjadi string kosong.

Beberapa contoh:

<Input>   -> <Output>
"abcdef"  -> "abcdefedcba"  (or "fedcbabcdef")
"abcba"   -> "abcba"
"abcb"    -> "abcba"
"cbca"    -> "acbca"

Penghargaan Ide Awal diberikan kepada VisualMelon, ide terakhir dengan bantuan dari Martin dan Zgarb

Istilah penutupan palindromik, penutupan pallindromik kiri dan penutupan palindromik kanan pertama kali digunakan dan didefinisikan oleh makalah ini .

Pyth, 22 19

hfq_TTsm,+z_d+_dzyz

Cobalah online .

Penjelasan

Penutupan palindromik dua arah adalah baik dari bentuk AXatau XA, di mana Xadalah string input dan Amerupakan substring dari X. Saya sebenarnya harus menjadi substring yang berdekatan X, sebuah awalan untuk satu bentuk, akhiran untuk bentuk lainnya. Tapi saya tidak peduli dengan kegagalan ini. Substring (bersebelahan atau tidak) adalah semua yang saya butuhkan dalam Pyth.

                        Implicit: z = raw_input() // Read a string
                 yz     A list with all substrings (contiguous or not) of z
       m                For each of these substrings d, build
        ,                  a pair of two strings:
         +z_d              ( z + inveres(d) ,
             +_dz            inverse(d) + z )
      s                 Sum (put all created pairs into a list)
 fq_TT                  filter elements T, where inverse(T) == T (Palindrom)
h                          Take the first element

Edit

Versi lama memesan string setelah disaring berdasarkan panjangnya .olN.... Baru sadar, itu ymengembalikan panjang substring yang dipesan. Jadi palindrom ini sudah diurutkan.

Klip , 40

(sl`f[a=ava}+m[i+v+ixx}Rlxm[i+xvu0ix}Rlx

Contoh

Documents>java -jar Clip4.jar palindrome.clip
abcb
abcba

Penjelasan

(sl`                                        .- The shortest                     -.
    f[a=ava}                                .- palindrome                       -.
            +                               .- among the following two sets:    -.
             m[i      }Rlx                  .- For each number up to length(x)  -.
                +                           .- combine                          -.
                 v+ix                       .- the last i chars of x, reversed  -.
                     x                      .- and x.                           -.
                          m[i       }Rlx    .- For each number up to length(x)  -.
                             +              .- combine                          -.
                              x             .- x and                            -.
                               vu0ix        .- the first i chars of x, reversed.-.

CJam, 30 byte

Benar-benar berharap untuk melihat jawaban CJam sekarang .. Jadi begini: P

q:Q,{)QW%/(Q+Q@+s}%{,}${_W%=}=

Saya benar-benar benci {,}$blok itu di sana, tapi saya mendapatkan daftar kemungkinan palindrom karena algoritma generasi yang saya gunakan.

Penjelasan kode

q:Q,{            }%             "Read the input string, store in Q, take length and";
                                "run the code block that many times";
     )QW%                       "Increment the iteration index and Put reversed Q on stack";
         /                      "Split reversed Q into parts of incremented iteration index";
          (Q+                   "Take out the first part and prepend it to Q";
             Q@+s               "Take the rest of the parts and append them to Q";
                   {,}$         "At this point, we have all possible prepended and appended";
                                "sequences of the input string. Sort them by length";
                       {_W%=}=  "Take the first sequence which is a palindrome";

Cobalah online di sini

Python 2, 115 113 109 105 96 byte

f=lambda x:[x for x in sum([[x[:~i:-1]+x,x+x[i::-1]]for i in range(len(x))],[])if x==x[::-1]][0]

Semoga bisa bermain golf lebih jauh. Bit yang mungkin patut diperhatikan:

• menggunakan jumlah untuk dua daftar pemahaman dalam satu
• membangun istilah dalam urutan untuk menghindari kebutuhan akan min (disarankan oleh @Jakube)

Mathematica, 96 byte

Pasti ada cara yang lebih elegan dari ini ...

""<>#&@@SortBy[r=Reverse;#/.{b___,a__/;r@{a}=={a}}:>{b,r@{b,a}}&/@{r@#,#}&@Characters@#,Length]&

Ini mendefinisikan fungsi tanpa nama yang mengambil string dan mengembalikan hasilnya.

Ide dasarnya adalah untuk

• Pisahkan string menjadi Characters.
• Bentuk array dengan daftar ini dan kebalikannya.

• Gunakan pencocokan pola untuk menemukan palindromik yang tepat dari masing-masing:

  {b___,a__/;r@{a}=={a}}:>{b,r@{b,a}}
  

  Perhatikan bahwa ini sebenarnya tidak mengembalikan daftar datar. Misalnya untuk {a,b,c}Anda

  {a,b,{c,b,a}}
  

• Urutkan kedua hasil berdasarkan panjangnya.

• Pilih yang lebih pendek dan gabungkan kembali menjadi string ""<>#&@@.

Brachylog (2), 6 byte, tantangan tanggal bahasa

~{↔?a}

Cobalah online!

Seperti biasa untuk Brachylog, ini adalah fungsi, bukan program lengkap.

Penjelasan

~{↔?a}
~{   }   Find a value that produces {the input} upon doing the following:
  ↔        reversing it;
   ?       asserting that we still have the same value;
    a      and taking either a prefix, or a suffix.

Sejauh yang saya tahu (itu bukan bahasa saya, tapi sepertinya tidak mungkin), atidak ditambahkan ke Brachylog untuk tantangan ini, tetapi sangat berguna di sini. Kami menggunakan metode "mundur, dan menyatakan itu tidak berubah" untuk menyatakan bahwa nilai yang kami temukan adalah palindrome.

Adapun mengapa ini menghasilkan palindrome terpendek , urutan evaluasi Prolog (dan karenanya Brachylog) sangat dipengaruhi oleh hal pertama yang dievaluasi. Dalam hal ini, itu adalah perintah "terbalik", dan (seperti kebanyakan operasi daftar) itu menetapkan urutan evaluasi yang bertujuan untuk meminimalkan ukuran daftar yang dihasilkan. Karena itu sama dengan ukuran output, program dengan senang hati akhirnya meminimalkan hal yang benar secara kebetulan, artinya saya tidak perlu menambahkan petunjuk eksplisit.

Ruby, 76 + 2 = 78

Dengan flag-command-line -pl( lmungkin tidak diperlukan tergantung pada bagaimana Anda melakukan input), jalankan

$_=[[$_,r=$_.reverse]*"\0",r+"\0#$_"].min_by{|s|s.sub!(/(.*)\0\1/){$1}.size}

Diberikan string 'abaa', menghasilkan string 'cbca 0 acbc' dan 'acbc 0 cbca', di mana 0 adalah karakter yang tidak patut dengan kode ascii 0. Kemudian menghapus satu salinan dari string berulang yang diulang framing 0 yang ditemukan di masing-masing, 'A' di yang pertama dan 'cbc' di yang kedua, untuk mendapatkan dua penutupan. Ini kemudian menampilkan hasil terpendek.

Satu-satunya hal yang sangat aneh tentang kode golf adalah bahwa ia memperpendek string di tempat sambil menyortirnya, yang dapat kita hindari karena min_byhanya mengeksekusi blok sekali per elemen dibandingkan (keduanya karena itu adalah transformasi Schwartzian dan karena hanya ada dua elemen untuk dibandingkan).

Python 3, 107 byte

f=lambda a:[i for i in[a[:i:-1]*j+a+a[-1-i::-1]*(1-j)for i in range(len(a))for j in(0,1)]if i==i[::-1]][-1]

Untuk menguji:

>>> print("\n".join(map(f, ["abcdef", "abcba", "abcb", "cbca"])))
abcdefedcba
abcba
abcba
acbca

Haskell, 107 byte

import Data.List
r=reverse
f s=snd$minimum[(length x,x)|x<-map(s++)(tails$r s)++map(++s)(inits$r s),x==r x]

Uji:

*Main> mapM_ (putStrLn.f) ["abcdef", "abcba", "abcb", "cbca"]
abcdefedcba
abcba
abcba
acbca

J, 66 62 byte

3 :'>({~[:(i.>./)(#%~[-:|.)@>),(<@([,|.@{.~)"#:i.@#"1)y,:|.y'

Cukup mudah. Dua trik yang saya gunakan:

Penutupan palindromik kanan adalah penutupan palindromik kiri dari string yang terbalik.

Menemukan panjang string dengan panjang minimum dan palindromity dengan ekspresi min (is_palindrome / length).

   f=.3 :'>({~[:(i.>./)(#%~[-:|.)@>),(<@([,|.@{.~)"#:i.@#"1)y,:|.y'

   f 'lama'
lamal

Cobalah online di sini.