Teka-teki Semi-palindrome

23

Palindrome adalah kata yang kebalikannya sendiri.

Sekarang ada beberapa kata yang mungkin terlihat seperti palindrom tetapi tidak. Misalnya menganggap kata sheesh, sheeshbukan palindrom karena kebalikannya hseehsyang berbeda, namun jika kita anggap shsebagai satu huruf, maka kebalikannya sheesh. Kata semacam ini akan kita sebut semi palindrome.

Secara khusus sebuah kata adalah semi-palindrome jika kita dapat membagi kata menjadi beberapa bilangan sehingga ketika urutan bongkahan dibalik, kata aslinya terbentuk. (Untuk sheeshpotongan-potongan itu sh e e sh) Kami juga tidak akan memerlukan potongan berisi huruf dari kedua bagian kata (jika tidak setiap kata akan menjadi semi-palindrome). Misalnya rearbukan semi palindrome karena r ea rmemiliki chunk ( ea) yang berisi huruf dari kedua sisi kata aslinya. Kami menganggap karakter sentral dalam kata panjang ganjil berada di kedua sisi kata, sehingga untuk kata-kata dengan panjang ganjil karakter pusat harus selalu dalam potongan itu sendiri.

Tugas Anda adalah mengambil daftar bilangan bulat positif dan menentukan apakah itu semi palindrom. Kode Anda harus menampilkan dua nilai tidak konsisten yang konsisten, satu jika inputnya semi-palindrome dan lainnya sebaliknya. Namun urutan byte dari kode Anda harus semi-palindrome itu sendiri.

Jawaban akan dinilai dalam byte dengan lebih sedikit byte menjadi lebih baik.

Kasus uji

[] -> True
[1] -> True
[2,1,2] -> True
[3,4,2,2,3,4] -> True
[3,5,1,3,5] -> True
[1,2,3,1] -> False
[1,2,3,3,4,1] -> False
[11,44,1,1] -> False
[1,3,2,4,1,2,3] -> False

Program untuk menghasilkan lebih banyak testcases.


Borrible menunjukkan bahwa ini mirip dengan palindrom Smarandache umum . Jadi, jika Anda ingin membaca lebih lanjut, itu adalah satu tempat untuk memulai.

Wisaya Gandum
sumber
2
Mengapa Anda mendefinisikan semi-palindrom menggunakan string tetapi input Anda adalah array bilangan bulat? Selain membingungkan, ini berarti kami tidak dapat menguji kode sumber kami menggunakan program kami sendiri.
BradC
@BradC Palindromes dan sejenisnya sering dijelaskan dari segi kata-kata, karena sedikit lebih mudah untuk melakukannya.
Erik the Outgolfer
@BradC Strings cenderung memperkenalkan kasus tepi aneh, terutama dalam hal karakter vs byte. Saya memilih nomor karena lebih sederhana. Saya pikir kata-kata akan lebih mudah untuk tujuan penjelasan.
Wheat Wizard
2
Palindrom jenis ini dikenal sebagai Palindrom Generalized Smarandache dalam literatur.
Mengerikan
1
@RosLuP Ya, palindrom "true" juga semi palindrom, cukup perlakukan setiap karakter / integer apa adanya tanpa tambahan "chunking".
BradC

Jawaban:

6

Retina 0.8.2 , 85 69 byte

M`^(.+,)*(\d+,)?(?<-1>\1)*$(?(1)^)|M`^(.+,)*(\d+,)?(?<-1>\1)*$(?(1)^)

Cobalah online! Penjelasan:

