Tugas Anda adalah menentukan seberapa besar palindrome yang sempurna dari sebuah string. Palindrom khas Anda (mis. 12321) adalah palindrom sempurna; kesempurnaannya adalah 1.

Untuk menentukan kesempurnaan string, Anda melihat berapa banyak bagian yang dapat Anda bagi menjadi setiap bagian dari palindrom. Jika ada ambiguitas, seperti dengan aaaa, ketika Anda dapat membaginya menjadi [aa, aa]atau [aaaa]atau [a, aaa]atau [aaa, a], set terpendek akan menimpanya, memberikan aaaaskor 1, yang merupakan panjang dari set terpendek.

Oleh karena itu, Anda harus menulis sebuah program atau fungsi yang akan mengambil satu input dan mengosongkan non-kosong seberapa sempurna itu (yang merupakan panjang dari set terpendek yang Anda dapat membaginya menjadi di mana setiap elemen dalam set adalah palindrom).

Contoh:

1111 -> 1 [1111]
abcb -> 2 [a, bcb]
abcbd -> 3 [a, bcb, d]
abcde -> 5 [a, b, c, d, e]
66a -> 2 [66, a]
abcba-> 1 [abcba]
x -> 1 [x]
ababacab -> 2 [aba, bacab]
bacababa -> 2 [bacab, aba]
26600 -> 3 [2, 66, 00] [my user id] [who has a more perfect user id?]
ababacabBACABABA -> 4 [aba, bacab, BACAB, ABA]

Perhatikan bahwa dalam contoh apa pun dalam tanda kurung tidak boleh menjadi bagian dari output.

Brachylog , 7 byte

~cL↔ᵐLl

Cobalah online!

Penjelasan

~cL          Deconcatenate the input into L
  L↔ᵐL       Reversing all elements of L results in L
     Ll      Output = length(L)

Jelly , 13 12 11 byte

ÞŒḂLÞŒḂ € P $ ÐfḢL 
ŒṖLÞṚ € ⁼ $ ÐfḢL
ŒṖṚ € ⁼ $ ÐfL € Ṃ
ŒṖ mendapatkan partisi
      Jika filter untuk partisi yang
  Ṛ € setelah membalik setiap subpartisi
    ⁼ sama dengan partisi
        Panjang L dari setiap partisi yang berhasil
          Ṃ minimum

Cobalah online!

Spesifikasi

• Input: "ababacab"(sebagai argumen)
• Keluaran: 2

Pyth, 9 byte

lh_I#I#./

Suite uji

Ini membentuk semua partisi input, dari terpendek ke terpanjang. Kemudian, ia memfilter partisi tersebut pada invarian di bawah memfilter elemen pada invarian di bawah pembalikan. Akhirnya, kami mengambil elemen pertama dari daftar partisi yang difilter, dan mengembalikan panjangnya.

Untuk menjelaskan bahwa langkah rumit, mari kita mulai dengan invarian di bawah pembalikan: _I. Itu memeriksa apakah inputnya adalah palindrome, karena memeriksa apakah membalikkan mengubah nilai.

Berikutnya, penyaringan untuk palindromicity: _I#. Ini hanya akan menyimpan elemen palindrom dari daftar.

Berikutnya, kita memeriksa invarian di bawah penyaringan untuk palindromicity: _I#I. Ini benar jika dan hanya jika semua elemen dalam daftar adalah palindrom.

Akhirnya, kami menyaring untuk daftar di mana semua elemen dari daftar adalah palindrom: _I#I#.

Haskell , 83 byte

f s=minimum[length x|x<-words.concat<$>mapM(\c->[[c],c:" "])s,all((==)=<<reverse)x]

Cobalah online!

Ini menggunakan tip hebat dari Zgarb untuk menghasilkan partisi string .

f s = minimum[                               -- take the minimum of the list
    length x |                               -- of the number of partitions in x
    x<-words.concat<$>mapM(\c->[[c],c:" "])s -- where x are all partitions of the input string s
    , all((==)=<<reverse)x                   -- where each partition is a palindrome.
]

Clojure, 111 byte

(defn f[s](if(=()s)0(+(apply min(for[i(range(count s))[a b][(split-at(inc i)s)]:when(=(reverse a)a)](f b)))1)))

Pisahkan pada semua posisi yang memungkinkan, dan ketika bagian pertama adalah palindrome, hasilkan untuk mencari partisi untuk sisa string.

Cobalah online .

Tidak disatukan, menggunakan makro thread-last ->> .

