Twoim zadaniem jest określenie, ile doskonałego palindromu ma struna. Twój typowy palindrom (np. 12321) to idealny palindrom; jego doskonałość wynosi 1.

Aby określić doskonałość łańcucha, zobaczysz, ile sekcji można podzielić na sekcje, gdzie każda sekcja to palindrom. Jeśli występują niejednoznaczności, takie jak z aaaa, ponieważ można go podzielić na [aa, aa]lub [aaaa]lub [a, aaa]lub [aaa, a], najkrótszy zestaw zastąpi się, dając aaaawynik 1, czyli długość najkrótszego zestawu.

Dlatego musisz napisać program lub funkcję, która pobierze jedno niepuste wejście i wyświetli, jaki jest doskonały (czyli długość najkrótszego zestawu, w którym można go podzielić na miejsce, gdzie każdy element w zestawie jest palindromem).

Przykłady:

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]

Zauważ, że w przykładach nic w nawiasach kwadratowych nie powinno być częścią wyniku.

Brachylog , 7 bajtów

~cL↔ᵐLl

Wypróbuj online!

Wyjaśnienie

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

Galaretka , 13 12 11 bajtów

ŒṖLÞŒḂ € P $ ÐfḢL 
ŒṖLÞṚ € ⁼ $ ÐfḢL
ŒṖṚ € ⁼ $ ÐfL € Ṃ
ŒṖ uzyskać partycje
      Filtr dla partycji, które
  Ṛ € po odwróceniu każdej podsekcji
    ⁼ jest równe partycji
        L € długość każdej udanej partycji
          Ṃ minimum

Wypróbuj online!

Okular

• Dane wejściowe: "ababacab"(jako argument)
• Wydajność: 2

Pyth, 9 bajtów

lh_I#I#./

Zestaw testowy

Tworzy to wszystkie partycje danych wejściowych, od najkrótszych do najdłuższych. Następnie filtruje te partycje przy niezmienniczości pod filtrowaniem elementów na niezmienniczości przy odwróceniu. Na koniec bierzemy pierwszy element filtrowanej listy partycji i zwracamy jej długość.

Aby wyjaśnić tę skomplikowaną krok, zacznijmy niezmienności pod odwróceniu: _I. To sprawdza, czy jego wejście jest palindromem, ponieważ sprawdza, czy cofanie zmienia wartość.

Następnie, filtrowanie palindromicity: _I#. Pozwoli to zachować tylko palindromiczne elementy listy.

Następnie sprawdzamy niezmienności pod filtrowanie palindromicity: _I#I. Jest to prawdą wtedy i tylko wtedy, gdy wszystkie elementy listy są palindromami.

Wreszcie możemy filtrować na listach, gdzie wszystkie elementy listy są Palindromy: _I#I#.

Haskell , 83 bajty

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

Wypróbuj online!

Wykorzystuje świetną wskazówkę Zgarb do generowania partycji łańcuchowych .

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 bajtów

(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)))

Dzieli się na wszystkich możliwych pozycjach, a gdy pierwsza część jest palindromem, przechodzi do podziału na resztę ciągu.

Wypróbuj online .

Ungolfed, używa makra ostatniego wątku ->> .

(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.

Niejasna wersja, proszę nie pisać takiego kodu: 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 bajtów

Zaoszczędzono 2 bajty dzięki Neilowi

Inspirowany metodą 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)

Sformatowane i skomentowane

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()

Przypadki testowe

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]

Wstępne podejście, 173 168 bajtów

Dość długa funkcja rekurencyjna, która oblicza wszystkie możliwe partycje ciągu wejściowego.

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)

Sformatowane i skomentowane

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

Przypadki testowe

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]

Galaretka , 10 bajtów

ŒṖŒḂ€¬$ÞḢL

Wypróbuj online!

W jaki sposób?

Wykorzystuje fakt, że
[0]<[0,0]<[0,0,0],...,<[0,...,0,1]<...
- w ten sposób, jeśli posortujemy partycje według klucza „nie jest palindromiczny dla każdej części”, pierwszy wpis będzie cały palindromiczny i ma minimalną długość.

Uwaga: każdy niepusty ciąg długości n będzie zawsze prowadzić w taki klucz z n zer, ponieważ wszystkie długości 1 ciągi są palindromiczna.

ŒṖŒḂ€¬$ÞḢ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 bajtów

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

Definiuje funkcję f. Wypróbuj online!

Wyjaśnienie

Funkcja pomocnicza infix x ! yoblicza listę liczb całkowitych, które są długościami niektórych podziałów reverse x ++ yna palindromy, w których reverse xpozostaje nienaruszona. Gwarantuje się, że zawiera długość minimalnego podziału, jeśli nie yjest pusty. Jak to działa?

• Jeśli yjest niepusty, znak char jest zrywany i wpychany do x. Jeśli xstaje się palindromem, wywołujemy główną funkcję fna końcu yi dodajemy 1, aby uwzględnić x. Wzywamy również !do nowego xi ynie przegap żadnego potencjalnego podziału.
• Jeśli yjest pusty, zwracamy [0](jeden podział o długości 0), jeśli xjest również pusty, i [](bez podziału) w przeciwnym razie.

Główna funkcja fpo prostu wywołuje "" ! xi zajmuje minimum wyników.

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 bajtów

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>

Wydaje się to tak proste rozwiązanie, że ciągle myślę, że o czymś zapomniałem, ale przynajmniej mija wszystkie testy.

Haskell, 139 116 109 bajtów

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]

Wciąż gra w golfa w Haskell, ale oto moja najlepsza próba, jaką mogę szybko wymyślić.

• h jest funkcją, która tworzy listę wszystkich możliwych ciągłych podciągów listy (jak ciąg znaków). Pobiera wejściowy ciąg znaków i dzieli go na g.
• r jest prostą funkcją zwracającą wartość logiczną, jeśli lista jest palindromem
• g jest główną funkcją, która pobiera listę wejściową, wywołuje h, aby uzyskać listę ciągłych możliwości podsekwencji, filtruje, (and.map r)aby usunąć listy podrzędne, które nie zawierają palindromu, w którym długość punktu jest stosowana do listy, a następnie wynikiem jest posortowane, abyśmy mogli złapać głowę, która jest odpowiedzią.

Myślałem, że lepsza odpowiedź może być w stanie wykorzystać niedeterministyczny charakter list w Haskell poprzez zastosowanie Aplikacji. Możliwe jest, że można ogolić wiele bajtów z funkcji h za pomocą aplikacji, nawet jeśli musimy zaimportować Control.Applicative. Komentarze do ulepszeń są mile widziane.

AKTUALIZACJA 1

Ogromne oszczędności oparte na przypomnieniu Laikoni o minimalnej funkcji. Usunięcie sortowania faktycznie pozwoliło mi upuścić import Data.List, ponieważ minimum jest zdefiniowane w Prelude!

AKTUALIZACJA 2

Dzięki sugestii nich o użyciu wyrażeń listowych jako przydatnego zamiennika filter.map. To zaoszczędziło mi kilka bajtów. Pożyczyłem też schludną sztuczkę dotyczącą partycji String z odpowiedzi Laikonis i zapisałem tam również kilka bajtów.

PHP, 319 bajtów

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;

Wersja online

Rozszerzony

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

Dłuższa wersja bez E_NOTICE i wyświetlenie wynikowej tablicy