4
\$\begingroup\$

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

\$\endgroup\$
3
  • 5
    \$\begingroup\$ Surely x should be accepted? The first string is x; the second is the empty string, so end iteration. \$\endgroup\$ Dec 30, 2011 at 12:29
  • \$\begingroup\$ you may be right about this, I would be interested to see someone formalize it \$\endgroup\$ Dec 30, 2011 at 13:43
  • 7
    \$\begingroup\$ 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. \$\endgroup\$ Dec 31, 2011 at 11:30

14 Answers 14

5
\$\begingroup\$

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.

\$\endgroup\$
10
  • \$\begingroup\$ very insightful \$\endgroup\$ Dec 30, 2011 at 11:30
  • \$\begingroup\$ I don't think you need the 0 on 0.5 \$\endgroup\$
    – gnibbler
    Dec 30, 2011 at 12:26
  • \$\begingroup\$ You can also use int((2*len(t))**0.5) which save quite some chars. \$\endgroup\$
    – Howard
    Dec 30, 2011 at 13:49
  • \$\begingroup\$ Or int(len(t+t)**.5) which is even shorter. \$\endgroup\$
    – Howard
    Dec 30, 2011 at 14:05
  • \$\begingroup\$ But unfortunately you have to add another check: "" and "x" yield true in your implementation. \$\endgroup\$
    – Howard
    Dec 30, 2011 at 14:17
4
\$\begingroup\$

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

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Going to have lo learn golfscript now :) \$\endgroup\$ Jan 1, 2012 at 1:30
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ 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. \$\endgroup\$ Dec 30, 2011 at 10:50
  • \$\begingroup\$ Ah, I was too fast with my upvote. Although it is a great approach also this regex fails on input like aaaaa. \$\endgroup\$
    – Howard
    Dec 30, 2011 at 11:29
  • 1
    \$\begingroup\$ @Howard fixed. At a huge cost. :( \$\endgroup\$
    – J B
    Dec 31, 2011 at 0:37
3
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
1
  • \$\begingroup\$ I doubt this will be beaten \$\endgroup\$ Jun 17, 2019 at 13:43
2
\$\begingroup\$

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

\$\endgroup\$
1
  • \$\begingroup\$ You can get this down to 97 bytes as Function t(s) k=Right(s,Len(s)-1) t=Len(k)\2 If t*(Left(k,t)<>Right(k,t))Then t=t(k) End Function \$\endgroup\$ Jun 20, 2019 at 14:21
2
\$\begingroup\$

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)
\$\endgroup\$
2
\$\begingroup\$

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");}
\$\endgroup\$
1
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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) }
\$\endgroup\$
1
\$\begingroup\$

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"
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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