Have you heard of tralindromes?

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)


non-tralindromes:

xy
coc
faff
xyzzy
mummy
random
hotshot
tralindrome
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.

• @thejonymyster Thanks. Certainly they should appear in that order. Hopefully the new rule 2 makes it clearer. Jul 27 at 0:58
• @Deadcode Seems to depend on the approach (or maybe the language features). I see at least two answers that do special-case 1-char strings, and at least two that do not. By rule 2, strings of length 3k+1 require both XY and YZ to overlap by exactly 1 char, and to me XYZ overlapping when k=0 is a natural consequence of the rules. Jul 27 at 4:00
• Suggested test case: abccbacbaabcabc. My regex matches this if shortened to 45 bytes. Jul 27 at 6:13
• up next: "For which n is it an nlindrome?" Jul 27 at 13:20
• Suggested test case: dadadadadadada – I found a 51 byte Java/Perl/PCRE/.NET regex that passes all the test cases, but misidentifies that as a tralindrome. Jul 27 at 20:48

Regex (Perl / PCRE2 / Boost / Pythonregex), 594746383733 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

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. This works in the latest version of Pythonregex, but not the one on TIO, and ATO doesn't have it installed. Regex (Ruby), 5352444339 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), 646355474642 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), 6157 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 bytes

^(.+)((.?)(?=.*?(?=(\3(?(6)\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+
Try it 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.

The old version of the Python mrab-regex module on TIO experiences at least two bugs with this. One is that (?(5)\5|.?) should work, and does work on other engines, but here a workaround was needed, creating an empty \6 group and using (?(6)\5|.?). The other bug is that dadadadadadada is matched, as well as the same with any number of das appended at the end. That said, these bugs are fixed in the latest version.

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
Try it online! - .NET

This combines both the 56 Java and 61 byte Python ports, to support five different regex engines. Oddly, the (.+?) workaround is needed for Python in this version, too, even though it isn't in the 61 byte version. (This is fixed in the latest version of mrab-regex.)

Perl, 4945 44 bytes

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


Try it online!

Ruby, 5147 46 bytes

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


Try it online!

$args-match'^(.?(.)*.?)(?<-2>\2)*(?(2)^)\1$|^.$'  Try it online! Julia v1.2+ 5450 49 bytes s->endswith(s,r"^((.+)((.)(?3)\4|(?=\2$).?))?.?")


Attempt This Online!

R, 5853 52 bytes

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


Attempt This Online!

PHP, 6460 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


Can't Try it online! - the version on TIO is old and buggy

Python (with regex), 72 bytes

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


Can't Try it online! - the version on TIO is old and buggy

(If it must be a pure lambda.)

Java, 85 75 bytes

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


Try it online!

$_=/^((.+)((.)(?3)\4|(?=\2$).?))?.?$/  Try it online! Ruby-n, 4743 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, 6359 58 bytes <?=preg_match('/^((.+)((.)(?3)\4|(?=\2$).?))?.?$/',$argn);


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

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.
• This seems to work? Jul 27 at 5:10

JavaScript (Node.js), 60 bytes

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


Try it online!

• Jul 27 at 9:35

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

• -n+~n is just ~n-n for -1 byte. Jul 27 at 2:09
• Thanks @Steffan. Unfortunately, I just noticed that my logic misses one edge case, so I'll have to fix that first. Jul 27 at 2:15
• I'm curious, would your code be shorter or longer if 1-character strings were not tralindromes? I can see @alephalpha's would be shorter. Jul 27 at 3:59
• @Deadcode probably longer since I would have to catch that as a special case. I take it alephalpha has to do extra wok because copy 1 and copy 3 of the repeated bit overlap? My code independently cuts everything from the full string, so n=1 is not special. Jul 27 at 4:34

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.

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.

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

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.

• Congratulations on the shortest regex so far. Do you mind if I adopt this into my post, giving you credit of course? Jul 27 at 8:10
• @Deadcode As long as you don't remove your own .NET solution.
– Neil
Jul 27 at 8:31
• I really didn't expect it to happen, but Perl/PCRE2/Boost has overtaken .NET again. By 2 bytes. Jul 27 at 21:49
• @Deadcode Well for regular palindromes, I think recursive regex is somewhat golfier than balancing groups, so I can't say I'm surprised.
– Neil
Jul 27 at 22:09

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


05AB1E, 15 bytes

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


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)


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.

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.
• A port using a regex from @Deadcode's answer would definitely be shorter. Jul 27 at 11:45
• True, and I added one (obligatory) but it's still nice seeing an original solution. I'd also be curious if a port of one of the other solutions to R could beat your current one. And of course an explanation would be nice. Jul 27 at 15:48

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!

• 305 bytes (footer stripped because it made link too long) Jul 27 at 1:39