Have you heard of tralindromes?

Question

I haven't. :P So I decided to define one:

A tralindrome is a string which contains three equal-length sections X, Y, Z such that

• all characters in the string are included in at least one of the three sections,
• X starts at the first character, Y starts at or right after the last character of X, and Z starts at or right after the last character of Y:

  abcdefgh  or  abcdefgh
  XXX           XXX
    YYY            YYY
       ZZZ           ZZZ
  

• and X is equal to the reverse of Y, and Y is equal to the reverse of Z.

Some examples of tralindromes:

a       (a / a / a)
bb      (b / b / b) - note that there are two possible choices for Y
ccc     (c / c / c)
coco    (co / oc / co)
mamma   (ma / am / ma)
uhhuh   (uh / hu / uh)
xyyxxy  (xy / yx / xy)
banaban    (ban / nab / ban)
dottodot   (dot / tod / dot)
dadadadada (dada / adad / dada)

non-tralindromes:

xy
coc
faff
xyzzy
mummy
random
hotshot
tralindrome
dadadadadada
aabaabaaaabaa
abccbacbaabcabc

Given a nonempty string that entirely consists of lowercase letters, determine if it is a tralindrome.

For output, you can choose to

• output truthy/falsy using your language's convention (swapping is allowed), or
• use two distinct, fixed values to represent true (affirmative) or false (negative) respectively.

Shortest code in bytes wins.

Answer 1

Regex (Perl / PCRE2 / Boost / Python^regex), 59 47 46 38 37 33 32 bytes

^((.+)((.)(?3)\4|(?=\2$).?))?.?$

Try it online! - Perl v5.28.2 / Attempt This Online! - Perl v5.36+
Try it online! - PCRE2 v10.33 / Attempt This Online! - PCRE2 v10.40+
Try it online! - Boost
Attempt This Online! - Python _{^{import regex}}

This has been a special-case rollercoaster. The original versions needed |^.$ to match one-character strings – and then two 38 byte versions suddenly didn't need that anymore, and just naturally matched one-character strings. And then at 37 the |^.$ was back... it stuck around during the drop to 33 bytes.

Now at 32 bytes, it's still there, but hiding. It's subsumed into the rest of the expression, at the cost of also matching an empty string (which is allowed by the challenge's rules).

The following explanation is for the 33 byte version, because it's easier to format the comments. The transformation is ^pattern.?$|^.$ → ^(pattern)?.?$, with all of pattern's capture group indices incremented by 1.

^                 # Anchor start
(.+)              # Match the longest prefix that we conjecture (but later prove)
                  # recurs as a suffix, and capture it in \1.
# Match the palindromic subsection at the end, using recursion
(                 # Define recursive subroutine (?2)
    (.)           # \3 = one character from the left side
    (?2)          # Call self recursively
    \3            # Match the same character on the right side
|           # or...
    (?=\1$)       # End the recursion. Assert that the remaining suffix exactly
                  # matches the prefix we captured.
    .?            # Optionally skip one character, which will happen if the
                  # palindromic portion is odd in length.
)
.?                # Optionally skip one character at the end. This will have been
                  # verified already by the "(?=\1$)" above, so we don't need to
                  # do so again.
$                 # Assert we've reached the end of the string.
|^.$              # Match a one-character string as a special case, since the
                  # above algorithm only works on multi-character tralindromes.

A previous 38 byte version was PCRE2-only due to use of non-atomic lookahead, but that has turned out to be unnecessary.

Regex (Ruby), 53 52 44 43 39 38 bytes

^((.+)((.)\g<3>\k<4+0>|(?=\2$).?))?.?$

Try it online!

This is the 47 46 38 37 33 32 byte regex ported to Ruby's subroutine call syntax. \k<4+0> retrieves \4 from the current level of recursion, whereas what \4 would retrieve may have been overwritten at a deeper level of recursion.

Regex (.NET), 35 bytes

^(.?(.)*.?)(?<-2>\2)*(?(2)^)\1$|^.$

Try it online!

From Neil's Retina answer; please see his post for the explanation. Beats my .NET regex by 20 12 11 7 6 bytes.

I have ported it to my style here, optimizing for the best speed at its length. Moving the special-case test to the end should make it theoretically faster to match any valid multi-character tralindrome, at the cost of being slower to match a one-character string.

Ported to PCRE2, this is 55 bytes, demonstrating that what's optimal in one regex engine isn't necessarily so in others:

^(?*((.?).*(?=(.*))(.?)))\2((.)(?5)\6|(?=\3$)\4)\1$|^.$

Attempt This Online! - PCRE2 v10.40+

Regex (_^.NET), 64 63 55 47 46 42 41 bytes

^((.+)(.)*(?=\2$).?(?<-3>\3)*(?(3)^))?.?$

Try it online!

At 55 47 46 42 41 bytes, this is now a port of the 38 37 33 32 byte Perl/PCRE2/Boost regex.

((.)(?3)\4|pattern3.?) becomes (.)*pattern3.?(?<-3>\3)*(?(3)^), using .NET's balancing groups instead of recursion to match the palindromic subsection:

(.)* - capture the left half of the palindrome, pushing it onto the \3 stack one character at a time.

.? - optionally skip one character, in the case that the palindrome is odd in length.

(?<-3>\3)* - pop every character off the \3 stack, matching them in reverse order.

(?(3)^) - assert that if the \3 stack isn't empty, then something impossible (that we're at the start of the string) is true – i.e. assert that the \3 stack is empty.

