Palindromizing string

30

pengantar

Bagi mereka yang tidak tahu, palindrome adalah ketika string sama dengan string mundur (dengan pengecualian untuk interpungsi, spasi, dll.). Contoh palindrome adalah:

abcdcba

Jika Anda membalikkan ini, Anda akan berakhir dengan:

abcdcba

Itu sama saja. Karena itu, kami menyebutnya palindrome. Untuk melakukan palindromize, mari kita lihat contoh string:

adbcb

Ini bukan palindrome. Untuk membuat palindromisasi ini, kita perlu menggabungkan string terbalik ke string awal di sebelah kanan string awal , meninggalkan kedua versi utuh. Semakin pendek, semakin baik.

Hal pertama yang bisa kita coba adalah sebagai berikut:

adbcb
bcbda
^^ ^^

Tidak semua karakter cocok, jadi ini bukan posisi yang tepat untuk string yang terbalik. Kami melangkah satu langkah ke kanan:

adbcb
 bcbda
 ^^^^

Ini juga tidak cocok dengan semua karakter. Kami melangkah ke kanan:

adbcb
  bcbda

Kali ini, semua karakter cocok . Kita dapat menggabungkan kedua string agar tetap utuh . Hasil akhirnya adalah:

adbcbda

Ini adalah string palindromized .


Tugas

Diberikan string (dengan setidaknya satu karakter) yang hanya berisi huruf kecil (atau huruf besar, jika itu lebih baik), mengeluarkan string palindromized .


Uji kasus

Input     Output

abcb      abcba
hello     hellolleh
bonobo    bonobonob
radar     radar
hex       hexeh

Ini adalah , jadi pengiriman dengan jumlah byte paling sedikit menang!

Adnan
sumber
3
Terkait
Zgarb
6
Anda harus menentukan bahwa string terbalik harus digabungkan ke string asli dengan yang terbalik di sebelah kanan. Jika bisa melaju ke kiri, obonoboakan menjadi solusi yang lebih baik untuk test case.
Level River St
2
Terkait 2
Sp3000
2
@LevelRiverSt +1 hanya karena "obonobo" adalah kata yang luar biasa
Nathaniel
1
@Nathaniel Terima kasih tapi bono b o nobini adalah kalimat yang lengkap. Apa perbedaan antara Tuhan dan Bono? Tuhan tidak berkeliaran di sekitar Dublin dengan berpura-pura menjadi Bono ;-)
Level River St

Jawaban:

5

Jelly, 11 10 byte

ṫỤfU$Ḣœ^;U

Cobalah online!

Bagaimana itu bekerja

ṫỤfU$Ḣœ^;U  Main link. Argument: s (string)

 Ụ          Yield all indices of s, sorted by their corr. character values.
ṫ           Tail; for each index n, remove all characters before thr nth.
            This yields the list of suffixes of s, sorted by their first character,
            then (in descending order) by length.
    $       Combine the two links to the left into a chain:
   U        Upend; reverse all suffixes.
  f         Filter; only keep suffixes that are also reversed suffixes.
            This gives the list of all palindromic suffixes. Since all of them
            start with the same letter, they are sorted by length.
     Ḣ      Head; select the first, longest palindromic suffix.
      œ^    Multiset symmetric difference; chop the selected suffix from s.
         U  Upend; yield s, reversed.
        ;   Concatenate the results to the left and to the right.
Dennis
sumber
15

Pyth (melakukan b93a874), 11 byte

.VkI_IJ+zbB

Suite uji

Kode ini mengeksploitasi bug dalam versi Pyth saat ini, melakukan b93a874 . Bugnya adalah yang _IJ+zbdiurai seolah-olah itu q_J+zbJ+zb, yang setara dengan _I+zb+zb, ketika seharusnya (dengan maksud desain Pyth) diurai seperti q_J+zbJ, yang setara dengan _I+zb. Ini memungkinkan saya untuk menyimpan byte - setelah bug diperbaiki, kode yang benar adalah .VkI_IJ+zbJB. Saya akan menjelaskan kode itu sebagai gantinya.

