Los palíndromos son divertidos, pero algunas de las otras cuerdas comienzan a sentirse excluidas. Podemos convertir esas cuerdas en palíndromos gruesos dividiéndolos en conjuntos palindrómicos de trozos.

Por ejemplo, la cadena "abcabca"no es un palíndromo si lo leemos carácter por carácter, pero tenemos tres formas diferentes de convertirlo en un palíndromo grueso :

["abcabca"]
["a" "bcabc" "a"]
["a" "bc" "a" "bc" "a"]

Como puede ver, la palindrómica gruesa es un concepto muy inclusivo; cada cadena se puede convertir en un grueso palíndromo de al menos una forma.

Tarea

Escriba un programa o una función que reciba una cadena como entrada y devuelva su fragmentación palindrómica , es decir, el número de sus particiones que son matrices palindrómicas.

Casos de prueba

 OUTPUT | INPUT
--------+---------------------------------------------
      1 | ""                                          
      1 | "a"                                         
      1 | "ab"                                        
      2 | "aa"                                        
      2 | "aaa"                                       
      3 | "abcabca"                                   
      4 | "abababab"                                  
     28 | "abcabcaabababababcabca"                    
      1 | "bbbbabababbbbababbbaaaaa"                  
     20 | "ababbaaaabababbbaaabbbaa"                  
      5 | "baaabaabababaababaaabbaab"                 
     62 | "bbaaababbabbabbbabaabaabb"                 
      2 | "a man a plan a canal panama"               
     25 | "ama nap lan aca nal pan ama"               
     93 | "SATOR   AREPO   TENET   OPERA   ROTAS"     
    976 | "abcabcaabcabcaabcabcaabcabcaabcabcaabcabca"
  28657 | "ababababababababababaababababababababababa"
2097152 | "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

Reglas adicionales

Puede suponer que la entrada consistirá en 42 caracteres ASCII o menos imprimibles, opcionalmente rodeados por los delimitadores de cadena de su idioma y / o seguidos por una nueva línea.
Para cada cadena de entrada válida, su código debe finalizar en menos de un minuto en mi máquina (Intel Core i7-3770, 16 GiB RAM, Fedora 21).

Con un algoritmo adecuado, debería ser fácil cumplir con este límite de tiempo. Sin embargo, lo más probable es que no pueda iterar sobre todas las particiones de la cadena de entrada.
Si elige imprimir el resultado en STDOUT, puede ir seguido de una nueva línea.
Se aplican reglas estándar de código de golf .

code-golf string palindrome set-partitions Dennis
fuente

4

Pyth, 40 34 27 22 bytes

Lhsmy:bd_df!xb>TbS/lb2

Pruébelo en el intérprete en línea .

Fuertemente golfed desde la versión inicial de 40 bytes. Gracias a FryAmTheEggman por señalar un par de operadores útiles (¡los documentos son difíciles de buscar!) Que me han ahorrado 6 bytes en total. Gracias a Dennis por un inteligente ahorro de un solo byte interpretando el resultado xcomo un valor verdadero / falso en lugar de un índice, en !xb>Tblugar de q<bT>Tb.

Cómo funciona:

Definimos una función yque determina la fragmentación de una cadena bal llamarse recursivamente en subcadenas de b. Las funciones se memorizan automáticamente en Pyth, por lo que la recursión tiene muy poca sobrecarga en términos de tiempo.

L                              def y(b): return ___
                 S/lb2         The range [1,2,...,len(b)/2]
          f!xb>Tb              Filter n for which b[:n] == b[-n:]
   m                           Map each n in the list to...
    y:bd_d                     y(b[d:-d])       
 hs                            Take the sum and add one (implicit return)

Sam Cappleman-Lynes
fuente

Sí, la mayor parte del aprendizaje de Pyth es comunal / prueba y error / lectura del lexer, ¡buen trabajo con el golf mucho más! :)

FryAmTheEggman

1

1. Puede guardar dos bytes enviando la función. No hay necesidad de llamarlo yz. 2. En lugar de dos mapas y un filtro, puede usar un solo mapa y un condicional ( enlace ), que ahorra tres bytes.

Dennis

2

CJam ( 41 39 bytes)

qM{_,2/,\f{\~_2$>@2$<@~)/(@=\M*j*}1b)}j

Demostración en línea

Esto es "ansioso" en el sentido de que encuentra el número de palíndromos gruesos para cada cadena "central" (es decir, el resultado de eliminar el mismo número de caracteres de ambos extremos de la cadena original), pero porque utiliza la memoria automática jcada operador se calcula una sola vez, lo que proporciona un programa muy rápido (y guarda algunos caracteres en una implementación no memorizada).

Gracias a Dennis por ahorrar un byte.

Peter Taylor
fuente

1

Mathematica, 77 72 57 bytes

1+Tr[#0/@ReplaceList[#,{a__,b___,a__}:>{b}]]&@*Characters

alephalpha
fuente

1

Perl, 86 bytes

Código de 84 bytes + 2 interruptores

Tiene que haber un método más corto, pero aquí va:

perl -lpe 'sub c{my($x,$i)=@_;$x=~/^(.{$i})(.*)\1$/&&c($2,0*++$s)while++$i<length$x}c$_;$_=++$s'

Toma información de STDIN, una cadena por línea.

Explicación: Para los valores 1<=$i<length(input string), usa la expresión regular /^(.{$i})(.*)\1$/para obtener los fragmentos izquierdo y derecho e incrementa el recuento. Luego, recursivamente, hace lo mismo para la parte central de la cadena.

svsd
fuente

Palíndromos gruesos