# Write the shortest code to match a tail-repeating string where one character falls off the head in each repetition

In this code-golf, you will attempt to match a string that is tail-repeating with one character falling off the head on each iteration. The code needs to be able to accept a string, and return to the user whether the string meets the above criteria.

Examples:

"", "x", and "xx" -> False


EDIT: There is some speculation about whether this is theoretically correct. I will accept any implementation that returns the same value for the three above values as of now. However I do not have an official position on whether this is true or false. Hopefully someone can formalize this.

The above cases will always be false regardless of the circumstance because the string is too short to have the property of tail repetition with one character falling off the head. For example "xx"'s first "tail" would be "x" and there is nothing after the "xx", so it would be false. The character does not matter here, "x" is an example.

"abb" -> True


"abb" is the simplest string I can think of that should be true, because if you take what we will call the "tail" off of it, you get "bb", then knock one character off the head, and you get "b", which is the next character in the string.

"abcbcc" -> True


"abcbcc" is the next simplest string I can think of that should be true. So far in contemplating this problem, testing the truth from the beginning to the end of the string seems difficult, so I'll explain from the end up.

"c", "cb", "cba"


When you examine the string in reverse it seems easier to determine where the "first tail" ends. It ends at the first "c" in "abc", but this can only be inferred from examining the string in reverse, to the best of my knowledge so far.

Here is an example of a string that does not match:

"abcbca" -> False


If we try to apply the above reverse-proof method to it:

"a", "cb"


we realize at the second step when the first character in the second string is not "a", that this must be false.

Shortest code in characters to implement this logic in any programming language wins.

EDIT: If you find a solution other than the suggested one, it is still a valid entry (and very cool!)

• Surely x should be accepted? The first string is x; the second is the empty string, so end iteration. – Peter Taylor Dec 30 '11 at 12:29
• you may be right about this, I would be interested to see someone formalize it – Thomas Dignan Dec 30 '11 at 13:43
• Assume we have defined an alphabet. Let e denote the empty word, a denote a letter in the alphabet, and w denote a word over the alphabet. Define a function f from words of the alphabet to words of the alphabet recursively as f(e) = e and f(aw) = aw f(w). Define the language L over the alphabet as the set of words l for which there exists a word w such that l = f(w). The language you're asking us to accept is the words in L of length at least two, but that's an arbitrary additional constraint. – Peter Taylor Dec 31 '11 at 11:30

.,,{1$<..,{(;.@\+\}*;}%?)  NB This requires the most recent version of Golfscript, which supports a string array ? indexof function. This implements the interpretation whereby "" and "x" are not in the language, which IMO is a funny way to define it. It is a statement which takes one argument on the stack and leaves an integer which can be interpreted as a boolean in standard GolfScript fashion (i.e. 0 for false, anything else for true). To turn this into a full program prepend n- and postpend some suitable manipulation depending on what output you want (e.g. "true""false"if). • Going to have lo learn golfscript now :) – Thomas Dignan Jan 1 '12 at 1:30 # Python Used the fact that the length of a valid string will always be a Triangle Number. t=raw_input() x=int(len(t+t)**.5) print t==''.join(t[i:x]for i in range(x))  A Ruby solution might be shorter, will post soon. • very insightful – Thomas Dignan Dec 30 '11 at 11:30 • I don't think you need the 0 on 0.5 – gnibbler Dec 30 '11 at 12:26 • You can also use int((2*len(t))**0.5) which save quite some chars. – Howard Dec 30 '11 at 13:49 • Or int(len(t+t)**.5) which is even shorter. – Howard Dec 30 '11 at 14:05 • But unfortunately you have to add another check: "" and "x" yield true in your implementation. – Howard Dec 30 '11 at 14:17 ## Ruby, 63 characters t=->x{b="";x.size>1&&(b,x=$2+b,$1while x=~/(.*)(.)#{b}/;x=="")}  This method returns true iff the string fits the definition. Usage: p t["abcbbc"] # -> false p t["abcbcc"] # -> true  # Perl regex, 24 69 ^.(.+)(?{$a=$+})((??{"\Q$a"})(?{$a=substr$a,1}))*(?(?{''eq$a})$|(*F))


Obviously not a genuine CS regular expression, but those modern recursive regexes can work wonders and the edited (but fixed) version is not that short at all. I'm starting to wonder if actual Perl code, with the ability to reverse the starting string, wouldn't be shorter than that.

