Sua tarefa é determinar o quanto de um palíndromo perfeito é uma string. Seu palíndromo típico (por exemplo, 12321) é um palíndromo perfeito; sua perfeição é 1.

Para determinar a perfeição de uma sequência, você vê quantas seções você pode dividir em onde cada seção é um palíndromo. Se houver ambiguidades, como com aaaa, como você pode dividi-lo em [aa, aa]ou [aaaa]ou [a, aaa]ou [aaa, a], o menor conjunto substituirá, dando aaaauma pontuação de 1, que é o tamanho do menor.

Portanto, você deve escrever um programa ou função que receba uma entrada não vazia e produza quão perfeita ela é (qual é o comprimento do menor conjunto que você pode dividir em que cada elemento do conjunto é um palíndromo).

Exemplos:

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]

Observe que, nos exemplos, qualquer coisa entre colchetes não deve fazer parte da saída.

Braquilog , 7 bytes

~cL↔ᵐLl

Experimente online!

Explicação

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

Geléia , 13 12 11 bytes

PLÞŒḂ € P $ ÐfḢL 
ŒṖLÞṚ € ⁼ $ ÐfḢL
⁼ € ÐfL € Ṃ
ŒṖ obter partições
      Ðf filtro para partições que
  After € depois de reverter cada subpartição
    ⁼ é igual à partição
        L € de comprimento de cada partição bem sucedida
          Ṃ mínimo

Experimente online!

Especificações

• Entrada: "ababacab"(como argumento)
• Saída: 2

Pitão, 9 bytes

lh_I#I#./

Suíte de teste

Isso forma todas as partições da entrada, do menor para o maior. Em seguida, filtra essas partições na invariância, filtrando os elementos na invariância, na reversão. Finalmente, pegamos o primeiro elemento da lista filtrada de partições e retornamos seu comprimento.

Para explicar esse passo complicado, vamos começar com invariância sob inversão: _I. Isso verifica se sua entrada é um palíndromo, porque verifica se a reversão altera o valor.

Em seguida, filtrando para palindromicity: _I#. Isso manterá apenas os elementos palíndromos da lista.

Em seguida, vamos verificar para invariância sob filtragem para palindromicity: _I#I. Isso é verdade se e somente se todos os elementos da lista são palíndromos.

Finalmente, filtrar listas onde todos os elementos da lista são palíndromos: _I#I#.

Haskell , 83 bytes

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

Experimente online!

Isso usa a ótima dica do Zgarb para gerar partições de 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 bytes

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

Divide-se em todas as posições possíveis e, quando a primeira parte é um palíndromo, prossegue para encontrar uma partição para o restante da sequência.

Experimente online .

Ungolfed, usa a macro 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.

Uma versão obscura, por favor, não escreva código como este: 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 bytes

Economizou 2 bytes graças a Neil

Inspirado pelo método 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)

Formatado e comentado

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

Casos de teste

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]

Abordagem inicial, 173 168 bytes

Uma função recursiva bastante longa que calcula todas as partições possíveis da string de entrada.

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)

Formatado e comentado

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

Casos de teste

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]

Gelatina , 10 bytes

ŒṖŒḂ€¬$ÞḢL

Experimente online!

Quão?

Usa o fato de que
[0]<[0,0]<[0,0,0],...,<[0,...,0,1]<...
- assim, se classificarmos as partições por uma chave "não é palindrômica para cada parte", a primeira entrada será toda palindrômica e de comprimento mínimo.

Nota: qualquer string não vazia de comprimento n sempre resultará em uma chave com n zeros, pois todas as strings de comprimento 1 são palíndricas.

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

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

Define uma função f. Experimente online!

Explicação

A função auxiliar de infix x ! ycalcula uma lista de números inteiros, que são os comprimentos de algumas divisões de reverse x ++ yem palíndromos onde reverse xé deixada intacta. É garantido que contenha o comprimento da divisão mínima se ynão estiver vazio. Como funciona é isso.

• Se ynão estiver vazio, um caractere é disparado e pressionado x. Se xse tornar um palíndromo, chamamos a função principal fno final ye adicionamos 1 para dar conta x. Além disso, apelamos !ao novo xe ya não perder nenhuma divisão potencial.
• Se yestiver vazio, retornamos [0](uma divisão do comprimento 0) se xtambém estiver vazia e [](sem divisão) caso contrário.

A função principal fapenas chama "" ! xe aceita o mínimo dos resultados.

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 bytes

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

Porta 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>

Parece uma solução tão simples que fico pensando que esqueci alguma coisa, mas ela passa pelo menos em todos os casos de teste.

Haskell, 139 116 109 bytes

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]

Ainda verde no golfe Haskell, mas aqui está a minha melhor tentativa que posso apresentar rapidamente.

• h é uma função que cria uma lista de todas as subsequências contíguas possíveis de uma lista (como uma string). Ele pega a String de entrada e a divide em g.
• r é uma função simples que retorna um booleano para se uma lista é um palíndromo
• g é a função principal que recebe uma lista de entrada, chama h para obter a lista de possibilidades de subsequência contígua, filtra (and.map r)para remover sub-listas que não contêm um palíndromo, em que o comprimento do ponto é aplicado à lista e, em seguida, o resultado é classificados para que possamos agarrar a cabeça, que é a resposta.

Eu estava pensando que uma resposta melhor poderia alavancar a natureza não determinística das Listas em Haskell através do uso de Aplicantes. Pode ser possível reduzir muitos bytes da função h usando aplicativos, mesmo que tenhamos que importar Control.Applicative. Comentários para melhorias são bem-vindos.

UPDATE1

Economias enormes com base no lembrete de Laikoni sobre a função mínima. A remoção da classificação realmente me permitiu descartar a importação Data.List porque o mínimo está definido no Prelude!

UPDATE2

Graças à sugestão de nimi sobre o uso de compreensão de lista como um substituto útil para filter.map. Isso me salvou alguns bytes. Também peguei emprestado o puro truque de partição String da resposta Laikonis e salvei alguns bytes também.

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;

Versão Online

Expandido

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

Versão mais longa sem E_NOTICE e Saída da matriz resultante