15
2
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.
Task
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"
Additional rules
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 code-golf rules apply.
Yeah, most of learning Pyth is communal / trial and error / reading the lexer, good work with golfing it much more! :) – FryAmTheEggman – 2015-10-13T17:22:35.720
1
>
yz
. 2. Instead of two maps and a filter, you could use a single map and a conditional (link), which saves three bytes.