Regex (_{^{Perl /}} PCRE _{^{/ .NET}}), 61 57 51 bytes

^(.+)((.?)(?=.*?(\3(?(4)\4|.?)$)))+(?=\1$).?\4$|^.$

Try it online! - Perl v5.28.2 / Attempt This Online! - Perl v5.36+
Try it online! - PCRE1
Try it online! - PCRE2 v10.33 / Attempt This Online! - PCRE2 v10.40+
Try it online! - .NET

This is a port of the 46 38 33 byte Perl/PCRE2/Boost version, to regex engines that don't have recursion (or do have it, but not in a non-atomic form, in the case of PCRE1). To match the palindromic subsection, group-building (with a nested backreference) is used instead of recursion.

Regex (Java _{^{/ Perl / PCRE / .NET}}), 66 56 bytes

^(.+?)((.?)(?=.*?(\3(\4|(?!\6).?)$))())+(?=\1$).?\4$|^.$

Try it online! - Java 12.0.2 / Attempt This Online! - Java 18.0.1+
Try it online! - Perl v5.28.2 / Attempt This Online! - Perl v5.36+
Try it online! - PCRE1
Try it online! - PCRE2 v10.33 / Attempt This Online! - PCRE2 v10.40+
Try it online! - .NET

This is a port of the 61 51 byte Perl/PCRE/.NET version, to regex engines that don't have conditionals but do have nested backreferences.

