Di mana saya harus meletakkan cermin saya?

30

Ini adalah cermin: |. Saya baru tahu bahwa Anda dapat menempelkan cermin di tengah-tengah tali jika tali itu dapat dicerminkan pada dirinya sendiri! Misalnya, string abccba. Jika Anda memotongnya menjadi dua bagian adalah gambar cermin satu sama lain:

abc  <-->  cba

Jadi, kita bisa menempelkan cermin di tengah-tengah string, dan string baru kita adalah abc|cba. Terkadang, hanya sebagian dari string yang dapat dicerminkan dengan sendirinya. Misalnya, string "mirror". Dua r dicerminkan, tetapi sisa string tidak. Tidak apa-apa, kami hanya akan menghapus bagian-bagian dari string yang tidak saling mencerminkan, dan kami mendapatkan string berikut:

r|r

Beberapa string dapat dicerminkan di banyak tempat. Misalnya, "Hello World, xyzzyx". Saya suka memiliki banyak teks yang terpantul di cermin saya, jadi Anda perlu menemukan tempat terbaik untuk meletakkan cermin saya. Dalam hal ini, Anda harus mengeluarkan string cermin yang lebih panjang dan seperti contoh terakhir kami, hapus yang lainnya. String ini menjadi:

xyz|zyx

Beberapa string terlihat seperti mereka dapat dicerminkan, tetapi sebenarnya tidak bisa. Jika string tidak dapat dicerminkan di mana pun, Anda seharusnya tidak menghasilkan apa-apa.

Tantangan:

Diberikan string yang hanya berisi ascii yang dapat dicetak, temukan tempat terbaik untuk meletakkan cermin saya. Dengan kata lain,

Temukan substring palindromic panjang rata-rata terbesar, lalu output dengan karakter pipa '|' di tengah-tengahnya.

Panjang input akan 1-50 karakter.

Anda dapat mengasumsikan bahwa input tidak akan mengandung mirror |atau baris baru. Selain itu, semua karakter cetak-ascii adalah permainan yang adil. Jika substring cermin terpanjang diikat di antara dua substring, Anda dapat memilih mana yang akan diproduksi. Misalnya, untuk string "abba ollo", Anda harus menampilkan "ab | ba" atau "ol | lo", tetapi tidak masalah yang mana yang Anda output. String peka huruf besar-kecil, misalnya "ABba" tidak boleh menampilkan "AB | ba", itu harus menampilkan string kosong.

Sampel IO:

"Hello World"     --> "l|l"
"Programming Puzzles and Code-Golf"     --> Either "m|m" or "z|z"
"abcba"           --> ""
"Hulluh"          --> "ul|lu"
"abcdefggfedcba"  --> "abcdefg|gfedcba"
"abcdefggfabc"    --> "fg|gf"
"AbbA"            --> "Ab|bA"
"This input is a lot like the last one, but with more characters that don't change the output. AbbA" --> "Ab|bA"

Seperti biasa, ini adalah kode-golf, sehingga celah standar berlaku, dan jawaban terpendek dalam byte menang!

DJMcMayhem
sumber
Apakah ada batasan pada panjang input?
Mego
@Mego Selama algoritma Anda secara teoritis bekerja pada input apa pun, saya tidak peduli berapa lama / berapa banyak memori yang dibutuhkan.
DJMcMayhem
Saya bertanya karena mesin vanilla regex hanya mampu mencocokkan palindrom dengan panjang hingga nilai tertentu, terbatas (berlawanan dengan palindrom panjang sewenang-wenang), dan kemungkinan solusi berbasis regex akan tergantung pada apakah ada atau tidak terikat pada panjang input.
Mego
@Mego Ah, itu masuk akal. Katakanlah inputnya bisa hingga 50 karakter. Bagaimana itu terdengar?
DJMcMayhem

Jawaban:

9

Pyth - 19 17 15 13 byte

Terima kasih kepada @FryAmTheEggman karena telah menyelamatkan saya dua byte.

ARRGH kasus khusus tanpa jawaban. Selesaikan itu!

e_I#jL\|cL2.:

Test Suite .