Pada dasarnya, kode brute memaksa semua string yang mungkin sampai menemukan string terpendek yang dapat ditambahkan ke input untuk membentuk palindrome, dan menghasilkan string gabungan.

.VkI_IJ+zbJB
                z = input()
.Vk             For b in possible strings ordered by length,
       +zb      Add z and b,
      J         Store it in J,
    _I          Check if the result is a palindrome,
   I            If so,
          J     Print J (This line doesn't actually exist, gets added by the bug.
          B     Break.
isaacg
sumber
Bagaimana Anda membuat kode seperti itu? Ini hampir tidak dapat dibaca dan sama sekali tidak dapat dimengerti oleh seseorang yang tidak mengenal Pyth. Apa tujuan dari bahasa seperti itu.
anukul
5
@momo Tujuan dari bahasa ini adalah untuk menulis kode pendek, untuk kesenangan. Ini kegiatan rekreasi. Saya dapat menulisnya karena saya memiliki banyak latihan, dan karena saya menemukan bahasa. Saya tahu itu tidak bisa dimengerti oleh seseorang yang tidak tahu bahasa, itu sebabnya saya memasukkan penjelasannya.
isaacg
13

Python, 46 byte

f=lambda s:s*(s==s[::-1])or s[0]+f(s[1:])+s[0]

Jika string adalah palindrom, kembalikan. Jika tidak, masukkan huruf pertama di sekitar hasil rekursif untuk sisa string.

Contoh pemecahan:

f(bonobo)
b  f(onobo) b
b o f(nobo) o b 
b o n f(obo) n o b
b o n obo n o b
Tidak
sumber
Saya pikir Anda dapat menyimpan byte jika Anda menggunakan kondisi yang berlawanan ( s!=s[::-1])
aditsu
@aditsu Itu berfungsi tetapi menggunakan multiply masih lebih pendek.
xnor
9

Haskell, 36 byte

f s|s==reverse s=s|h:t<-s=h:f t++[h]

Lebih mudah dibaca:

f s
 |s==reverse s = s
 |(h:t)<-s     = h:(f t)++[h]

Jika string adalah palindrom, kembalikan. Kalau tidak, sandarkan huruf pertama di sekitar hasil rekursif untuk ekor string.

Tali sdipecah menjadi h:tdi penjaga kedua, menghindarkan pengisi 1>0untuk kasus ini. Ini lebih pendek daripada melakukan s@(h:t)input.

Tidak
sumber
5

Pyth - 16 12 byte

4 byte disimpan berkat @FryAmTheEggman.

FGITW, banyak bermain golf mungkin.

h_I#+R_Q+k._

Test Suite .

Maltysen
sumber
5

Brachylog , 16 6 5 byte (Tidak bersaing)

:Ac.r

Cobalah online!

Ketika saya memposting jawaban awal saya, itu masih pada implementasi lama di Jawa Karena saya telah memprogram ulang semuanya dalam Prolog, sekarang ia berfungsi sebagaimana mestinya.

Penjelasan

(?):Ac.        Output is the concatenation of Input with another unknown string A
      .r(.)    The reverse of the Output is the Output

Backpropagation membuatnya sehingga nilai valid pertama yang Aakan ditemukan akan menjadi yang terpendek yang dapat Anda gabungkan ke Input untuk menjadikannya palindrome.

Solusi alternatif, 5 byte

~@[.r

Ini kira-kira sama dengan jawaban di atas, kecuali bahwa alih-alih menyatakan "Output adalah gabungan dari Input dengan string A", kami menyatakan bahwa "Output adalah string yang Inputnya merupakan awalan dari Output".

Fatalisasi
sumber
4

JavaScript (ES6), 92 byte

(s,a=[...s],r=a.reverse().join``)=>s.slice(0,a.findIndex((_,i)=>r.startsWith(s.slice(i))))+r

Menghitung dan memotong tumpang tindih antara string asli dan pembalikannya.

Neil
sumber
4

Retina, 29 25

$
¶$_
O^#r`.\G
(.+)¶\1
$1

Cobalah online!

Terima kasih banyak untuk Martin selama 11 byte yang disimpan!

Ini hanya membuat salinan string yang terbalik dan membuat mereka menjadi satu. Satu-satunya bagian yang sangat mewah dari ini adalah metode pembalikan:, O^#r`.\Gyang dilakukan dengan menggunakan mode pengurutan. Kami mengurutkan huruf-huruf dari string kedua (yang bukan baris baru dan berturut-turut dari akhir string, terima kasih kepada \G) dengan nilai numeriknya, yang, karena tidak ada angka, adalah 0. Kemudian kami membalikkan urutan hasil sortir stabil ini dengan ^opsi. Semua kredit untuk penggunaan mewah \Gmilik Martin :)

FryAmTheEggman
sumber
3

CJam, 18

q__,,{1$>_W%=}#<W%

Cobalah online

Penjelasan:

q         read the input
__        make 2 copies
,,        convert the last one to a range [0 … length-1]
{…}#      find the first index that satisfies the condition:
  1$>     copy the input string and take the suffix from that position
  _W%=    duplicate, reverse and compare (palindrome check)
<         take the prefix before the found index
W%        reverse that prefix
          at the end, the stack contains the input string and that reversed prefix
aditsu
sumber
3

Lua, 89 88 Bytes

Saya mengalahkan Javascript! \ o / Disimpan 1 byte berkat @LeakyNun ^^

Ini adalah program lengkap, mengambil inputnya sebagai argumen baris perintah.

i=1s=...r=s:reverse()while s:sub(i)~=r:sub(0,#r-i+1)do i=i+1 end print(s..r:sub(#r-i+2))

ungolfed

i=1                             -- initialise i at 1 as string are 1-indexed in lua
s=...                           -- use s as a shorthand for the first argument
r=s:reverse()                   -- reverse the string s and save it into r
while(s:sub(i)~=r:sub(0,#r-i+1))-- iterate while the last i characters of s
do                              -- aren't equals to the first i characters of r
  i=i+1                         -- increment the number of character to skip
end
print(s..r:sub(#r-i+2))         -- output the merged string
Katenkyo
sumber
Saya percaya tanda kurung dekat whiledapat dihapus?
Leaky Nun
@LeakyNun yakin mereka bisa ^^
Katenkyo
Tidak bisa melakukan i=i+1end?
Erik the Outgolfer
1
@ EʀɪᴋᴛʜᴇGᴏʟғᴇʀ Sedihnya, saya tidak bisa. Itu akan mencoba untuk mengevaluasi 1endsebagai angka heksadesimal. Secara umum, Anda tidak dapat menggunakan [abcdef]langsung setelah nomor tanpa dianggap sebagai heksadesimal. Ada satu lagi pengecualian 0x.
Katenkyo
3

Prolog, 43 byte

a(S):-append(S,_,U),reverse(U,U),writef(U).

Ini mengharapkan string kode sebagai input, misalnya pada SWI-Prolog 7: a(`hello`).

Penjelasan

Ini pada dasarnya adalah port dari jawaban Brachylog saya.

a(S) :-               % S is the input string as a list of codes
    append(S,_,U),    % U is a list of codes resulting in appending an unknown list to S
    reverse(U,U),     % The reverse of U is U
    writef(U).        % Write U to STDOUT as a list of codes
Fatalisasi
sumber
3

Oktaf, 78 75 byte

Disimpan 3 byte berkat Eʀɪᴋ ᴛʜᴇ Gᴏʟғᴇʀ!

function p=L(s)d=0;while~all(diag(s==rot90(s),d++))p=[s fliplr(s(1:d))];end

ideone masih gagal untuk fungsi-fungsi yang disebutkan, tetapi di sini ada uji coba kode sebagai sebuah program.

gelas kimia
sumber
2

Perl, 37 byte

Berdasarkan jawaban xnor.

Termasuk +2 untuk -lp

Jalankan dengan input pada STDIN, mis

palindromize.pl <<< bonobo

palindromize.pl:

#!/usr/bin/perl -lp
s/.//,do$0,$_=$&.$_.$&if$_!~reverse
Ton Hospel
sumber
1

05AB1E , 18 byte

Kode:

©gF¹ðN×®«ðñD®åi,q

Menggunakan pengodean CP-1252 . Cobalah online!

Adnan
sumber
1

J, 20 byte

,[|.@{.~(-:|.)\.i.1:

Ini adalah kata kerja monadik. Coba di sini. Pemakaian:

   f =: ,[|.@{.~(-:|.)\.i.1:
   f 'race'
'racecar'

Penjelasan

Saya menggunakan fakta bahwa palindromisasi S adalah S + reverse (P) , di mana P adalah awalan terpendek dari S yang penghapusannya menghasilkan palindrome. Dalam J, sedikit kikuk untuk melakukan pencarian elemen pertama dari array yang memenuhi predikat; karenanya pengindeksan.

,[|.@{.~(-:|.)\.i.1:  Input is S.
        (    )\.      Map over suffixes of S:
         -:             Does it match
           |.           its reversal? This gives 1 for palindromic suffixes and 0 for others.
                i.1:  Take the first (0-based) index of 1 in that array.
 [   {.~              Take a prefix of S of that length: this is P.
  |.@                 Reverse of P.
,                     Concatenate it to S.
Zgarb
sumber
1

Haskell, 68 byte

import Data.List
f i=[i++r x|x<-inits i,i++r x==x++r i]!!0
r=reverse

Contoh penggunaan: f "abcb"-> "abcba".

Cari melalui initsinput i(misalnya inits "abcb"-> ["", "a", "ab", "abc", "abcb"]) sampai Anda menemukan satu di mana itu terbalik ditambahkan untuk imembangun palindrome.

nimi
sumber
Tidak r=reverseharus pergi sebelum f i=...?
Erik the Outgolfer
@ EʀɪᴋᴛʜᴇGᴏʟғᴇʀ: Tidak, Anda dapat menggunakan pesanan apa pun.
nimi
Saya berhasil dalam 46 byte. Saya yakin itu bisa dilakukan lebih baik lagi.
theonlygusti
@theonlygusti: lihat jawaban xnor .
nimi
1

MATL , 17 16 byte

Terinspirasi secara longgar dalam jawaban CJam @ aditsu .

`xGt@q:)PhttP=A~

Cobalah online!

Penjelasan

`        % Do...while loop
  x      %   Delete top of stack, which contains a not useful result from the
         %   iteration. Takes input implicitly on first iteration, and deletes it
  G      %   Push input
  t      %   Duplicate
  @q:    %   Generate range [1,...,n-1], where n is iteration index. On the  first
         %   iteration this is an empty array
  )      %   Use that as index into copy of input string: get its first n elements
  Ph     %   Flip and concatenate to input string
  t      %   Duplicate. This will be the final result, or will be deleted at the
         %   beginning of next iteration
  tP     %   Duplicate and flip
  =A~    %   Compare element-wise. Is there some element different? If so, the
         %   result is true. This is the loop condition, so go there will be a 
         %   new iteration. Else the loop is exited with the stack containing
         %   the contatenated string
         % End loop implicitly
         % Display stack contents implicitly
Luis Mendo
sumber
1

Ruby, 44 byte

Jawaban ini didasarkan pada solusi Python dan Haskell xnor .

f=->s{s.reverse==s ?s:s[0]+f[s[1..-1]]+s[0]}
Sherlock9
sumber
Tidak bisa melakukan ==s?s:?
Erik the Outgolfer
@ EʀɪᴋᴛʜᴇGᴏʟғᴇʀ irb cocok jika saya mencobanya. Pasti ada hubungannya dengan bagaimana ia diurai ?antara ?:untuk ternary dan ?x == 'x'substitusi yang digunakan sejak Ruby 1.9
Sherlock9
1

Oracle SQL 11.2, 195 byte

SELECT MIN(p)KEEP(DENSE_RANK FIRST ORDER BY LENGTH(p))FROM(SELECT:1||SUBSTR(REVERSE(:1),LEVEL+1)p FROM DUAL WHERE SUBSTR(:1,-LEVEL,LEVEL)=SUBSTR(REVERSE(:1),1,LEVEL)CONNECT BY LEVEL<=LENGTH(:1));

Tidak bermain golf

SELECT MIN(p)KEEP(DENSE_RANK FIRST ORDER BY LENGTH(p))
FROM (
       SELECT :1||SUBSTR(REVERSE(:1),LEVEL+1)p 
       FROM   DUAL 
       WHERE  SUBSTR(:1,-LEVEL,LEVEL)=SUBSTR(REVERSE(:1),1,LEVEL)
       CONNECT BY LEVEL<=LENGTH(:1)
     );
Jeto
sumber
1

Serius, 34 byte

╩╜lur`╜╨"Σ╜+;;R=*"£M`MΣ;░p╜;;R=I.

Karakter terakhir adalah ruang tanpa putus (ASCII 127 atau 0x7F).

Cobalah online!

Penjelasan:

╩╜lur`╜╨"Σ╜+;;R=*"£M`MΣ;░p╜;;R=I.<NBSP>
╩                                        push inputs to registers (call the value in register 0 "s" for this explanation)
 ╜lur                                    push range(0, len(s)+1)
     `              `M                   map (for i in a):
      ╜╨                                   push all i-length permutations of s
        "        "£M                       map (for k in perms):
         Σ╜+                                 push s+''.join(k) (call it p)
            ;;R=                             palindrome test
                *                            multiply (push p if palindrome else '')
                      Σ                  summation (flatten lists into list of strings)
                       ;░                filter truthy values
                         p               pop first element (guaranteed to be shortest, call it x)
                          ╜;;R=I         pop x, push s if s is palindromic else x
                                .<NBSP>  print and quit
Mego
sumber
1

C #, 202 byte

Saya mencoba.

class P{static void Main(string[]a){string s=Console.ReadLine(),o=new string(s.Reverse().ToArray()),w=s;for(int i=0;w!=new string(w.Reverse().ToArray());){w=s.Substring(0,i++)+o;}Console.WriteLine(w);}}

Tidak Disatukan:

class P
{
    static void Main(string[] a)
    {
        string s = Console.ReadLine(), o = new string(s.Reverse().ToArray()), w = s;
        for(int i = 0; w!=new string(w.Reverse().ToArray());)
        {
            w = s.Substring(0, i++) + o;
        }
        Console.WriteLine(w);
        Console.ReadKey();
    }

}

Adakah yang bisa memberi saya ide untuk mengelompokkan dua panggilan .Reverse (). ToArray ()? Metode terpisah lebih banyak byte.

SkyPharaoh
sumber
0

QBIC , 41 byte

;_FA|C=A{a=a+1~C=_fC||_XC\C=A+right$(B,a)

Penjelasan:

;_FA|    Read A$ from the cmd line, then flip it to create B$
C=A      Set C$ to be A$
{        Start an infinite DO-loop
a=a+1    Increment a (not to be confused with A$...)
~C=_fC|  If C$ is equal to its own reversed version
|_XC     THEN end, printing C$
\C=A+    ELSE, C$ is reset to the base A$, with
right$(B the right part of its own reversal
,a)      for length a (remember, we increment this each iteration
         DO and IF implicitly closed at EOF
steenbergh
sumber
0

Haskell, 46 byte

f l|l==reverse l=l|(h:t)<-l=l!!0:(f$tail l)++[l!!0]

Saya ingin tahu apakah ada cara untuk menghapus tanda kurung di (f$tail l)++[l!!0]...

theonlygusti
sumber