(defn f [s]
  (if (empty? s)
    0
    (let [results (for[i (range(count s))]
                      (let [[a b] (split-at (inc i) s)]
                         (when (= a (reverse a))
                           (f b))))]
      (->> results        ; Take results (a list of integers and nils),
           (filter some?) ; remove null values (they occur when "a" is not a palindrome)
           (apply min)    ; find the minium value,
           inc))))        ; and increment by one.

Versi yang tidak jelas, tolong jangan menulis kode seperti ini: D

(defn f [s]
   (->> (f b)
        (when (= a (reverse a)))
        (let [[a b] (split-at (inc i) s)])
        (for[i (range(count s))])
        (filter some?)
        (apply min)
        inc
        (if (empty? s) 0)))

JavaScript (ES6), 143 126 124 byte

Disimpan 2 byte berkat Neil

Terinspirasi oleh metode NikoNyrh .

s=>(r=1/0,F=(s,i=1,p=0)=>s[p++]?([...o=s.slice(0,p)].reverse().join``==o&&(s[p]?F(s.slice(p),i+1):r=r<i?r:i),F(s,i,p)):r)(s)

Diformat dan dikomentari

s => (                          // given a string 's':
  r = 1 / 0,                    // 'r' = best score, initialized to +Infinity
  F = (                         // 'F' is a recursive function that takes:
    s,                          //   - the current string 's'
    i = 1,                      //   - a substring counter 'i'
    p = 0                       //   - a character pointer 'p'
  ) =>                          //
    s[p++] ? (                  // if we haven't reached the end of the string:
      [...o = s.slice(0, p)]    //   compute 'o' = substring of length 'p'
      .reverse().join`` == o    //   if 'o' is a palindrome,
      && (                      //   then:
        s[p] ?                  //     if there are still characters to process:
          F(s.slice(p), i + 1)  //       do a recursive call on the remaining part
        :                       //     else:
          r = r < i ? r : i     //       update the score with r = min(r, i)
      ),                        //   in all cases:
      F(s, i, p)                //     do a recursive call with a longer substring
    ) :                         // else:
      r                         //   return the final score
  )(s)                          // initial call to F()

Uji kasus

let f =

s=>(r=1/0,F=(s,i=1,p=0)=>s[p++]?([...o=s.slice(0,p)].reverse().join``==o&&(s[p]?F(s.slice(p),i+1):r=r<i?r:i),F(s,i,p)):r)(s)

console.log(f('1111'))      // -> 1 [1111]
console.log(f('abcb'))      // -> 2 [a, bcb]
console.log(f('abcbd'))     // -> 3 [a, bcb, d]
console.log(f('abcde'))     // -> 5 [a, b, c, d, e]
console.log(f('66a'))       // -> 2 [66, a]
console.log(f('abcba'))     // -> 1 [abcba]
console.log(f('x'))         // -> 1 [x]
console.log(f('ababacab'))  // -> 2 [aba, bacab]
console.log(f('bacababa'))  // -> 2 [bacab, aba]

Pendekatan awal, 173 168 byte

Fungsi rekursif yang cukup panjang yang menghitung semua kemungkinan partisi dari string input.

f=(s,b=1/(k=0))=>++k>>(L=s.length)?b:f(s,(k|1<<30).toString(2).slice(-L).match(/(.)\1*/g).some(m=>[...o=s.slice(i,i+=m.length)].reverse(n++).join``!=o,n=i=0)?b:b<n?b:n)

Diformat dan dikomentari

f = (                           // given:
  s,                            //   - a string 's'
  b = 1 / (k = 0)               //   - a best score 'b' (initialized to +Infinity)
) =>                            //   - a counter 'k' (initialized to 0)
  ++k >> (L = s.length) ?       // if 'k' is greater or equal to 2^(s.length):
    b                           //   stop recursion and return 'b'
  :                             // else:
    f(                          //   do a recursive call:
      s,                        //     using the same string 's'
      (k | 1 << 30)             //     compute an array containing the groups of identical
      .toString(2).slice(-L)    //     digits in the binary representation of 'k', padded
      .match(/(.)\1*/g)         //     with leading zeros and cut to the length of 's'
      .some(g =>                //     for each group 'g' in this array:
        [... o = s.slice(       //       compute 'o' = corresponding substring of 's',
          i, i += g.length      //       starting at position 'i' with the same length
        )]                      //       (e.g. s = 'abcd' / k = 0b1101 => 'ab','c','d')
        .reverse(n++)           //       increment the number of groups 'n'
        .join`` != o,           //       return true if this substring is NOT a palindrome
        n = i = 0               //       initialize 'n' and 'i'
      ) ?                       //     if some() returns true:
        b                       //       invalid partition -> keep the previous score 'b'
      :                         //     else:
        b < n ? b : n           //       valid partition -> use min(b, n)
    )                           //   end of recursive call

