String.prototype.isRepeated

Question

UPDATE : isaacg's Pyth submission is the winner!

---

Many of you must have heard that there is a cooler version of JavaScript in town (read ES6) which has a method String.prototype.repeat so that you can do

"Hello, World!".repeat(3)

and get

"Hello, World!Hello, World!Hello, World!"

as the output.

Your job is to write a function or a program in a language of your choice which detects if a string has been gone under such transformation.

i.e. The input string can be represented as an exact n times repetition of a smaller string. The output (as function's return statement or STDOUT) should be truthy if the string can be or falsy if the string cannot be represented as a repetition of smaller string.

Some sample input:

"asdfasdfasdf"  // true
"asdfasdfa"     // false
"ĴĴĴĴĴĴĴĴĴ"     // true
"ĴĴĴ123ĴĴĴ123"  // true
"abcdefgh"      // false

Note that the last input is false, thus n should be greater than 1

Complete rules

• Write a function/program in any language to input (via function argument/command line args/STDIN) a string
• Return/Print truthy value if the given string is formed via an exact repetition of a smaller string, repeating at least twice.
• Maximum size of the input string is ideally Infinity
• String can have all possible ASCII characters
• This is a code-golf so smallest code in characters wins.

Answer 1

Python (24)

lambda s:s in(s+s)[1:-1]

Checks if the string is a substring of itself concatenated twice, eliminating the first and last characters to avoid trivial matches. If it is, it must be a nontrivial cyclic permutation of itself, and thus the sum of repeated segments.

Answer 2

Regex (ECMAScript flavour), 11 bytes

Sounds like a job for regex!

^([^]+)\1+$

Test it here.

I've chosen ECMAScript, because it's the only flavour (I know) in which [^] matches any character. In all others, I'd either need a flag to change the behaviour of . or use [\s\S] which is three characters longer.

Depending on how we're counting the flag, that could of course be a byte shorter. E.g. if we're counting pattern + flags (e.g. ignoring delimiters), the PCRE/Perl equivalent would be

/^(.+)\1+$/s

Which is 10 bytes, ignoring the delimiters.

Test it here.

This matches only strings which consist of at least two repetitions of some substring.

Here is a full 26-byte ES6 function, but I maintain that regular expression submissions are generally valid:

f=s->/^([^]+)\1+$/.test(s)

Answer 3

Pyth, 9

/:+zz1_1z

Or

}z:+zz1_1

These are both close translations of @xnor's python answer, except that they take input from STDIN and print it. The first is equivalent to:

z = input()
print((z+z)[1:-1].count(z))

0 for False, 1 for True.

The second line is equivalent to:

z = input()
print(z in (z+z)[1:-1])

False for False, True for True.

Pyth's official compiler had a bug related to the second one, which I just patched, so the first is my official submission.

Answer 4

CJam, 9

q__+)@+#)

Similar to xnor's idea.

q      " Read input. ";
__+    " Duplicate twice and concatenate them together. ";
)      " Remove the last character of the longer string. ";
@+     " Insert that character at the beginning of the shorter string. ";
#)     " Find the shorter string in the longer string, and increase by one. ";

Answer 5

APL, 11

2<+/x⍷,⍨x←⍞

Explanation
⍞ takes string input from screen
x← assigns to variable x
,⍨ concatenates the string with itself
x⍷ searches for x in the resulting string. Returns an array consisting of 1's in the starting position of a match and 0's elsewhere.
+/ sums the array
2< check if the sum is greater than 2 (as there will be 2 trivial matches)

Answer 6

CJam, 10 bytes

I caught the CJam bug. My first answer, so probably can be golfed some more:

q__+(;);\#

Outputs -1 for FALSE and a number >=0 for TRUE

Answer 7

GolfScript, 10 bytes

..+(;);\?)

Yet another implementation of xnor's clever idea.

Answer 8

Python - 59 57

lambda s:any([s*n==s[:n]*len(s)for n in range(2,len(s))])

Answer 9

Pure bash, 30 bytes

Simple port of @xnor's clever answer:

[[ ${1:1}${1:0: -1} =~ "$1" ]]

Exit code is 0 for TRUE and 1 for FALSE:

$ for s in 'Hello, World!Hello, World!Hello, World!' 'asdfasdfasdf' 'asdfasdfa' 'ĴĴĴĴĴĴĴĴĴ' 'ĴĴĴ123ĴĴĴ123' 'abcdefgh'; do echo "./isrepeated.sh "\"$s\"" returns $(./isrepeated.sh "$s"; echo $?)"; done
./isrepeated.sh "Hello, World!Hello, World!Hello, World!" returns 0
./isrepeated.sh "asdfasdfasdf" returns 0
./isrepeated.sh "asdfasdfa" returns 1
./isrepeated.sh "ĴĴĴĴĴĴĴĴĴ" returns 0
./isrepeated.sh "ĴĴĴ123ĴĴĴ123" returns 0
./isrepeated.sh "abcdefgh" returns 1
$ 

Note =~ within [[ ... ]] is the regex operator in bash. However "Any part of the pattern may be quoted to force it to be matched as a string". So as ai often the case with bash, getting quoting right is very important - here we just want to check for a string submatch and not a regex match.

Answer 10

TI-BASIC - 32

I thought I'd try a tokenized language. Run with the string in Ans, returns 0 if false and the length of the repeated string if true.

inString(sub(Ans+Ans,1,2length(Ans)-1),sub(Ans,length(Ans),1)+Ans

Amazing how it's a one-liner.

Answer 11

ECMAScript 6 (189)

(function(){var S=String.prototype,r=S.repeat;S.isRepeated=function(){return!1};S.repeat=function(c){var s=new String(r.call(this,c));if(c>1)s.isRepeated=function(){return!0};return s}}());

 

< console.log("abc".isRepeated(),"abc".repeat(10).isRepeated());
> false true

Surely this is the only valid solution? For example, the word (string) nana isn't necessarily created from "na".repeat(2)

Answer 12

ECMAScript 6 (34 36)

Another ES6 answer, but without using repeat and using xnor's trick:

f=i=>(i+i).slice(1,-1).contains(i)

Must be run in the console of a ES6-capable browser such as Firefox.

Answer 13

C 85

l,d;f(s){return l=strlen(s),strstr(d,strcpy(strcpy(d=alloca(l*2+1),s)+l,s)-1)-d-l+1;}

It turned out to be quite long but external functions are always like that. It came to my mind that I could rewrite every string function replacing them by a loop or a recursive one. But in my experience it would turn out longer and frankly I don't want to try that out.

After some research I saw solutions on high performance but not as clever (and short) as xnor's one. just to be original... i rewrote the same idea in c.

explanation:

int length, 
    duplicate;
int is_repetition(char *input)
{
    // length = "abc" -> 3
    length = strlen(input);
    // alloca because the function name is as long as "malloc" 
    // but you don't have to call free() because it uses the stack
    // to allocate memory
    // duplicate = x x x x x x + x
    duplicate = alloca(length*2 + 1);
    // duplicate = a b c 0 x x + x
    strcpy(duplicate, input);
    // duplicate = a b c a b c + 0
    strcpy(duplicate + length, input);
    if (strstr(duplicate,duplicate + length - 1) != duplicate + length - 1)
        // repetition
        // e.g. abab -> abababab -> aba[babab]
        // -> first occurence of [babab] is not aba[babab]
        // but a[babab]ab -> this is a repetition
        return 1;
    else
        // not repetition
        // e.g. abc -> abcabc -> ab[cabc]
        // -> first occurence of [cabc] is ab[cabc]
        // it matches the last "cabc"
        return 0;
}

Answer 14

ECMAScript 6 (59 62 67 73)

Not a winner, but seems like there should at least be one answer actually in ES6 for this question that actually uses the repeat function:

f=i=>[...i].some((_,j)=>i.slice(0,j).repeat(i.length/j)==i)

Must be run in the console of a ES6-capable browser such as Firefox.

It does a lot of unnecessary iterations, but why make it longer just to avoid that, right?

• Edit #1: Saved a few bytes by converting it into a function. Thanks to Optimizer!
• Edit #2: Thanks to hsl for the spread operator trick to save more bytes!
• Edit #3: And thanks to Rob W. for another 3 bytes!

Answer 15

Jelly, 3 bytes

ṙJċ

Try it online!

Same as this answer (maybe the later challenge is a generalization of this one?).

Answer 16

Java 8, 28 bytes

s->s.matches("(?s)(.+)\\1+")

Try it online.

Explanation:

Checks if the input-String matches the regex, where String#matches implicitly adds ^...$ to match the entire String.
Explanation of the regex itself:

^(s?)(.+)\1+$
^                Begin of the string
 (s?)            Enable DOTALL-mode, where `.` also matches new-lines
     (           Open capture group 1
      .+          One or more characters
        )        Close capture group 1
         \1+     Plus the match of the capture group 1, one or more times
            $    End of the string

So it basically checks if a substring is repeated two or more times (supporting new-lines).