• wonderful, I initially thought of this problem while practicing regex but could not grasp how to do it yet. I'm in the middle of reading mastering regex 3rd ed. – Thomas Dignan Dec 30 '11 at 10:50
• Ah, I was too fast with my upvote. Although it is a great approach also this regex fails on input like aaaaa. – Howard Dec 30 '11 at 11:29
• @Howard fixed. At a huge cost. :( – J B Dec 31 '11 at 0:37

import List
f x=any((==x).concat.tails)$inits x  Brute force. Note that this returns true for f "x" and f "". Example usage in GHCi: > f "abb" True > f "abcbcc" True > f "abcbca" False  # C, 191 bytes That's the best I can golf this in C: main(){char a[9],*b=a,p[9],c=0,i=strlen(gets(a)),j=0,k=0;p[0]='\0';while(i>=0){b[strlen(b=a+(i-=++j))-k]='\0';k=strlen(b);if(strcmp(p,b+1)&&c++)exit(puts("false"));strcpy(p,b);}puts("true");}  # Element, 40 characters _)#3:s;m;$'[m~)#4:m;$'[(#2:'."]#s~=[1]]  This is a language of my own creation. It is designed so that all operators are one character long and always perform the same function. This allows the programs to be much shorter than many other programming languages. In some challenges, however, I must program something for which there is no built-in function, causing the program to grow in size. Element has no built-in regex matching of any kind, so I think that I actually did pretty well on this challenge. This is a complete program that will take one line of input as the string to test, and it will print a 1 for true and nothing for false. As for why I am answering code golf questions in Element, it is partially to raise awareness, partially a publicity stunt, and partially an exercise to test the language. A description of Element can be found here, and the (hopefully working) source of an interpreter for Element (written in Perl) can be found here. ## Scala 113: def t(s:String):Boolean={ val k=s.tail val l=k.size if(l<2)false else if(k.take(l/2)==k.drop(l/2))true else t(k)}  Takes rekursively the rest of the string, and tests whether first half equals second. ungolfed: def tailrepeating (s: String): Boolean = { val k=s.tail if (k.size < 2) false else if (k.take (k.size /2) == k.drop (k.size / 2)) true else tailrepeating (k) }  ## bash 111 #!/bin/bash s=$1
l=${#s} for i in$(seq 1 $((l-2))) do test "${s:i:$(((l-i)/2))}" = "${s:\$(((l+i)/2))}"&&exit 0
done||false


111 chars without shebang. Invocation:

./tailrepeated.sh foobalaa && echo "true" || echo "false"


## VBA, 113 characters

Function t(s)
k=Right(s,Len(s)-1)
t=Round(Len(k)/2)
If t>0 Then If Left(k,t)<>Right(k,t) Then t=t(k)
End Function


This returns a 1 or 0.

Usage is MsgBox t("abcbcc"), or to get a "True"/"False" outsput, use MsgBox CBool(t("abcbcc"))

Here is my own un-golfed answer in C for testing.

#include <stdio.h>
#include <string.h>
#include <assert.h>

int tailrep(char *str, char *sub, int sublen, int len) {
if (str == sub) {
return 1;
}

int i;
for (i = 0; i < sublen; i++) {
char *a,  *b;
a = str + len - sublen;
b = sub + sublen - 1;

//        printf("%p->%c %p->%c\n", a - i, a[-i], b - i, b[-i]);
if (a[-i] != b[-i]) {
return 0;
}
}

return tailrep(str, sub - sublen - 1, sublen + 1, len - sublen);
}

int istailrep(char *str) {
int len = strlen(str);
if (len < 3) {
return 0;
}
return tailrep(str, str + len - 1, 1, len - 1);
}

int main() {
// must be false
assert(!istailrep(""));
assert(!istailrep("a"));
assert(!istailrep("aa"));
assert(!istailrep("aab"));
assert(!istailrep("abcbbc"));
assert(!istailrep("abcdabcdabcd"));

// must be true
assert(istailrep("aaa"));
assert(istailrep("abb"));
assert(istailrep("abcbcc"));
assert(istailrep("abcdbcdcdd"));
assert(istailrep("abcdebcdecdedee"));
printf("yay\n");
return 0;
}


# Pyth, 33 22 bytes

This is my second attempt on Pyth :)

qz_jk.__<z/t@+1*8lz2 2
print(
q                       is_equal(
z                       input(),
_                       reverse(
jk                      concat(
._                     all_prefixes(
_                     reverse(
<z                    input()[:
/t@h*8lz2 2          divide(decrement(root(increment(multiply(8,len(z))),2)),2)
])))))


Previous attempt:

KJ<z/t@+1*8lz2 2;WnkJ=K+K=JtJ;qKz


Try it online!

How it works:

KJ<z/t@+1*8lz2 2;WnkJ=K+K=JtJ;qKz
z=input()
KJ<z/t@+1*8lz2 2                    K=J=z[:(root(1+8*len(z),2)-1)/2]
<z                                    z[:
+1*8lz                                    1+8*len(z)
@      2                              root(          ,2)
t                                                        -1
WnKJ               while not_equal(k,J):
=K+K=JtJ        K=plus(K,J=tail(J))
qKz   equal(K,z)
`