Java seems to have some bugs in its regex engine, especially in the vein of giving up on backtracking when there are too many possibilities (and there don't even have to be all that many). To work around this, (.+?) is used instead of (.+). If Java's regex engine were really behaving well, this wouldn't be necessary.

Some other variants don't play nice in Java. For example, a port of the previous 57 byte Perl/PCRE/.NET version is 62 bytes:

^(.*)(?=(.)).?((.)(?=.*(\4(\5()|(?!\7))$)))*(?=\1\2$).?\5$|^.$

But fails in Java: Try it online! (12.0.2) / Attempt This Online! (18.0.1+)
This warrants further research.

Regex (_{^{Perl / PCRE / Pythonregex / .NET}}), 61 59 bytes

^(.+)((.?)(?=.*?(?=(\3(?(5)\5|.?)$))(\4)))+(?=\1$).?\4$|^.$

Try it online! - Perl v5.28.2 / Attempt This Online! - Perl v5.36+
Try it online! - PCRE1
Try it online! - PCRE2 v10.33 / Attempt This Online! - PCRE2 v10.40+
Attempt This Online! - Python _{^{import regex}}
Try it online! - .NET

This is a port of the 51 byte Perl/PCRE/.NET regex to engines that lack nested backreferences. To emulate them, \4 and \5 are copied back and forth to each other.

Ruby does not work with this regex at all. It just hangs.

Regex (_{^{Java / Perl / PCRE / Pythonregex / .NET}}), 64 bytes

^(.+?)((.?)(?=.*?(?=(\3(\6|(?!\7).?)$))(\4))())+(?=\1$).?\4$|^.$

Try it online! - Java 12.0.2 / Attempt This Online! - Java 18.0.1+
Try it online! - Perl v5.28.2 / Attempt This Online! - Perl v5.36+
Try it online! - PCRE1
Try it online! - PCRE2 v10.33 / Attempt This Online! - PCRE2 v10.40+
Try it online! - Python _{^{import regex}} / Attempt This Online!
Try it online! - .NET

This combines both the 56 Java and 59 byte Python ports, to support five different regex engines.

\$\large\textit{Anonymous functions}\$

Perl, 49 45 44 bytes

sub{pop=~/^((.+)((.)(?3)\4|(?=\2$).?))?.?$/}

Try it online!

Ruby, 53 49 48 bytes

->s{s=~/^((.+)((.)\g<3>\k<4+0>|(?=\2$).?))?.?$/}

Try it online!

PowerShell, 48 bytes

$args-match'^(.?(.)*.?)(?<-2>\2)*(?(2)^)\1$|^.$'

Try it online!

Julia v1.2+, 54 50 49 bytes

s->endswith(s,r"^((.+)((.)(?3)\4|(?=\2$).?))?.?")

Attempt This Online!

R, 58 53 52 bytes

\(L)grepl('^((.+)((.)(?3)\\4|(?=\\2$).?))?.?$',L,,1)

Attempt This Online!

PHP, 64 60 59 bytes

fn($s)=>preg_match('/^((.+)((.)(?3)\4|(?=\2$).?))?.?$/',$s)

Try it online!

Python (with regex), 71 bytes

lambda s:regex.match(r'((.+)((.)(?3)\4|(?=\2$).?))?.?$',s);import regex

Attempt This Online!

Python (with regex), 72 bytes

lambda s:__import__('regex').match(r'((.+)((.)(?3)\4|(?=\2$).?))?.?$',s)

Attempt This Online!

(If it must be a pure lambda.)

Java, 85 75 bytes

s->s.matches("((.+?)((.?)(?=.*?(\\4(\\5|(?!\\7).?)$))())+(?=\\2$).?\\5)|.")

Try it online!

\$\large\textit{Full programs}\$

Perl -p, 42 38 37 bytes

$_=/^((.+)((.)(?3)\4|(?=\2$).?))?.?$/

Try it online!

Ruby -n, 47 43 42 bytes

p~/^((.+)((.)\g<3>\k<4+0>|(?=\2$).?))?.?$/

Try it online!

Prints nil for false and 0 for true, which are respectively falsey and truthy in Ruby. If printing 0 or 1 is desired, replace p~ with p !! (+2 bytes).

PHP -F, 63 59 58 bytes

<?=preg_match('/^((.+)((.)(?3)\4|(?=\2$).?))?.?$/',$argn);

Try it online! - bare-bones test harness
Try it online! - fancier test harness

Answer 2

Curry (PAKCS), 38 bytes

-14 bytes thanks to @Bubbler.

g a=a?tail a
f(a++g(reverse a)++g a)=1

Try it online!

---

Curry (PAKCS), 52 bytes

f([_]?(a++reverse(g a)++a))=1
g(a?(a++[_]))=a?tail a

Try it online!

Returns 1 for truth, and nothing otherwise.

How?

Returns 1 when the input is either:

• a single character, or
• in the form a ++ reverse b ++ a, where b is one of the following:
  • a,
  • removing the first character from a,
  • removing the last character from a,
  • removing the first and the last characters from a.

Answer 3

JavaScript (Node.js), 60 bytes

s=>[...s,l=r=''].some(t=>s.match(`^${l+=t}?${r=t+r}?${l}$`))

Try it online!

Answer 4

Python, 72 bytes

lambda s:1>s.find(s[(l:=len(s))//-3:])<=s.find(s[-~-l//3-1::-1])<=l%3//2

Attempt This Online!

Previous Python, 74 bytes

lambda s:s.find(u:=s[(l:=len(s))//-3:])<1>=s[l//3:l-l//3].find(u[::-1])>=0

Attempt This Online!

Previous Python, 88 bytes

lambda s:{s[~(n:=len(s)//-3)::-1]}&{s[:n-1:-1]}&{s[n-~n:~n-n],s[-n:n],s[~n:n],s[-n:-~n]}

Attempt This Online!

Returns the middle copy of the "template" as a singleton set (which is truthy in Python) or the empty set (falsy in Python).

Previous Python, 90 bytes (-1 @Steffan)

lambda s:s[~(n:=len(s)//-3)::-1]in(s[n:]==s[:-n])*[s[n-~n:~n-n],s[-n:n],s[~n:n],s[-n:-~n]]

Attempt This Online!

Sort of similar to @alephalpha's logic now.

Previous wrong Python, 85 bytes

lambda s:s[~(n:=len(s)//-3)::-1]in(s[n:]==s[:-n])*(s[2*n:n],s[-n:-2*n],s[n-~n:-n+~n])

Attempt This Online!

Fails on aabaabaaaabaa (false positive).

Answer 5

Python 3.8 (pre-release), 61 bytes

lambda s:s[1:~(m:=-len(s)//3)]in s[m-1:~m:-1]in s[:-m]==s[m:]

Try it online!

• If the full string S has length \$L\$, then the length \$l\$ of each of the three sections is \$\lceil\frac{L}{3}\rceil \$; \$m = \lfloor\frac{-L}{3}\rfloor = -\lceil\frac{L}{3}\rceil = -l\$.
• The sections X and Z are extracted as s[:-m] and s[m:]; they must be equal.
• The remainder of the string, reversed, which is s[m-1:~m:-1], must be X with the first and last characters each possibly removed. This is equivalent to it being a substring of X and a superstring of (X with the first and last characters removed).
  (There is a subtlety to why this equivalence is true.
  The generalisation to removing up to \$k\$ characters from each end is false: for X=dedent and \$k=2\$, ded is a substring of X and a superstring of the central part de, but cannot be obtained from X by removing up to 2 characters from each end.
  However, the original equivalence (which is the \$k=1\$ case) is true. If the length is reduced by 2, that is the same as the central part's length, so it can only be a superstring of the central part if it is equal. If the length is reduced by 1 or 0, then for it to be a substring of X, it can only be X with one end possibly removed.)
• Chaining of comparisons is used to check all those conditions together concisely.
• The \$L=1\$ case is a bit different, but it works out because negative-length slices produce empty strings in Python.

Answer 6

J, 31 bytes

<e.[:;&.>@,(<{@;g@|.,g=.<@;}.)\

Try it online!

Inspired by alephalpha's Curry answer, and Bubbler's edit.

It's a bit ugly mechanically, but I like the simplicity of the idea.

For each prefix, we create the Cartesian product of:

1. [prefix]
2. [prefix reversed, tail of prefix reversed]
3. [prefix, tail of prefix]

And then check if the input is equal to any of the elements of any of the Cartesian products.

Answer 7

lin, 69 bytes

.+.#a $`.a len `t1+ `t \; `|
.+ `rev \`_`.' ,.a"^%s?%s?%1$s$".@ sf ?t

Try it here! Switched to an approach inspired by @tsh because previous approach - although interesting - sucked at handling the edge cases.

For testing purposes:

"mamma" ; outln
.+.#a $`.a len `t1+ `t \; `|
.+ `rev \`_`.' ,.a"^%s?%s?%1$s$".@ sf ?t

Explanation

Prettified code:

.+.#a $` .a len `t 1+ `t \; `|
.+ `rev \`_`.' , .a "^%s?%s?%1$s$".@ sf ?t

• .+.#a store input as a
• $` .a len `t 1+ `t generate prefixes
• \; `| check if any are true...
  • .+ `rev duplicate prefix, reverse
  • \`_`.' convert to string
  • , pair
  • "^%s?%s?%1$s$".@ sf turn into regex (templated as x, y, x)
  • .a ... ?t check if regex matches

Answer 8

Retina 0.8.2, 35 bytes

^.$|^(.?(.)*.?)(?<-2>\2)*(?(2)^)\1$

Try it online! Link includes test cases. Explanation: Port of @alephalpha's Curry explanation.

^.$|

Match a single character, or...

^(.?(.)*.?)

... a leading substring, capturing a substring of that which optionally skips the first and/or last characters, ...

(?<-2>\2)*(?(2)^)

... the inner substring in reverse, ...

\1$

... and the leading substring again.

Answer 9

Brachylog, 20 19 bytes

~cṪ{|~k}ʰ{|~b}ᵗ↺↔ʰ=

Try it online!

Explanation

~cṪ                   Deconcatenate the input into 3 strings
   {|~k}ʰ             Do nothing, or add an unknown trailing char to the first string
         {|~b}ᵗ       Do nothing, or add an unknown leading char to the last string
               ↺↔ʰ    Reverse the middle string
                   =  The 3 strings must be equal

Answer 10

05AB1E, 15 bytes

ηεºyû‚yy¦‚δ«}Qà

Try it online or verify all test cases.

Explanation:

η         # Get the prefixes of the (implicit) input-string
 ε        # Map over each prefix:
     ‚    #  Push a pair of:
  º       #   The mirrored version of the prefix
   yû     #   And the palindromized version of the prefix
          #    e.g. "abc" → ["abccba","abcba"]
     ‚    #  Push another pair of:
  y       #   The prefix
   y¦     #   And the prefix minus its first character
          #    e.g. "abc" → ["abc","bc"]
      δ   #  Apply double-vectorized over the two pairs:
       «  #   Append
          #    → [["abccbaabc","abccbabc"],["abcbaabc","abcbabc"]]
 }        # Close the map
  Q       # Check if any inner-most string is equal to the (implicit) input
   à      # Check if any is truthy by taking the flattened maximum
          # (which is output implicitly as result)

Answer 11

Charcoal, 32 bytes

⊙θ⊙Ｅ⊕κ⮌✂θμ⊕κ¹Φ²∧⁼…θ⁺μξλΦ²⁼λ✂θ⁺κρ

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - for a tralindrome, nothing if not. Explanation: Brute-force search for a substring whose reverse equals its possibly overlapping prefix and suffix.

 θ                                  Input string
⊙                                   Any index satisfies
     κ                              Current index
    ⊕                               Incremented
   Ｅ                                Map over implicit range
        θ                           Input string
       ✂    ¹                       Sliced from
         μ                          Inner index to
           κ                        Outer index
          ⊕                         Incremented
      ⮌                             Reversed
  ⊙                                 Any reversed substring satisfies
              ²                     Literal integer `2`
             Φ                      Filter over implicit range
                  θ                 Input string
                 …                  Truncated to length
                    μ               Inner index
                   ⁺                Plus
                     ξ              Optional overlap
                ⁼                   Equals
                      λ             Reversed substring
               ∧                    Logical And
                        ²           Literal integer `2`
                       Φ            Filter over implicit range
                          λ         Reversed substring
                         ⁼          Equals
                            θ       Input string
                           ✂        Sliced from
                              κ     Outer index
                             ⁺      Plus
                               ρ    Optional overlap
                                    Implicitly print

The final optional overlap is added rather than subtracted because the outer index is actually that of the last character in the substring (which is why it is incremented when the substring is actually extracted). Filter is used instead of Any in the inner loops because it accepts an implicit range and Any does not.

Answer 12

R, 96 86 bytes

\(x,l=sum(x|1),t=l%%3>0,`!`=\(y)any(y-x[1:h]))!tail(x,h<-l%/%3+t)|!x[q<-h:1+h]&!x[q-t]

Attempt This Online!

Pretty naive implementation, with some optimizations to make the code shorter (and unreadable).

Takes input as a vector of character codes. Outputs FALSE for tralindromes and TRUE otherwise.

Explanation outline:

1. Let l be the length of input vector x.
2. Compute h - the length of the tralindrome parts. It's \$\lfloor\frac{l}{3}\rfloor+t\$, where t is 0 for l divisible by 3 and 1 otherwise.
3. Prepare a helper function !, which compares its input with first h elements of x (denote them with X as in the question).
4. Then last h characters must be equal to X.
5. And one of the following must be equal to X:
   1. characters from h+1 to 2*h, reversed
   2. characters from h+1-t to 2*h-t, reversed.

Answer 13

Python3, 305 bytes:

lambda s:any(all({*s}-{*k}for k in j)^1and K(s,j)and j[0]==j[1][::-1]==j[2]for i in R(1,L(s)+1)for j in C(s,i))
R=range
L=len
K=lambda s,l:not(l or s)or l and s[:(T:=L(l[0]))]==l[0]and any(K(s[T-i:],l[1:])for i in[0,1])
C=lambda s,n,l=[]:L(l)==3and[l]or[j for x in R(L(s)-n+1)for j in C(s,n,l+[s[x:x+n]])]

Try it online!

Answer 14

Nekomata + -e, 11 bytes

p::↔ᵃᶜt$,,=

Attempt This Online!

A port of my Curry answer (based on @Bubbler's comment).

p::↔ᵃᶜt$,,=
p               Find a prefix of the input
 ::             Triplicate it
   ↔            Reverse the third copy
    ᵃᶜt         Optionally drop the first character of the second and third copies
       $        Swap the second and third copies
        ,,      Join three copies together
          =     Check if the result is equal to the input