M`

Memilih mode Kecocokan. Bahkan, Retina default ke mode Match untuk program single-line, tetapi salinan kode kedua akan selalu cocok jika bukan karena karakter tambahan ini.

^

Pertandingan harus dimulai dari awal.

(.+,)*

Abadikan sejumlah run karakter. Setiap proses harus diakhiri dengan koma.

(\d+,)?

Secara opsional cocok dengan angka dan koma.

(?<-1>\1)*

Secara opsional mencocokkan semua tangkapan dalam urutan terbalik, muncul masing-masing saat cocok.

$

Pertandingan harus berakhir di akhir.

(?(1)^)

Mundur kecuali jika semua tangkapan muncul. Ini berfungsi dengan mengharuskan pertandingan tetap berada di awal string jika kita memiliki tangkapan yang tidak dijatuhkan, yang tidak mungkin.

Neil
sumber
5

Jelly , 27 23 byte

ṖUṁ@Ƒ€ṚẸHḢŒŒHḢŒṖUṁ@Ƒ€ṚẸ

Mengembalikan 1 untuk semi-palindrom, 0 sebaliknya.

Cobalah online!

Bagaimana itu bekerja

ṖUṁ@Ƒ€ṚẸHḢŒŒHḢŒṖUṁ@Ƒ€ṚẸ  Main link. Argument: A (array)

          Œ              Invalid token. Everything to its left is ignored.
           ŒH            Halve; divide A into two halves similar lengths. The middle
                         element (if there is one) goes into the first half.
             Ḣ           Head; extract the first half.
              ŒṖ         Generate all partitions of the first half.
                U        Upend; reverse each chunk of each partition.
                         Let's call the result C.

                     Ṛ   Yield R, A reversed.
                   Ƒ€    Fixed each; for each array P in C, call the link to the left
                         with arguments P and R.
                         Return 1 if the result is P, 0 if not.
                 ṁ@          Mold swapped; replace the n integers of C, in reading
                             order, with the first n integers of R.
                     Ẹ   Exists; check if one of the calls returned 1.
Dennis
sumber
4

Python 2 , 157 153 147 143 byte

-4 byte terima kasih kepada tsh .

s=lambda x,i=0:len(x)<2or[]<x[i:]and(x[-i:]==x[:i])&s(x[i:-i])|s(x,i+1)
s=lambda x,i=0:len(x)<2or[]<x[i:]and(x[-i:]==x[:i])&s(x[i:-i])|s(x,i+1)

Cobalah online!

ovs
sumber
1
Ubah x==x[::-1]untuk len(x)<2menghemat 2 * 2 byte; 143 byte
tsh
4

05AB1E , 59 47 43 41 byte

2äøø€.œ`âʒ`RQ}gĀIg_^q2äøø€.œ`âʒ`RQ}gĀIg_^

-12 byte terima kasih kepada @Emigna .

Cobalah secara online atau verifikasi semua kasus uji .

Penjelasan:

2ä               # Split the input into two parts
                 #  i.e. [3,4,2,0,2,3,4] → [[3,4,2,0],[2,3,4]]
  øø             # Zip twice without filler
                 # This will remove the middle item for odd-length inputs
                 #  i.e. [[3,4,2,0],[2,3,4]] → [[3,2],[4,3],[2,4]] → [[3,4,2],[2,3,4]]
    €.œ          #  Then take all possible partitions for each inner list
                 #   i.e. [[3,4,2],[2,3,4]]
                 #    → [[[[3],[4],[2]],[[3],[4,2]],[[3,4],[2]],[[3,4,2]]],
                 #       [[[2],[3],[4]],[[2],[3,4]],[[2,3],[4]],[[2,3,4]]]]
`                # Push both lists of partitions to the stack
 â               # Take the cartesian product (all possible combinations) of the partitions
                 #  i.e. [[[[3],[4],[2]],[[2],[3],[4]]],
                 #        [[[3],[4],[2]],[[2],[3,4]]],
                 #        ...,
                 #        [[[3,4,2]],[[2,3,4]]]]
  ʒ   }          # Filter this list of combinations by:
   `             #  Push both parts to the stack
    RQ           #  Check if the second list reversed, is equal to the first
                 #   i.e. [[3,4],[2]] and [[2],[3,4]] → 1 (truthy)
       gĀ        # After the filter, check if there are any combinations left
                 #  i.e. [[[[3,4],[2]],[[2],[3,4]]]] → 1 (truthy)
         Ig_     # Check if the length of the input was 0 (empty input-list edge-case)
                 #  i.e. [3,4,2,0,2,3,4] → 7 → 0 (falsey)
            ^    # Bitwise-XOR
                 #  i.e. 1 XOR 0 → 1 (truthy)
             q   # Stop the program (and then implicitly output the top of the stack)
2äøø€.œ`âʒ`RQ}gĀIg_^
                 # Everything after the `q` are no-ops to comply to the challenge rules
Kevin Cruijssen
sumber
Anda dapat mengatasi masalah dengan daftar panjang ganjil dengan øøε.œ} `, menghemat 6 byte. Anda juga tampaknya telah meninggalkan 30 byte yang tidak terpakai di ...
Emigna
@Emigna no-ops pada akhirnya harus mematuhi persyaratan sumber terbatas tantangan
Kamil Drakari
@ KamilDrakari: Oh benar. Lupa bagian itu. Berita
baiknya
@ Emigna Sangat pintar dengan trik ritsleting ganda. Saya tidak senang dengan bagian itu, tetapi ini jauh lebih baik! Btw, sejak Elixir menulis ulang perintah 2-byte dapat digunakan dengan bukan ε }. :)
Kevin Cruijssen
@KevinCruijssen: Ah keren. Saya tidak tahu itu.
Emigna
4

