# Chunky palindromes

Palindromes are fun, but some of the other strings are starting to feel left out. We can turn those strings into chunky palindromes by splitting them up into palindromic arrays of chunks.

For example, the string "abcabca" isn't a palindrome if we read it character by character, but we have three different ways of making it a chunky palindrome:

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


As you can see, chunky palindromicness is a very inclusive concept; every string can be turned into a chunky palindrome in at least one way.

Write a program or a function that receives a string as input and returns its palindromic chunkiness, i.e., the number of its partitions that are palindromic arrays.

### Test cases

 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"


• You may assume that the input will consist of 42 or less printable ASCII characters, optionally surrounded by your language's string delimiters and/or followed by a newline.

• For each valid input string, your code must finish in less than one minute on my machine (Intel Core i7-3770, 16 GiB RAM, Fedora 21).

With an adequate algorithm, it should be easy to comply with this time limit. However, you will most likely not be able to iterate over all partitions of the input string.

• If you choose to print the output to STDOUT, it may be followed by a single newline.

• Standard rules apply.

# Pyth, 403427 22 bytes

Lhsmy:bd_df!xb>TbS/lb2


Heavily golfed down from initial 40 byte version. Thanks to FryAmTheEggman for pointing out a couple of useful operators (docs are hard to search!) that have saved me 6 bytes total. Thanks to Dennis for a clever single byte saving by interpreting the result of x as a truthy/falsy value rather than an index - !xb>Tb rather than q<bT>Tb.

How it works:

We define a function y which determines the chunkiness of a string b by recursively calling itself on substrings of b. Functions are automatically memoized in Pyth, so recursion has very little overhead in terms of time.

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)

• Yeah, most of learning Pyth is communal / trial and error / reading the lexer, good work with golfing it much more! :) Oct 13 '15 at 17:22
• 1. You can save two bytes by submitting the function. There's no need to call it with yz. 2. Instead of two maps and a filter, you could use a single map and a conditional (link), which saves three bytes. Oct 13 '15 at 19:54

# Pip, 98 66 bytes

-32 thanks to @DLosc!