41
\$\begingroup\$

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 so smallest code in characters wins.
\$\endgroup\$
  • \$\begingroup\$ What should "" - the empty string - return? (It contains an infinite number of copies of the empty string.) \$\endgroup\$ – billpg Sep 17 '14 at 13:29
  • \$\begingroup\$ @billpg falsy value \$\endgroup\$ – Optimizer Sep 17 '14 at 13:42
  • \$\begingroup\$ Are you tie-breaking by votes? The common practice is earlier submission I think (well, the first one that got golfed down to the tying score). But I'm not sure that's written down as the default tie-breaker anywhere, so ultimately it's up to you. \$\endgroup\$ – Martin Ender Sep 17 '14 at 16:54
  • \$\begingroup\$ Time between their posting is only 30 minutes. I will not consider that to be enough for winning :) . Since that time won't change now, but votes can, I went with votes \$\endgroup\$ – Optimizer Sep 17 '14 at 17:03
  • \$\begingroup\$ This question should be renamed into xnor :) He is the man! \$\endgroup\$ – Silviu Burcea Sep 19 '14 at 8:52

16 Answers 16

16
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I was just searching for a way to inform you about that bug (the Boolean doesn't get printed). Didn't think of the first and using x was too long... \$\endgroup\$ – Dennis Sep 16 '14 at 0:13
  • \$\begingroup\$ Yeah, the bug is fixed now. Also, if you want to report bugs, a good way might be to open an issue on the github site, here: github.com/isaacg1/pyth/issues \$\endgroup\$ – isaacg Sep 16 '14 at 0:31
  • \$\begingroup\$ Oh, there it is. I don't know my way around GitHub, and I never noticed the navigation panel on the right... \$\endgroup\$ – Dennis Sep 16 '14 at 0:33
81
\$\begingroup\$

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.

\$\endgroup\$
  • 8
    \$\begingroup\$ A trivial translation into Golfscript yields 10 chars: ..+);(;\?) \$\endgroup\$ – Justin Sep 15 '14 at 22:49
  • 3
    \$\begingroup\$ I don't quite understand how this works. Can you give a manually explained example of how this would handle a string? \$\endgroup\$ – Nzall Sep 16 '14 at 8:37
  • 8
    \$\begingroup\$ @NateKerkhofs take abcabc. s+s turns it into abcabcabcabc. the [1:-1] chops of the two ends to yield bcabcabcabcab. and then s in ... tries to find abcabc as a substring of that. This substring can't be found in either of the original half, because they have both been shortened, so it must span both halves. In particular, it must have its own end before its start, which implies that it must be made up of identical (repeated) substrings. \$\endgroup\$ – Martin Ender Sep 16 '14 at 9:26
  • 6
    \$\begingroup\$ You chop it after you double it. ab becomes abab becomes ba, so it returns false, while aa becomes aaaa becomes aa, which returns true. \$\endgroup\$ – histocrat Sep 16 '14 at 16:53
  • 1
    \$\begingroup\$ @SargeBorsch It works just the same: qweqweqwe in weqweqweqweqweqw is True. \$\endgroup\$ – xnor Sep 17 '14 at 20:24
30
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ ^(.+)\1+$ works for me, which is 9 bytes. It doesn't work for you ? \$\endgroup\$ – Optimizer Sep 16 '14 at 8:51
  • \$\begingroup\$ @Optimizer Try a string with line breaks. \$\endgroup\$ – Martin Ender Sep 16 '14 at 8:53
  • \$\begingroup\$ I tried asd\nasd\nasd\n . It works \$\endgroup\$ – Optimizer Sep 16 '14 at 8:55
  • \$\begingroup\$ @Optimizer refiddle.com/refiddles/5417fb2475622d4df7e70a00 doesn't seem to work for me (and it shouldn't) \$\endgroup\$ – Martin Ender Sep 16 '14 at 8:56
  • \$\begingroup\$ Yup, that doesn't work. Maybe it escapes the \ when I write \n manually \$\endgroup\$ – Optimizer Sep 16 '14 at 9:07
12
\$\begingroup\$

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. ";
\$\endgroup\$
  • \$\begingroup\$ +1 obligated to upvote this ahead of my own CJam answer \$\endgroup\$ – Digital Trauma Sep 15 '14 at 23:36
  • \$\begingroup\$ Why the need for the final )? I think its reasonable to have -1 mean FALSE and >=0 mean TRUE \$\endgroup\$ – Digital Trauma Sep 15 '14 at 23:39
  • \$\begingroup\$ @DigitalTrauma I think 0 is falsy in CJam... for operators like g and ?. \$\endgroup\$ – jimmy23013 Sep 15 '14 at 23:42
  • \$\begingroup\$ @DigitalTrauma: Whether it's needed ultimately depends on the OP, but strictly speaking only zero is considered falsy in CJam. \$\endgroup\$ – Dennis Sep 15 '14 at 23:43
  • \$\begingroup\$ @user23013 @Dennis But what about the # find operator? Surely the result of that is also "truthy" from the success vs failure perspective? \$\endgroup\$ – Digital Trauma Sep 15 '14 at 23:45