05AB1E , 37 byte

Memanfaatkan teknik yang kira-kira sama dengan Jonathan .

.œʒ€gηOZ;îå}εÂQ}ZĀqĀZ}QÂε}åî;ZOηg€ʒ.œ

Cobalah online!


.œʒ€gηOZ;îå}εÂQ}ZĀqĀZ}QÂε}åî;ZOηg€ʒ.œ

Program lengkap. Menerima daftar dari STDIN, keluaran 1 atau 0 hingga STDOUT.

.œʒ        }

Saring-pertahankan partisi yang memuaskan ...

   €gηOZ;îå

Kondisi ini: Panjang masing-masing ( €g) disimpan dalam daftar, yang awalannya ( η) kemudian dijumlahkan ( O), sehingga memberi kami jumlah kumulatif dari daftar panjang. Kemudian, setengah dari batas maksimum dari daftar itu didorong ke tumpukan - tetapi menyimpan daftar asli juga ( Z;î) dan jika itu terjadi ( å) dalam jumlah kumulatif maka fungsi mengembalikan kebenaran.

εÂQ}

Untuk masing-masing, membandingkan ( Q) a dengan sebuah terbalik, yang didorong secara terpisah pada stack oleh Â. Mengembalikan daftar 0 s dan 1 s.

ZĀq

Maksimum. Jika ada yang benar, maka 1 lainnya 0 . Akhiri eksekusi. Segala sesuatu yang mengikuti ini sepenuhnya diabaikan.

Tuan Xcoder
sumber
3

Python 2 , 275 251 205 byte

-24 byte terima kasih kepada @KevinCruijssen

-44 byte terima kasih kepada @PostLeftGhostHunter

-2 byte lebih banyak berkat @KevinCruijssen

def s(x):
 l=len(x)
 if l<2:return 1>0
 for i in range(1,l/2+1):
	if x[l-i:]==x[:i]:return s(x[i:l-i])
def s(x):
 l=len(x)
 if l<2:return 1>0
 for i in range(1,l/2+1):
	if x[l-i:]==x[:i]:return s(x[i:l-i])

Returns True untuk semi-palindrome, Tidak ada sebaliknya

Cobalah online!

Cowabunghole
sumber
1
Atau cukup kembalikan 1
Jo King
Mengapa s (x) didefinisikan dua kali?
Dr Y Wit
Karena mereka mengatakan menghitung sebagai palindrome ... tetapi mungkin mendefinisikan satu fungsi dengan nama yang sama ???
RosLuP
@RosLuP Ya Anda bisa. Yang kedua hanya menimpa yang pertama
Jo King
3

Jelly ,  33  32 byte

-1 Terima kasih kepada Erik the Outgolfer
Terima kasih juga kepada Dennis untuk perbaikan bug dan melihat untuk mengubah detail implementasi di Jelly.

