17
\$\begingroup\$

A palindrome is a word which is spelled the same backwards and forwards. For example, "racecar" is a palindrome as is "redder". A double palindrome is a palindrome whose halves are also palindromes. For example, "abbabba" is a double palindrome, as the half "abba" is also a palindrome. Similarily, "abaababaaba" is a triple palindrome and so on. Your task is to take a string and return the degree of palindromess. If the string is not a palindrome, return 0.

In order to avoid ambiguity in some edge-cases, the first two letters are guranteed to be different, and the input has at least three letters.

The input string consists entirely of lowercase letters.

Examples

"notapalindrome"
-> 0

"madam"
-> 1

"xyxxxyx"
-> 1

"racecarracecar"
-> 2

"ababababa"
-> 3

"abbaabbaabbaabba"
-> 3
\$\endgroup\$
7
  • 2
    \$\begingroup\$ Suggested test case: xyxxxyx, It's a palindrome and its halves contain non-trivial palindromes but are not actually palindromes themselves. \$\endgroup\$
    – Wheat Wizard
    Jan 19 at 9:36
  • \$\begingroup\$ Palindromess? Palindromeness? Palindromosity? Palindromity? \$\endgroup\$ Jan 19 at 14:15
  • \$\begingroup\$ @DJClayworth Palindromicity? \$\endgroup\$
    – DLosc
    Jan 19 at 19:05
  • \$\begingroup\$ I don't find it clear what a triple palindrome is from the description and examples so far (it's not clear how to generalize "halves"), much less higher order palindromes. \$\endgroup\$ Jan 20 at 5:32
  • 1
    \$\begingroup\$ @GregMartin Okay, the concept of "half". If the string has equal length, the half is just half of the string (ex. "format", a half would be "for" or "mat" ). If the string has odd length, you include the center character (ex. "hello", a half would be "hel" or "llo"). It doesn't matter which half you choose. If one of the halves is a palindrome, then they are identical. Anyways, a triple palindrome is a palindrome, whose halves are double palindromes. \$\endgroup\$
    – AnttiP
    Jan 20 at 5:45

13 Answers 13

7
\$\begingroup\$

Python 2, 41 bytes

f=lambda s:s==s[::-1]and-~f(s[len(s)/2:])

Try it online!

Simple recursive function. If the string is not a palindrome, returns false instead of 0 (which I think is allowed for Python).

\$\endgroup\$
2
  • \$\begingroup\$ First I ever heard of ~ tbh... I suppose you could add 0 to the result to cast it to int f=lambda s:0+(s==s[::-1]and-~f(s[len(s)/2:])) \$\endgroup\$
    – airstrike
    Jan 19 at 15:22
  • 1
    \$\begingroup\$ @airstrike No need, False is treated as 0 for Python. See meta discussion. ~x is -x-1, so it's a common trick to use it for increment/decrement (e.g. -~x == x+1 and ~-x == x-1). The advantage is you can save a whitespace before the expression. \$\endgroup\$ Jan 19 at 20:51
4
\$\begingroup\$

Vyxal, 8 bytes

‡Ḃ=‡½hŀL

Try it Online!

‡  ‡  ŀ  # Collect until false
 Ḃ=      # Is a palindrome
    ½h   # Get first half (rounded up)

       L # Get length
\$\endgroup\$
4
\$\begingroup\$

Husk, 9 bytes

←VS≠↔¡o←½

Try it online!

Longer recursion: ?K0ö→₀←½S≠↔

\$\endgroup\$
3
\$\begingroup\$

Jelly, 10 bytes

ŒHḢ$ŒḂпL’

A monadic Link accepting a list of characters that yields an integer.

Try it online!

