15
\$\begingroup\$

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 rules apply.

\$\endgroup\$
4
\$\begingroup\$

Pyth, 40 34 27 22 bytes

Lhsmy:bd_df!xb>TbS/lb2

Try it in the online interpreter.

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)
\$\endgroup\$
  • \$\begingroup\$ Yeah, most of learning Pyth is communal / trial and error / reading the lexer, good work with golfing it much more! :) \$\endgroup\$ – FryAmTheEggman Oct 13 '15 at 17:22
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Dennis Oct 13 '15 at 19:54
2
\$\begingroup\$

CJam (41 39 bytes)

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

Online demo

This is "eager" in the sense that it finds the number of chunky palindromes for each "central" string (i.e. the result of removing the same number of characters from both ends of the original string), but because it uses the auto-memoising j operator each is calculated once only, giving a very fast program (and saving a few characters over a non-memoised implementation).

Thanks to Dennis for a one byte saving.

\$\endgroup\$
1
\$\begingroup\$

Mathematica, 77 72 57 bytes

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

Perl, 86 bytes

84 bytes code + 2 switches

There HAS to be a shorter method, but here goes:

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

Takes input from STDIN, one string per line.

Explanation: For values 1<=$i<length(input string), uses the regex /^(.{$i})(.*)\1$/ to get the left and right chunks and increments the count. Then recursively does the same for the center part of the string.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.