ẸƇŒḂƇƊ$ƊĊHṀċÄẈṖŒŒṖẈÄċṀHĊƊ$ƊƇŒḂƇẸ

Semi-palindrom menghasilkan 1, yang lain menghasilkan 0.

HAI(2n)

Atau lihat test-suite .

Satu-satunya potongan adalah byte ŒḂs ({3 rd & 4 th } vs {29 th & 30 th }), hanya untuk memungkinkan kode diurai.

Bagaimana?

Semua pekerjaan dilakukan oleh sisi kanan - "Tautan Utama":

ŒṖẈÄċṀHĊƊ$ƊƇŒḂƇẸ - Main Link: list
ŒṖ               - all partitions
           Ƈ     - filter keep those for which this is truthy (i.e. non-zero):
          Ɗ      -   last three links as a monad:
  Ẉ              -     length of each
         $       -     last two links as a monad:
   Ä             -       cumulative addition
        Ɗ        -       last three links as a monad:
     Ṁ           -         maximum
      H          -         halve
       Ċ         -         ceiling
    ċ            -     count
              Ƈ  - filter keep those for which this is truthy:
            ŒḂ   -   is palindrome?
               Ẹ - any?
Jonathan Allan
sumber
3

Perl 6 , 87 79 byte

-8 Bytes dengan beberapa trik dari jawaban Jo King

$!={/\s/&&/^(.+)\s[(.+)\s]*$0$/&&$1.$!}#$!={/\s/&&/^(.+)\s[(.+)\s]*$0$/&&$1.$!}

Cobalah online!

Port jawaban JavaScript tsh. Mengembalikan dua objek Regex yang berbeda.

nwellnhof
sumber
2

Ruby , 129 byte

f=->l{!l[1]||(1...l.size).any?{|x|l[0,x]==l[-x,x]&&f[l[x..~x]]}}#f=->l{!l[1]||(1...l.size).any?{|x|l[0,x]==l[-x,x]&&f[l[x..~x]]}}

Cobalah online!

GB
sumber
1

JavaScript (Node.js) , 139 byte

f=a=>(s=(''+a).replace(/^(.*),((.*),)?\1$/,'$3'))!=a?f(s):/,/.test(s)//^(.*),((.*),)?\1$/,'$3'))!=a?f(s):/,/.test(s)f=a=>(s=(''+a).replace(

Cobalah online!

tsh
sumber
1

C (gcc) (X86), 216 byte

p(L,a,n)int*a;{return n?(memcmp(a,a+L-n,n*4)|p(L-2*n,a+n,L/2-n))&&p(L,a,n-1):1<L;}
#define p(L,a)p(L,a,L/2)//p(L,a,n)int*a;{return n?(memcmp(a,a+L-n,n*4)|p(L-2*n,a+n,L/2-n))&&p(L,a,n-1):1<L;}
#define p(L,a)p(L,a,L/2)

Cobalah online!

p(L,a,n)mengembalikan 0 jika apanjang array Ladalah semi-palindrome, 1 sebaliknya. Karena semua awalan panjang >nsudah diperiksa, ia membandingkan awalan panjang ndengan akhiran panjang n. p(L,a)adalah titik masuknya.

Sayangnya, solusi yang lebih menarik lebih lama:

224 byte

(f(L,a,n))//#define p(L,a)(n=L/2,
int*a,n;
{return n?(memcmp(a,a+L-n,n*4)|f(L-2*n,a+n,L/2-n))&&f(L,a,n-1):1<L;}//{return n?(memcmp(a,a+L-n,n*4)|f(L-2*n,a+n,L/2-n))&&f(L,a,n-1):1<L;}
int*a,n;
#define p(L,a)(n=L/2,f(L,a,n))//(

Cobalah online!

Tidak Disatukan:

(f(L,a,n)) //#define p(L,a)(n=L/2,
int*a,n;
{
  return n 
    ? (memcmp(a, a+L-n, n*4) | f(L-2*n, a+n, L/2-n)) &&
      f(L,a,n-1)
    : 1 < L;
} // { ... } 
int*a,n;
#define p(L,a)(n=L/2,f(L,a,n)) //(
eush77
sumber
1