So many 2 byte instructions:(

How?

ŒHḢ$ŒḂпL’ - Link: list of characters, S
      п   - collect up input values while...
    ŒḂ     - ...condition: is a palindrome?
   $       - ...next input: last two links as a monad:
ŒH         -      split into halves (first 1 longer if odd length)
  Ḣ        -      head
        L  - length
         ’ - decrement
\$\endgroup\$
3
\$\begingroup\$

BQN, 21 bytes

{𝕩≡⌽𝕩?1+𝕊𝕩↑˜⌈÷⟜2≠𝕩;0}

Anonymous function that takes a string and returns an integer. Run it online!

Explanation

{𝕩≡⌽𝕩?1+𝕊𝕩↑˜⌈÷⟜2≠𝕩;0}
{                     }  Define a block function
      ?                  If:
   ⌽𝕩                      The argument, reversed
 𝕩≡                         is the same as the argument
                         Then (the argument is a palindrome):
                  ≠𝕩       Length of the argument
              ÷⟜2          Divided by 2
             ⌈             Rounded up
          𝕩↑˜              Take that many characters from the argument
         𝕊                 Recurse
       1+                  Add 1 to the result of the recursive call
                    ;    Else (the argument is not a palindrome):
                     0     0
\$\endgroup\$
2
\$\begingroup\$

R, 61 bytes

Or R>=4.1, 54 bytes by replacing the word function with a \.

f=function(x)"if"(any(x-rev(x)),0,1+f(x[1:((sum(x|1)+1)/2)]))

Try it online!

I hate and am ashamed of the part taking first half of the input, but couldn't think of something better...

\$\endgroup\$
2
\$\begingroup\$

Java 8, 101 bytes

s->{int r=0;for(;s.contains(new StringBuffer(s).reverse());r++)s=s.substring(s.length()/2);return r;}

Try it online.

Explanation:

s->{          // Method with String parameter and integer return-type
  int r=0;    //  Result-integer, starting at 0
  for(;s.contains(new StringBuffer(s).reverse())
              //  Loop as long as the String is a palindrome:
     ;r++)    //    After every iteration: Increase the result by 1
    s=        //   Replace the String with:
      s.substring(s.length()/2);
              //    Its second halve; substring at index-range [length//2,length)
  return r;}  //  After the loop, return the result
\$\endgroup\$
2
\$\begingroup\$

Brachylog, 10 9 bytes

-1 byte thanks to a clever observation from Unrelated String

↔?ḍt↰<|∧0

Try it online!

Alternate 9-byte solution: ↔?ḍt↰<.∨0 (Try it online!)

Explanation

↔?ḍt↰<|∧0
↔          The input reversed
 ?         is the same as the input
  ḍ        Split into two halves
   t       Take the second half (which is the longer one if they aren't the same)
    ↰      Recurse
     <     First integer greater than the result of the recursive call
      |    If the preceding part failed (because the input isn't a palindrome):
       ∧   Break unification with the input
        0  and set the output to 0
\$\endgroup\$
3
  • 2
    \$\begingroup\$ If you're willing to let eventual labeling do some of the work, +₁ can be golfed to < \$\endgroup\$ Jan 20 at 21:08
  • 1
    \$\begingroup\$ @UnrelatedString Oh, very nice! TBH I still have difficulty guessing when I have to spell stuff out and when Brachylog will automatically do the thing that I want for me. \$\endgroup\$
    – DLosc
    Jan 20 at 21:24
  • \$\begingroup\$ Come to think of it, I thought to try < because I had just tried removing the trailing 0 (letting the output remain unbound), and I can't say I'm surprised that didn't work: since there's no real minimum it's able to label all outputs to 0, but what's really weird is that if you use the I/O style in your TIO link it seems to actually consistently land the output at 1 less than intended instead. CLP(FD) never fails to be enigmatic... \$\endgroup\$ Jan 21 at 0:28
1
\$\begingroup\$

Haskell, 51 bytes

v s|s/=reverse s=0|0<1=1+v(take(div(1+length s)2)s)

Try it Online!

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

Retina 0.8.2, 36 bytes

+m`^((.)+.?)(?<-2>\2)+(?(2)^)$
$1¶
¶

Try it online! Link includes test cases. Accepts a double letter as a palindrome but not a single letter. Explanation:

+`

Repeat until no more matches can be made:

m`^((.)+.?)

Match the first half (including the middle character where relevant) of the palindrome, ...

(?<-2>\2)+(?(2)^)$

... then match the characters captured by capture group 2 in reverse, popping as we go, until there are none left, and...

$1¶

... replace the second half of the palindrome with a newline.

Count the number of newlines.

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

Charcoal, 20 bytes

W⁼θ⮌θ«≔∕⁺θψ²θ⊞υω»ILυ

Try it online! Link is to verbose version of code. Explanation:

W⁼θ⮌θ«

Repeat while the word equals its reverse...

≔∕⁺θψ²θ

... append a character, then halve its length, so that odd lengths get rounded up, and...

⊞υω

... keep track of how many times the loop executed.

»ILυ

Output the final number of loops.

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

JavaScript (Node.js), 57 bytes

f=n=>n==[...n].reverse().join``&&f(n.slice(n.length/2))+1

Try it online!

A port of Surculose Sputum's Python answer (I couldn't find any other shorter way). Replace && with ? and add :0 at the end of the program to make it return 0 in cases where it currently returns false, for an extra byte.

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

05AB1E (legacy), 10 bytes

[ÐRÊ#2äн}N

Try it online or verify all test cases.

Explanation:

[      # Loop indefinitely:
 Ð     #  Triplicate the current string
       #  (which will be the implicit input in the first iteration)
  R    #  Reverse the top copy
   Ê   #  Pop the top two, and check whether they're NOT equal
    #  #  If this is truthy (it's not a palindrome): stop the infinite loop
  2ä   #  Split the string into two equal-sized halves
       #  (if the length is odd, the first string is one char longer)
    н  #  Pop and keep just the first item
}N     # After the infinite loop: push the (last) 0-based loop-index
       # (after which it is output implicitly as result)

Uses the legacy version, because pushing N outside of a loop will result in 0 in the new version of 05AB1E.

\$\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.