e                Last element in list, this works out to longest one
  _I             Invariance under reverse, this detect palindrome
   #             Filter
   jL            Map join
    \|           By "|"
    cL2          Map chop in two pieces
     .:Q)        Substrings. Implicit Q). ) makes it do all substrings.
Maltysen
sumber
2
Tidaaaak! Ninja'd to the pyth answer; _;
Downgoat
Penjelasannya tolong? : 3
Downgoat
@Downgoat ia mengambil semua substring dan memotong menjadi dua, bergabung dengan masing-masing pasangan dengan |, filter berdasarkan simetri, tambahkan itu ke [k] dan dapatkan elemen terakhir (yang merupakan yang terpanjang)
busukxuan
@Downgoat selesai.
Maltysen
2
:Q)= Bignose
gcampbell
8

05AB1E , 19 17 14 byte

Kode:

Œévy2ä'|ý©ÂQi®

Penjelasan:

Œ                # Get all substrings of the input
 é               # Sort by length (shortest first)
  vy             # For each element...
    2ä           # Split into two pieces
      '|ý        # Join by "|"
         ©       # Copy this into the register
          Â      # Bifurcate, pushing a and reversed a
           Q     # Check if it's a palindrome
            i®   # If so, push that string again
                 # Implicit, the top element is outputted

Menggunakan pengkodean CP-1252 . Cobalah online! .

Adnan
sumber
5

Python 2, 102 97 byte

def f(s):h=len(s)/2;r=s[:h]+'|'+s[h:];return s and max(r*(r==r[::-1]),f(s[1:]),f(s[:-1]),key=len)

Agak lambat dan tidak efisien ... Verifikasi kasus uji yang lebih kecil di Ideone .

Dennis
sumber
4

JavaScript, 100 99 byte

s=>eval('for(O=i=0;s[i++];O=O[j+j]?O:o)for(o="|",j=0;(S=s[i-1-j])&&S==s[i+j++];o=S+o+S);O[1]?O:""')

atau

s=>eval('for(O="",i=0;s[i++];O=O[j+j]||j<2?O:o)for(o="|",j=0;(S=s[i-1-j])&&S==s[i+j++];o=S+o+S);O')
Jrich
sumber
Hanya ingin tahu, untuk apa eval?
gcampbell
@gcampbell evaluntuk menghindarireturn
edc65
Tidak bisakah Anda menggunakan operator koma untuk menghindari kembali?
MayorMonty
@SpeedyNinja nggak. forbukan ekspresi, jadi itu biasanya membutuhkan kawat gigi dan areturn
jrich
3

Lua, 133 byte

s=...for i=#s,1,-1 do for j=1,#s-i do m=j+i/2-i%2/2t=s:sub(j,m).."|"..s:sub(m+1,i+j)if t==t.reverse(t)then print(t)return end end end

Verifikasi semua testcases di Ideone.com .

Biarawati Bocor
sumber
1
Gunakan t==t:reverse()untuk menyimpan byte :)
Katenkyo
2

Retina , 66 byte

Hitungan byte mengasumsikan penyandian ISO 8859-1.

