20
\$\begingroup\$

A string of characters repeats if it contains two consecutive substrings that are equivalent.

For example, 2034384538452 repeats as it contains 3845 twice, consecutively.

Therefore, your challenge is to decide whether a string contains a repeating substring. You may take the input as a string or an array of characters.

You will never receive an empty input, and the length of the substring (if it exists) may be 1 or more.

I use 1 and 0 here as my truthy and falsy values, but you may use different values, as long as they are truthy and falsy in your language.

Examples:

abcab -> 0
bdefdefg -> 1
Hello, World! -> 1
pp.pp/pp -> 1
q -> 0
21020121012021020120210121020121012021012102012021020121012021020120210121020120210201210120210121020121012021020120210121020121012021012102012021020121012021012102012101202102012021012102012021020121012021020120210121020121012021012102012021020121012021020120210121020120210201210120210121020121012021020120210121020120210201210120210201202101210201210120210121020120210201210120210121020121012021020120210121020121012021012102012021020121012021020120210121020120210201210120210121020121012021020120 -> 0

(The last example was generated from the amount of ones between each zero in the Thue-Morse sequence)

\$\endgroup\$
  • 2
    \$\begingroup\$ Can I use inconsistent values, as long as they're still appropriately truthy or falsey? \$\endgroup\$ – Erik the Outgolfer Jun 10 '17 at 10:18
  • \$\begingroup\$ @EriktheOutgolfer Of course \$\endgroup\$ – Okx Jun 10 '17 at 10:22
  • \$\begingroup\$ @trichoplax I think he means consecutive subsequences of length >= 1. \$\endgroup\$ – Erik the Outgolfer Jun 10 '17 at 10:31
  • \$\begingroup\$ @EriktheOutgolfer "consecutive" was the word I missed. Thank you - it makes perfect sense now. \$\endgroup\$ – trichoplax Jun 10 '17 at 10:33
  • \$\begingroup\$ Can we output 1 for falsey and 0 for truthy instead? \$\endgroup\$ – Cows quack Jun 10 '17 at 10:57

18 Answers 18

12
\$\begingroup\$

Retina, 6 bytes

(.+)\1

Try it online!

Positive value for truthy; zero for falsey.

How it works

Returns the number of matches of the regex /(.+)\1/g.

\$\endgroup\$
10
\$\begingroup\$

Brachylog, 3 bytes

s~j

Try it online!

s~j
s    exists a sublist of input
 ~j  which is the result of a juxtaposition of something
\$\endgroup\$
7
\$\begingroup\$

Jelly, 6 5 bytes

Ẇµ;"f

This is a full program. TIO can't handle the last test case without truncating it.

Try it online! (last test case truncated to 250 digits)

How it works

Ẇµ;"f  Main link. Argument: s (string)

Ẇ      Words; generate all substrings of s.
 µ     New chain. Argument: A (substring array)
  ;"   Vectorized concatenation; concatenate each substring with itself.
    f  Filter; keep "doubled" substrings that are also substrings.
       This keeps non-empty string iff the output should be truthy, producing
       non-empty output (truthy) in this case and empty output (falsy) otherwise.
\$\endgroup\$
5
\$\begingroup\$

Mathematica, 32 bytes

StringMatchQ[___~~x__~~x__~~___]
\$\endgroup\$
  • \$\begingroup\$ Doesn't this require that the repeating string subsegments be adjacent? \$\endgroup\$ – DavidC Jun 10 '17 at 20:49
  • 1
    \$\begingroup\$ @Svetlana, you are correct! I hadn't taken abcab-> 0 into account. \$\endgroup\$ – DavidC Jun 11 '17 at 11:32
  • 1
    \$\begingroup\$ StringContainsQ[x__~~x__] and !StringFreeQ[#,x__~~x__]& are both shorter. \$\endgroup\$ – ngenisis Jun 21 '17 at 19:21
5
\$\begingroup\$

Java, 27 bytes

a->a.matches(".*(.+)\\1.*")

Pretty much a duplicate of the Retina answer, but there's no way Java's getting any shorter.

\$\endgroup\$
5
\$\begingroup\$

05AB1E, 5 bytes

Œ2×åZ

Try it online!

Outputs 1 as truthy value and 0 as falsy value

Explanation

Œ2×åZ
Π    # Substrings of input
 2×   # duplicate them (vectorized)
   å  # Is the element in the input? (vectorized)
    Z # Maximum value from list of elements
\$\endgroup\$
4
\$\begingroup\$

Python, 38 bytes

import re
re.compile(r'(.+)\1').search

Try it online!

Yawn, a regex. Checks if the string contains a string of one of more characters .+ followed by that same string that was just captured. The output search object is Truthy if there's at least one match, as can be checked by bool.

Using compile here saves over writing a lambda:

lambda s:re.search(r'(.+)\1',s)

Python, 54 bytes

f=lambda s:s>''and(s in(s*2)[1:-1])|f(s[1:])|f(s[:-1])

Try it online!

Searches for a substring that is composed two or more equal strings concatenated, as checked by s in(s*2)[1:-1] as in this answer. Substrings are generated recursively by choosing to cut either the first or last character. This is exponential, so it times out on the large test case.

Near misses:

f=lambda s,p='':s and(s==p)*s+f(s[1:],p+s[0])+f(s[:-1])
f=lambda s,i=1:s[i:]and(2*s[:i]in s)*s+f(s[1:])+f(s,i+1)

The first one doesn't use Python's in for checking substrings, and so could be adapted to other languages.

\$\endgroup\$
4
\$\begingroup\$

Pyth - 10 9 8 bytes

f}+TTQ.:

Returns a list of all the repeating substrings (which if there aren't any, is an empty list, which is falsy)

Try It

Explanation:

f}+TTQ.:
      .:    # All substrings of the input (implicit):
f           # filter the list of substrings T by whether...
  +TT       # ...the concatenation of the substring with itself...
 }   Q      # ...is a substring of the input
\$\endgroup\$
  • 1
    \$\begingroup\$ If you assume that the input is in quotes f}+TTQ.: works from 1 Byte less: link \$\endgroup\$ – KarlKastor Jun 12 '17 at 7:16
3
\$\begingroup\$

Cheddar, 60 bytes

n->(|>n.len).any(i->(|>i).any(j->n.index(n.slice(j,i)*2)+1))

Try it online!

\$\endgroup\$
  • \$\begingroup\$ You can golf: @.test(/(.+)\1/) \$\endgroup\$ – Downgoat Jun 21 '17 at 17:34
  • \$\begingroup\$ @Downgoat You should just submit that as another answer, really. \$\endgroup\$ – Leaky Nun Jun 21 '17 at 17:39
3
\$\begingroup\$

PHP, 32 bytes

<?=preg_match('#(.+)\1#',$argn);

Try it online!

PHP, 38 bytes

<?=preg_match('#(.+)(?(1)\1)#',$argn);

Try it online!

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

Python 3, 73 66 bytes

-7 bytes thanks to @LeakyNun

lambda s:any(2*s[j:i]in s for i in range(len(s))for j in range(i))

Try it online!

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

Perl 6, 11 bytes

{?/(.+)$0/}

Test it

Expanded:

{        # bare block lambda with implicit parameter 「$_」

  ?      # Boolify the following
         # (need something here so it runs the regex instead of returning it)

  /      # a regex that implicitly matches against 「$_」
    (.+) # one or more characters stored in $0
     $0  # that string of characters again
  /
}
\$\endgroup\$
2
\$\begingroup\$

PHP, 32 bytes

<?=preg_match('#(.+)\1#',$argn);

Run as pipe with -F. Sorry Jörg, I hadn´t noticed You had posted the same.

non-regex version, 84 82 bytes

    for($s=$argn;++$e;)for($i=0;~$s[$i];)substr($s,$i,$e)==substr($s,$e+$i++,$e)&&die

exits with return code 0 for a repeat, times out (and exits with error) for none. Run as pipe with -nr.
assumes printable ASCII input; replace ~ with a& for any ASCII.

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

JavaScript (ES6), 19 bytes

s=>/(.+)\1/.test(s)
\$\endgroup\$
  • \$\begingroup\$ How about /(.+)\1/.test? \$\endgroup\$ – Luke Jun 10 '17 at 11:13
  • \$\begingroup\$ That's what I have, @Luke. \$\endgroup\$ – Shaggy Jun 10 '17 at 11:17
  • \$\begingroup\$ @Shaggy I believe he means /(.+)\1/.test itself as the complete submission. \$\endgroup\$ – Leaky Nun Jun 10 '17 at 12:59
  • \$\begingroup\$ @Luke /(.+)\1/.test is unbound (has no this). f=/(.+)\1/.test;f('aa') wouldn't work, for example. You would need /./.test.bind(/(.+)\1/) \$\endgroup\$ – Artyer Jun 10 '17 at 20:33
  • \$\begingroup\$ You can golf to: ::/(.+)\1/.test (15 bytes) \$\endgroup\$ – Downgoat Jun 21 '17 at 17:33
1
\$\begingroup\$

Pyth, 15 bytes

.E.nm.bqNYtdd./

Try it!

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

V, 6 bytes

ø¨.«©±

Try it online!

Test Suite!

The program outputs 0 for falsey values, and a positive integer for positive values.

(Note that there was a small bug, so I had to gain 1 byte. Now after the bugfix, I will be able to replace with \x82)

Explanation

ø                     " This is a recent addition to V. This command takes in a regex
                      " and replaces the line with the number of matches of the regex
 ¨.«©±                " The compressed regex. This decompresses to \(.\+\)\1
\$\endgroup\$
1
\$\begingroup\$

Japt, 8 + 1 = 9 8 bytes

f"(.+)%1

Try it online. Outputs null for falsy, and an array containing all the repeating strings for truthy.

Explanation

 f"(.+)%1
Uf"(.+)%1" # Implicit input and string termination
Uf         # Find in the input
  "(.+)%1" #   a sequence followed by itself
 f         # and return the matched substring
           # output the return value
\$\endgroup\$
  • \$\begingroup\$ Inconsistent output values are permitted so you could use è to return the number of matches and drop the flag. \$\endgroup\$ – Shaggy Jun 10 '17 at 11:11
  • \$\begingroup\$ Yeah. I could also just drop the flag to return the match itself, since no match returns null, which is falsy. \$\endgroup\$ – Luke Jun 10 '17 at 11:13
  • \$\begingroup\$ For input 00, it outputs 00. Are you sure this is truthy in Japt? \$\endgroup\$ – Okx Jun 10 '17 at 11:25
  • \$\begingroup\$ @Okx The string "00" is. \$\endgroup\$ – ETHproductions Jun 10 '17 at 17:21
  • \$\begingroup\$ @Okx; try this. The -Q flag "prettyprints" the output so you can see that it's an array containing a single string. \$\endgroup\$ – Shaggy Jun 12 '17 at 14:53
0
\$\begingroup\$

Cheddar, 16 bytes

@.test(/(.+)\1/)

This is a function. Try it online!

\$\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.