Recursive palindromes

Question

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

Suggested test case: xyxxxyx, It's a palindrome and its halves contain non-trivial palindromes but are not actually palindromes themselves. — Wheat Wizard, Jan 19 at 9:36
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. — Greg Martin, Jan 20 at 5:32
@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. — AnttiP, Jan 20 at 5:45

Surculose Sputum · Accepted Answer · 2022-01-19 06:25:21Z

7

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).

answered Jan 19 at 6:25

Surculose Sputum

8,2431 gold badge10 silver badges40 bronze badges

\$\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\$
– Surculose Sputum
Jan 19 at 20:51

Add a comment |

Nitrodon · Accepted Answer · 2022-01-19 06:26:11Z

4

Vyxal, 8 bytes

‡Ḃ=‡½hŀL

Try it Online!

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

       L # Get length

answered Jan 19 at 6:26

Nitrodon

10.5k2 gold badges16 silver badges32 bronze badges

Add a comment |

Razetime · Accepted Answer · 2022-01-19 06:38:50Z

4

Husk, 9 bytes

←VS≠↔¡o←½

Try it online!

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

edited Jan 19 at 6:38

answered Jan 19 at 6:23

Razetime

25.1k3 gold badges20 silver badges70 bronze badges

Add a comment |

Jonathan Allan · Accepted Answer · 2022-01-19 13:33:19Z

3

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

edited Jan 19 at 13:33

answered Jan 19 at 13:27

Jonathan Allan

90.8k7 gold badges60 silver badges250 bronze badges

Add a comment |

DLosc · Accepted Answer · 2022-01-21 17:23:47Z

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

pajonk · Accepted Answer · 2022-01-19 08:34:34Z

2

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

answered Jan 19 at 8:34

pajonk

10.7k2 gold badges16 silver badges56 bronze badges

Add a comment |

Kevin Cruijssen · Accepted Answer · 2022-01-19 09:54:06Z

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

DLosc · Accepted Answer · 2022-01-20 21:23:50Z

2

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

edited Jan 20 at 21:23

answered Jan 19 at 19:44

DLosc

31.8k4 gold badges53 silver badges119 bronze badges

2

\$\begingroup\$ If you're willing to let eventual labeling do some of the work, +₁ can be golfed to < \$\endgroup\$
– Unrelated String
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\$
– Unrelated String
Jan 21 at 0:28

Add a comment |

Madison Silver · Accepted Answer · 2022-01-19 06:30:08Z

1

Haskell, 51 bytes

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

Try it Online!

answered Jan 19 at 6:30

Madison Silver

6493 silver badges5 bronze badges

Add a comment |

Neil · Accepted Answer · 2022-01-19 07:33:19Z

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.

Neil · Accepted Answer · 2022-01-19 07:42:13Z

1

Charcoal, 20 bytes

Ｗ⁼θ⮌θ«≔∕⁺θψ²θ⊞υω»ＩＬυ

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

Ｗ⁼θ⮌θ«

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.

»ＩＬυ

Output the final number of loops.

answered Jan 19 at 7:42

Neil

142k10 gold badges64 silver badges248 bronze badges

Add a comment |

ophact · Accepted Answer · 2022-01-19 08:46:09Z

1

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.

answered Jan 19 at 8:46

ophact

2,6591 gold badge2 silver badges22 bronze badges

Add a comment |

Kevin Cruijssen · Accepted Answer · 2022-01-19 09:44:03Z

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.

Stack Exchange Network

current community

your communities

more stack exchange communities

Recursive palindromes

Examples

13 Answers 13

Python 2, 41 bytes

Vyxal, 8 bytes

Husk, 9 bytes

Jelly, 10 bytes

How?

BQN, 21 bytes

Explanation

R, 61 bytes

Java 8, 101 bytes

Brachylog, 10 9 bytes

Explanation

Haskell, 51 bytes

Retina 0.8.2, 36 bytes

Charcoal, 20 bytes

JavaScript (Node.js), 57 bytes

05AB1E (legacy), 10 bytes

Your Answer

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

Linked

Hot Network Questions

Recursive palindromes

Examples

13 Answers 13

Python 2, 41 bytes

Vyxal, 8 bytes

Husk, 9 bytes

Jelly, 10 bytes

How?

BQN, 21 bytes

Explanation

R, 61 bytes

Java 8, 101 bytes

Brachylog, 10 9 bytes

Explanation

Haskell, 51 bytes

Retina 0.8.2, 36 bytes

Charcoal, 20 bytes

JavaScript (Node.js), 57 bytes

05AB1E (legacy), 10 bytes

Your Answer

Sign up or log in

Post as a guest

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

Linked

Related

Hot Network Questions