7
\$\begingroup\$

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)

\$\endgroup\$
7
\$\begingroup\$

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

\$\endgroup\$
  • 5
    \$\begingroup\$ Welcome to the club! \$\endgroup\$ – Dennis Sep 15 '14 at 23:36
5
\$\begingroup\$

GolfScript, 10 bytes

..+(;);\?)

Yet another implementation of xnor's clever idea.

\$\endgroup\$
  • \$\begingroup\$ Hahaha, I just posted this a minute ago: codegolf.stackexchange.com/questions/37851/… . I thought about posting it as an answer, but I thought that trivial translations are uninteresting. \$\endgroup\$ – Justin Sep 15 '14 at 22:53
  • \$\begingroup\$ I even checked for new answers this time, but not for new comments... Your code is missing the ) though; when there's not match, it will print -1. If you're going to post that as an answer, I'll gladly delete mine. \$\endgroup\$ – Dennis Sep 15 '14 at 22:54
  • \$\begingroup\$ I added the ) just before you posted your answer (I edited the comment) \$\endgroup\$ – Justin Sep 15 '14 at 22:55
  • 1
    \$\begingroup\$ Improved version (in CJam): q__+)@+#). It doesn't work in GolfScript. \$\endgroup\$ – jimmy23013 Sep 15 '14 at 23:19
  • 1
    \$\begingroup\$ @user23013: Not again. I was just going to post that! There are too many CJammers out there by now... :P \$\endgroup\$ – Dennis Sep 15 '14 at 23:21
3
\$\begingroup\$

Python - 59 57

lambda s:any([s*n==s[:n]*len(s)for n in range(2,len(s))])
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ But... but... I was going to use TI-BASIC :P +1 \$\endgroup\$ – Timtech Sep 16 '14 at 22:57
  • \$\begingroup\$ @Timtech Well, note to anyone trying string manipulation in TI-BASIC: Don't try string manipulation in TI-BASIC. :P That was so hard to make and optimize. \$\endgroup\$ – Josiah Winslow Sep 17 '14 at 1:18
  • \$\begingroup\$ Good idea. String manipulation is one of the hardest things to do. However, I've posted several answers like this, so I guess now you have a competitor ;) \$\endgroup\$ – Timtech Sep 17 '14 at 11:03
  • \$\begingroup\$ Bring it on! :P \$\endgroup\$ – Josiah Winslow Sep 17 '14 at 23:39
3
\$\begingroup\$

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)

\$\endgroup\$
  • \$\begingroup\$ "nana" isn't, but the question is not testing whether .repeat was used or not. Rather, whether the string is a repeated one or not \$\endgroup\$ – Optimizer Sep 18 '14 at 11:00
  • \$\begingroup\$ I know, I was just trying to be a smart-arse :P \$\endgroup\$ – Mardoxx Sep 18 '14 at 11:02
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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

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!
\$\endgroup\$
  • \$\begingroup\$ You can just convert it into a function to save more bytes there \$\endgroup\$ – Optimizer Sep 16 '14 at 18:24
  • \$\begingroup\$ @Optimizer True, I guess it doesn't have to be "stdin". Your live up to your name :) \$\endgroup\$ – Ingo Bürk Sep 16 '14 at 18:27
  • \$\begingroup\$ I haven't tested this, but you should be able to use the spread operator for [...i] instead of i.split('') \$\endgroup\$ – NinjaBearMonkey Sep 16 '14 at 18:37
  • 1
    \$\begingroup\$ @hsl Crazy, that works. I didn't know the spread operator works like that. Originally I desperately tried to use it to create an array with the range 0..N. Thanks! \$\endgroup\$ – Ingo Bürk Sep 16 '14 at 18:39
  • 1
    \$\begingroup\$ .slice(0,j) is one character shorter than .substr(0,j). Further, the conversion to an integer seems unnecessary |0 can be removed (using |0 actually reduces the usefulness of the method because it will fail for repetitions that exceed 2^31). \$\endgroup\$ – Rob W Sep 19 '14 at 18:08
1
\$\begingroup\$

Jelly, 3 bytes

ṙJċ

Try it online!

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

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

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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