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

Question

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

Answer 1

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.

Answer 2

GolfScript, 25 chars

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

Answer 3

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

Answer 4

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.

Answer 5

Haskell, 48 characters

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

Answer 6

Brachylog, 8 bytes

aa₁ᶠc?ẹṀ

Try it online!

Takes input through the input variable and outputs through success or failure. I don't quite get why length-zero and length-one initial heads have to have the same output as the very straightforwardly illegal "xx", but fortunately ruling them out only takes two bytes.

    c       The concatenation of
   ᶠ        every
 a₁         suffix (in descending order of length) of
a           some adfix of the input
     ?      is the input,
      ẹṀ    which has multiple elements.

Instead of using a sane algorithm to walk backwards through the input and match each repetition, or determine the initial head from the length of the input then generate the rest and check for equality, this brute-forces the initial head from the set of all adfixes of the input (not just prefixes, because that would be a byte longer).

Answer 7

VBA, 113 characters

Adding my 2 VBA cents...

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

Answer 8

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)

Answer 9

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");}

Answer 10

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.

Answer 11

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

Answer 12

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"

Answer 13

C (gcc), 80 bytes

i,j,k,l;f(b,e)char*b;{for(i=j=k=e<2;e--;k|=l?i-=++j:b[e]-b[j+e])l=++i>j;b=!k*l;}

Try it online!

Rejects "x" and "". -1 if "x" can be accepted, and another -1 if "" is ok as well.

Answer 14

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;
}