Uji kasus

f=(s,b=1/(k=0))=>++k>>(L=s.length)?b:f(s,(k|1<<30).toString(2).slice(-L).match(/(.)\1*/g).some(m=>[...o=s.slice(i,i+=m.length)].reverse(n++).join``!=o,n=i=0)?b:b<n?b:n)

console.log(f('1111'))      // -> 1 [1111]
console.log(f('abcb'))      // -> 2 [a, bcb]
console.log(f('abcbd'))     // -> 3 [a, bcb, d]
console.log(f('abcde'))     // -> 5 [a, b, c, d, e]
console.log(f('66a'))       // -> 2 [66, a]
console.log(f('abcba'))     // -> 1 [abcba]
console.log(f('x'))         // -> 1 [x]
console.log(f('ababacab'))  // -> 2 [aba, bacab]
console.log(f('bacababa'))  // -> 2 [bacab, aba]

Jelly , 10 byte

ŒṖŒḂ€¬$ÞḢL

Cobalah online!

Bagaimana?

Menggunakan fakta bahwa
[0]<[0,0]<[0,0,0],...,<[0,...,0,1]<...
- jadi jika kita mengurutkan partisi dengan kunci "tidak palindrom untuk setiap bagian" entri pertama akan semuanya palindrom dan panjang minimal.

Catatan: string panjang n yang tidak kosong akan selalu menghasilkan kunci dengan n nol, karena semua string 1 panjang adalah palindromik.

ŒṖŒḂ€¬$ÞḢL - Main link: s             e.g. 'abab'
ŒṖ         - partitions of s               [['a','b','a','b'],['a','b','ab'],['a','ba','b'],['a','bab'],['ab','a','b'],['ab','ab'],['aba','b'],['abab']]
       Þ   - sort by (create the following key and sort the partitions by it):
      $    -   last two links as a monad:  (key evaluations aligned with above:)
  ŒḂ€      -     is palindromic? for €ach   [ 1 , 1 , 1 , 1 ] [ 1 , 1 , 0  ] [ 1 , 0  , 1 ] [ 1 , 1   ] [ 0  , 1 , 1 ] [ 0  , 0  ] [ 1   , 1 ] [ 0    ] 
     ¬     -     not                        [ 0 , 0 , 0 , 0 ] [ 0 , 0 , 1  ] [ 0 , 1  , 0 ] [ 0 , 0   ] [ 1  , 0 , 0 ] [ 1  , 1  ] [ 0   , 0 ] [ 1    ]
           - ...i.e.:         
           -       making the sorted keys: [[ 0 , 0   ],[ 0   , 0 ],[ 0 , 0 , 0 , 0 ],[ 0 , 0 , 1  ],[ 0 , 1  , 0 ],[ 1    ],[ 1  , 0 , 0 ],[ 1  , 1  ]]
           -  hence the sorted partitions: [['a','bab'],['aba','b'],['a','b','a','b'],['a','b','ab'],['a','ba','b'],['abab'],['ab','a','b'],['ab','ab']]
        Ḣ  - head of the result             ['a','bab']
         L - length                         2

Haskell , 69 byte

x!(a:b)|p<-a:x=p!b++[1+f b|p==reverse p]
x!y=[0|x==y]
f=minimum.(""!)

Menentukan fungsi f. Cobalah online!

Penjelasan

Fungsi pembantu infiks x ! ymenghitung daftar bilangan bulat, yang merupakan panjang dari beberapa kelengkapan reverse x ++ ymenjadi palindrom reverse xyang dibiarkan utuh. Dijamin mengandung panjang pemisahan minimum jika ytidak kosong. Cara kerjanya adalah ini.

• Jika ytidak kosong, char dikeluarkan dan didorong ke dalam x. Jika xmenjadi palindrome, kami memanggil fungsi utama fdi bagian ekor ydan menambahkan 1 untuk menjelaskan x. Kami juga memanggil !yang baru xdany tidak ketinggalan potensi pemecahan.
• Jika ykosong, kami kembali [0](satu pemisahan dengan panjang 0) jika xjuga kosong, dan [](tidak ada pemisahan) jika tidak.