Japt , 66 byte


@¯X eUsXn}a1 "
ʧV?UÊ<2:ßUéV sVÑ
@¯X eUsXn}a1 "
ʧV?UÊ<2:ßUéV sVÑ

Japt Interpreter

Peningkatan besar versi ini, sebenarnya mengalahkan sebagian besar bahasa praktis sekarang. Sekarang beroperasi pada array bilangan bulat karena metode sebelumnya memiliki bug.

Penjelasan:

@        }a1         Find the first number n > 0 such that...
 ¯X                   the first n elements
     UsXn             and the last n elements
    e                 are the same

"
ʧV?UÊ<2:ßUéV sVÑ    String literal to make it a Semi-palindrome
@¯X eUsXn}a1 "

ʧV?                 If n >= length of input...
    UÊ<2              return true if the length is less than 2
        :            Otherwise...
          UéV         move n elements from the end of the input to the start
              sVÑ     remove the first 2*n elements
         ß            and repeat on the remaining elements
Kamil Drakari
sumber
0

PHP 237 byte

function f($a){for($x=2>$c=count($a);++$i<=$c/2;)$x|=($s=array_slice)($a,0,$i)==$s($a,-$i)&f($s($a,$i,-$i));return$x;}#function f($a){for($x=2>$c=count($a);++$i<=$c/2;)$x|=($s=array_slice)($a,0,$i)==$s($a,-$i)&f($s($a,$i,-$i));return$x;}

fungsi rekursif, mengembalikan true(untuk input yang mengandung kurang dari dua elemen) atau 1untuk kebenaran,
0untuk kepalsuan. Cobalah secara online (mengandung kerusakan).

Panjang kode aktual adalah 118 byte; semi-palindrome dibuat melalui duplikasi kode.

Untuk kinerja yang lebih baik, ganti &dengan &&dan masukkan !$x&&sebelumnya ++$i.

Titus
sumber
0

Scala, 252 byte

def^(s:Seq[Int]):Int={val l=s.size;if(l>1)(1 to l/2).map(i=>if(s.take(i)==s.takeRight(i))^(s.slice(i,l-i))else 0).max else 1}//def^(s:Seq[Int]):Int={val l=s.size;if(l>1)(1 to l/2).map(i=>if(s.take(i)==s.takeRight(i))^(s.slice(i,l-i))else 0).max else 1}

Cobalah online!

PS. Rupanya, solusinya 2 kali lebih lama hanya untuk memenuhi persyaratan bahwa kode sumber juga semi palindrome.

PPS. Bukan kandidat kode-golf tetapi solusi murni fungsional menggunakan pencocokan pola:

  def f(s:Seq[Int], i:Int=1):Int = {
    (s, i) match {
      case (Nil ,_) => 1
      case (Seq(_), _) => 1
      case (l, _) if l.take(i) == l.takeRight(i) => f(l.slice(i,l.size-i), 1)
      case (l, j) if j < l.size/2 => f(l, i+1)
      case (_, _) => 0
    }
  }
Dr Y Wit
sumber
Tantangannya mengharuskan kode Anda juga semi-palindrome. Itu yang paling menyenangkan dalam tantangan.
Wheat Wizard
@ PostLeftGhostHunter, saya menambahkan kode sumber asli ke dalam komentar untuk memenuhi persyaratan. BTW, apa asyiknya membuat kode sumber semi palindrome? Jika saya tidak salah, setiap solusi di utas ini akan dua kali lebih pendek tanpa persyaratan ini. Apakah Anda mengetahui ada solusi yang tidak seperti itu?
Dr Y Wit
0

Perl 6 , 81 byte

($!={/../&&/^(.+)(.*)$0$/&&$1.$!})o&chrs#($!={/../&&/^(.+)(.*)$0$/&&$1.$!})o&chrs

Cobalah online!

Mengembalikan regex /../untuk True dan regex /^(.+)(.*)$0$/untuk False. Bekerja mirip dengan jawaban nwellnhof , tetapi mengonversi daftar menjadi string sebelumnya.

Jo King
sumber