M!&`(.)+(?<-1>\1)+(?(1)¶)
O$#`.+
$.&
A-2`
^(.)+?(?=(?<-1>.)+$)
$&|

Cobalah online! (Baris pertama memungkinkan pengujian beberapa test case yang dipisahkan linefeed sekaligus.)

Hmmm, lebih lama dari yang saya inginkan ...

Martin Ender
sumber
2

JavaScript (ES6), 91

s=>[...s].map((d,i)=>{for(a='|',j=0;d=s[i-j],d&&d==s[i-~j];r=r[j+++j]?r:a)a=d+a+d},r='')&&r

Kurang golf

f=s=>
  [...s].map(
    (d,i) => {
    for(a='|', j=0; d=s[i-j], d&&d==s[i-~j]; r = r[j++ +j]? r : a)
      a = d+a+d
    }, r=''
  ) && r

Uji

F=
s=>[...s].map((d,i)=>{for(a='|',j=0;d=s[i-j],d&&d==s[i-~j];r=r[j+++j]?r:a)a=d+a+d},r='')&&r

;[["Hello World", "l|l"]
,["Programming Puzzles and Code-Golf", "m|m"]
,["abcba", ""]
,["Hulluh", "ul|lu"]
,["abcdefggfedcba", "abcdefg|gfedcba"]
,["abcdefggfabc", "fg|gf"]
,["AbbA", "Ab|bA"]
,["This input is a lot like the last one, but with more characters that don't change the output. AbbA", "Ab|bA"]]
.forEach(t=>{
  var i=t[0],k=t[1],r=F(i)
  console.log(k==r?'OK ':'KO ',i+' -> '+r,k!=r?'(check '+k+')':'')
})  

edc65
sumber
2

Perl 5, 105 100 98 + 1 = 106 101 99 byte

/(?=((.)(?1)?\2)(?{[push@_,$1})(?!))/;($_)=sort{length$b<=>length$a}@_;substr($_,length>>1,0)='|'if$_

Saya hanya ingin memberikan regex rekursif. Membutuhkan -popsi. Sunting: Disimpan (dicoret 4) 7 byte berkat @ msh210. (Bita yang hilang disebabkan oleh penghematan yang digantikan oleh penghematan terbaru @ msh210.)

Neil
sumber
Saya belum menguji semua ini, tapi mungkin ini bisa disingkat berbagai cara, termasuk: (1) @_=(@_,$1)bisa push@_,$1. (2) Abaikan baris baru dan final ;. (3) Saya menduga ada kondisi semacam pendek Anda dapat menggunakan (jika tidak ada yang lain maka setidaknya --- mungkin --- pengganti -untuk <=>)
msh210
@ msh210 Terima kasih untuk dua poin pertama tapi saya sudah mencoba -dan tidak berhasil (mungkin perlu parens untuk diutamakan yang mengalahkan penghematan).
Neil
Coba y...c>>1atau y...c/2bukan length>>1. (Belum diuji.)
msh210
@ msh210 Saya jelas harus membaca tips untuk bermain golf di Perl pertama ...
Neil
Saya menduga sepasang parens terakhir Anda bisa pergi juga.
msh210
2

Python 2, 91 byte

f=lambda s,p='':s and max((''<p<=s<p+'\x7f')*(p[::-1]+'|'+p),f(s[1:]),f(s[1:],s[0]+p),key=len)

Ganti \x7fdengan karakter aktual DEL, yaitu ASCII 127 (kredit ke Dennis).

Ini mengikuti strategi yang mirip dengan jawaban Dennis tentang penggunaan maxdan percabangan rekursif untuk menemukan interval palindrom terpanjang. Tetapi, sebaliknya, ia menemukan bagian kiri, memeriksa bahwa bagian kanan yang sesuai dicerminkan datang setelahnya dengan permulaan buatan sendiri .

Fungsi menebak apakah karakter pertama di bagian kiri cermin. Jika tidak, itu hanya menjatuhkannya dan berulang pada sisanya. Jika ya, itu ditambahkan ke tumpukan pkarakter yang terbalik. Jika string pernah dimulai dengan tumpukan, string cermin dihasilkan dan dianggap sebagai cermin terpanjang yang mungkin. Untuk menghindarinya |sebagai output, hanya tumpukan yang tidak kosong yang dipertimbangkan.

Tidak
sumber
2

Jelly , 17 byte

ẆŒḂÐfṪœs2j”|µẋLḂ$

Cobalah online!

Dilakukan dengan bantuan dari Mr. Xcoder dan DJMcMayhem dalam obrolan

Bagaimana itu bekerja

ẆŒḂÐfṪœs2j”|µẋLḂ$ - Main link. Argument s  e.g.    ; 'AbbA'

Ẇ                 - All contiguous sublists
   Ðf             - Keep elements that are...
 ŒḂ               -  Palindromic                   ; [['A'], ['b'], ['b'], ['A'], ['bb'], ['AbbA']]
     Ṫ            - Final element                  ; 'AbbA'
      œs2         - Split into 2 chunks            ; ['Ab', 'bA']
         j”|      - Join with "|"                  ; 'Ab|bA'
            µ     - New link with ^ as argument
              LḂ$ - Is the length odd?             ; 1
             ẋ    - Repeat the string ^ many times ; 'Ab|bA'
caird coinheringaahing
sumber
1

Haskell, 126 111 byte

(!)=drop
f s|n<-length s=last$"":[a++'|':b|k<-[1..n],t<-map(!s)[1..n-k],let[a,b]=take k<$>[t,k!t],a==reverse b]
Lynn
sumber
1

TSQL 227 223 byte

Saya hardcoded panjangnya hingga maks 99 byte, ini disimpan byte tetapi membuatnya lebih lambat. Ini masih memiliki kinerja yang baik.

Golf:

DECLARE @t varchar(99)='AbccbA'

,@z char(99)='',@a INT=0,@ INT=0WHILE @a<LEN(@t)SELECT
@z=IIF(LEN(x)>LEN(@z)/2and @t LIKE'%'+x+REVERSE(x)+'%'COLLATE
Thai_bin,x+'|'+REVERSE(x),@z),@=IIF(@=50,1,@+1),@a+=IIF(@=1,1,0)FROM(SELECT
SUBSTRING(@t,@a,@)x)x PRINT @z

Tidak Disatukan:

DECLARE @t varchar(99)='AbccbA'

,@z char(99)='',
@a INT=0,
@ INT=0
WHILE @a<LEN(@t)
  SELECT
    @z=IIF(LEN(x)>LEN(@z)/2and @t LIKE'%'+x+REVERSE(x)+'%'COLLATE Thai_bin,x+'|'
       +REVERSE(x),@z),
    @=IIF(@=99,1,@+1),
    @a+=IIF(@=1,1,0)
  FROM
    (SELECT SUBSTRING(@t,@a,@)x)x

PRINT @z

Biola

t-clausen.dk
sumber
1
Anda dapat mengurangi 2 byte jika Anda membatasi hingga 99 sebagai contoh terakhir hanya 99 karakter
Alex Carlsen
1
@VisualBean terima kasih, mengubah skrip untuk hanya mengizinkan 99 karakter, juga mengubah susunan dari Thai_CS_AS ke thai_bin
t-clausen.dk
0

Python 2, 149 byte

R,L,s=range,len,input()
t=max([s[i:j/2+i/2]for i in R(L(s))for j in R(L(s)+1)if s[i:j]==s[i:j][::-1]and(j-i)%2<1],key=L)
print t+'|'*(L(t)>0)+t[::-1]

Cobalah online

Program ini menemukan bagian pertama dari substring palindromik terbesar dengan panjang genap, dan mencetak string itu, diikuti oleh |, diikuti oleh string yang dibalik. Jika tidak ada string yang cocok, takan menjadi string kosong, dan '|'*(L(t)>0)akan mengevaluasi ke string kosong.

Mego
sumber
0

Java 8, 294 283 232 byte

s->{int l=s.length(),i=0,j,z,y=0;String a,b="";for(;i<l;i++)for(j=0;j<=l-i;)if((a=s.substring(i,i+j++)).equals(new StringBuffer(a).reverse()+"")&(z=a.length())%2<1&z>y){y=z;b=a;}return y>0?b.substring(0,y/=2)+"|"+b.substring(y):"";}

Penjelasan:

Coba di sini.

s->{                               // Method with String as both parameter and return-type
  int l=s.length(),                //  Length of the input-String
      i=0,j,                       //  Index-integers
      z,y=0;                       //  Temp-integers
  String a,b="";                   //  Temp-Strings
  for(;i<l;i++)                    //  Loop (1) from 0 to `l` (exclusive)
    for(j=0;j<=l-i;                //   Inner loop (2) from 0 to `l-i` (inclusive)
      if((a=s.substring(i,i+j++))  //    Set the current substring to `a`
          .equals(new StringBuffer(a).reverse()+"")
                                   //    If `a` is a palindrome
         &(z=a.length())%2<1       //    And the length of `a` is even
         &z>y){                    //    And the length of `a` is larger than `y`
        y=z;                       //     Change `y` to `z`
        b=a;}                      //     Change `b` to `a`
                                   //   End of inner loop (2) (implicit / single-line body)
                                   //  End of loop (1) (implicit / single-line body)
  return y>0?                      //  If the result-length is not 0:
    b.substring(0,y/=2)+"|"+b.substring(y)
                                   //   Return the result
   :                               //  Else:
    "";                            //   Return an empty String
}                                  // End of method
Kevin Cruijssen
sumber