Fungsi utama fhanya memanggil "" ! xdan mengambil hasil minimum.

x!(a:b)|          -- Function ! on inputs x and list with head a and tail b,
  p<-a:x=         -- where p is the list a:x, is
  p!b++           -- the numbers in p!b, and
  [1+f b|         -- 1 + f b,
   p==reverse p]  -- but only if p is a palindrome.
x!y=              -- Function ! on inputs x and (empty) list y is
  [0|             -- 0,
   x==y]          -- but only if x is also empty.
f=                -- Function f is:
  minimum.(""!)   -- evaluate ! on empty string and input, then take minimum.

JavaScript (Firefox 30-57), 97 byte

f=(s,t=``,i=0)=>s?Math.min(...(for(c of s)if([...t+=c].reverse(++i).join``==t)1+f(s.slice(i)))):0

Port ES6:

f=(s,t=``)=>s?Math.min(...[...s].map((c,i)=>[...t+=c].reverse().join``==t?1+f(s.slice(i+1)):1/0)):0

<input oninput=o.textContent=f(this.value)><pre id=o>

Tampaknya solusi yang sangat sederhana sehingga saya terus berpikir saya telah melupakan sesuatu tetapi setidaknya lulus semua test case.

Haskell, 139 116 109 byte

h[]=[[]]
h x=words.concat<$>mapM(\c->[[c],c:" "])x
r x=reverse x==x
g x=minimum[length y|y<-h x,and$r<$>y]

Masih hijau di golf Haskell, tetapi ini adalah upaya terbaik yang bisa saya lakukan dengan cepat.

• h adalah fungsi yang membuat Daftar dari semua kemungkinan daftar yang berdekatan (seperti string). Dibutuhkan input String dan memecahkannya untuk g.
• r adalah fungsi sederhana yang mengembalikan Boolean untuk jika Daftar adalah palindrom
• g adalah fungsi utama yang mengambil daftar input, memanggil h untuk mendapatkan daftar kemungkinan selanjutnya yang bersebelahan, memfilter (and.map r)untuk menghapus sub daftar yang tidak mengandung palindrom, di mana panjang titik diterapkan ke daftar, dan hasilnya adalah disortir sehingga kita bisa mengambil kepala yang merupakan jawabannya.

Saya berpikir jawaban yang lebih baik mungkin dapat memanfaatkan sifat Daftar yang tidak deterministik di Haskell melalui penggunaan Applicatives. Dimungkinkan untuk memotong banyak byte dari fungsi h dengan menggunakan aplikasi, bahkan jika kita harus mengimpor Control.Applicative. Komentar untuk perbaikan dipersilahkan.

UPDATE1

Penghematan besar berdasarkan pengingat Laikoni tentang fungsi minimum. Menghapus semacam sebenarnya memungkinkan saya untuk menjatuhkan impor Data.List karena minimum didefinisikan di Prelude!

UPDATE2

Berkat saran nimi tentang penggunaan daftar pemahaman sebagai pengganti yang berguna untuk filter.map. Itu menyelamatkan saya beberapa byte. Saya juga meminjam trik partisi String yang rapi dari Laikonis dan menyimpan beberapa byte di sana juga.

PHP, 319 Bytes

for(;$i<$l=strlen($s=$argn);$i++)for($j=$l-$i;$j;$j--)strrev($r=substr($s,$i,$j))!=$r?:$e[+$i][]=$r;uasort($e,function($a,$b){return strlen($b[0])<=>strlen($a[0])?:count($a)<=>count($b);});foreach($e as$p=>$v)foreach($v as$w){$s=preg_replace("#^(.{{$p}})$w#","$1".str_pad("",strlen($w),"ö"),$s,1,$c);!$c?:++$d;}echo$d;

Versi Online

Diperluas

for(;$i<$l=strlen($s=$argn);$i++)
for($j=$l-$i;$j;$j--)strrev($r=substr($s,$i,$j))!=$r?:$e[+$i][]=$r; #Make all substrings that are palindromes for each position
uasort($e,function($a,$b){return strlen($b[0])<=>strlen($a[0])?:count($a)<=>count($b);}); # sort palindrome list high strlen lowest count for each position
foreach($e as$p=>$v)
foreach($v as$w){
    $s=preg_replace("#^(.{{$p}})$w#","$1".str_pad("",strlen($w),"ö"),$s,1,$c);
    !$c?:++$d; # raise count
}
echo$d; # Output

Versi yang lebih panjang tanpa E_NOTICE dan Output array yang dihasilkan