Pairable strings

Question

A string is pairable if it can be split into subtrings, each of which is a string repeated twice consecutively. For example, aabaaababbbaba is pairable as:

aaba aaba
b b
ba ba

Given a non-empty string of a's and b's, output a Truthy value if it's pairable and a Falsey value if it isn't.

Pairable:

aa
abaaba
bbababbb
aabaaababbbaba
babababa
bbbbbbbbbbbb
aaababbabbabbbababbaabaabaababaaba
aaaabaab

Not pairable:

a
ba
baab
abaabaaba
bbbbbbbbbbbbbbb
baababbabaaaab
aaaaabbaaaaa

I encourage you to come up with non-regex-based solutions even when there's already a shorter regex answer in your language. You can mark them as "no regex". By regex, I mean a built-in string pattern matching subsystem.

---

Leaderboard:

var QUESTION_ID=98252,OVERRIDE_USER=20260;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/98252/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;

body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

Answer 1

Python 2, 68 63 bytes

f=lambda s,n=1:s==2*s[:n]or''<s[n:]>-f(s,n+1)<f(s[n:])*f(s[:n])

Returns True or False. Test it on Ideone.

Answer 2

Retina, 11 bytes

^((.+)\2)+$

Try all the test cases. The first two bytes make it multi-line.

Pretty literal interpretation of the rules, obviously uses regex, like all Retina programs will.

Answer 3

Jelly, 10 bytes

ẆŒPẋ€€2F€ċ

Not exactly efficient... Try it online!

How it works

ẆŒPẋ€€2F€ċ  Main link. Argument: s (string)

Ẇ           Window, generate the array of all substrings of s.
 ŒP         Powerset; generate all subarrays of substrings of s.
   ẋ€€2     Repeat each substring in each subarray twice.
            For example, ["ab", "a", "b"] becomes ["abab", "aa", "bb"].
       F€   Flatten the subarrays by concatenating their strings.
         ċ  Count how many times s appears in the generated strings.

Answer 4

Haskell, 72 69 bytes (no regex)

g(a:b:c)|a==b=g c
g x=x==[]
any(g.words.concat).mapM(\c->[[c],c:" "])

A brute-force approach. Try it on Ideone.

Thanks to BlackCap for -3 bytes.

Explanation

The helper function g takes a list of strings, and checks that it consists of pairs of identical strings, like ["aa","aa","bba","bba","ab","ab"]. The (anonymous) main function splits a string in all possible ways, and checks that at least one splitting results in a list that g accepts.

g(a:b:c)                                  g on list with elements a, b and tail c,
        |a==b                              in the case that a==b,
             =g c                          recurses to the tail c.
g x=                                      g on any other list x
    x==[]                                  checks that x is empty.
                                           This includes the case where a is not equal
                                           to b, resulting in False.
any(g.words.concat).mapM(\c->[[c],c:" "]) The main function:
                    mapM(\c->[[c],c:" "])  Replace each letter c with either "c" or "c "
                                           in all possible ways, return list of results.
any(              ).                       Check that at least one result satisfies this:
            concat                          Concatenate the 1- or 2-letter strings,
      words.                                split again at each space,
    g.                                      apply g.

Answer 5

Python 2, 60 bytes

f=lambda s,t='':''<s>f(s[1:],t+s[0])|f(t and s)*f(t)>-(s==t)

I hope this is correct. It runs pretty slowly and the and doesn't look optimal.

Answer 6

Jelly, 12 bytes

ŒṖµœs€2ZEµ€S

Two bytes longer than my other answer, but this approach is a lot more efficient and handles all but one of the test cases.

Try it online!

How it works

ŒṖµœs€2ZEµ€S  Main link. Argument: s (string)

ŒṖ            Generate all partitions of s.
  µ      µ€   Map the monadic chain between the µ's over the partitions.
   œs€2         Split each string in the partition into two chunks of equal length.
       Z        Zip/transpose, collecting the first halves in one array and the
                second halves in another.
        E       Test the arrays of halves for equality.
           S  Return the sum of the results, counting the number of different
              ways s can be paired.

Answer 7

Pyth - No Regex - 13 12 bytes

Checks if any of the partitions are made up of all string that are equals to each other when chopped in two.

sm.AqMcL2d./

Test Suite.

Answer 8

Brachylog, 14 bytes (no regex)

lye~l:1j@2zcc?

Try it online!

This is too slow for some of the test cases

Explanation

ly                  The list [0, …, length(Input)]
  e~l               A list whose length is an element of the previous list
     :1j            Append itself to this list
        @2zc        Split in half, zip and concatenate so that the list contains pairs of
                      consecutive identical elements
            c?      The concatenation of that list must result in the Input

Answer 9

JavaScript (ES6), no regexp, 75 74 bytes

f=s=>!s|[...s].some((_,i)=>i&&s[e='slice'](0,i)==s[e](i,i+=i)&&f(s[e](i)))

Returns 1 for pairable otherwise 0. Edit: Saved 1 byte thanks to @edc65.

Answer 10

Python, 58 bytes

f=lambda s,p='':s>''and(f(p)>-(s==p)<f(s))|f(s[1:],p+s[0])

This is based on the Dennis's recursive method. The Boolean negation trick is taken from there as well.

The new idea is to recurse over partitions (p,s) of the original string by starting with ('',s) and repeatedly moving the first character of s to be the last character of p. This allows for the parts to be referred to directly without string slicing. But, because the partition starts with p empty, we must be careful to avoid infinite loops of f(s) calling f(s).

Answer 11

JavaScript (ES6), 24 bytes

x=>/^((.+)\2)+$/.test(x)

Probably doesn't get shorter than this.

Answer 12

PHP, 40 Bytes

prints 0 for false and 1 for true

<?=preg_match("#^((.+)\\2)+$#",$argv[1]);

Answer 13

Python, 66 64 bytes

Thanks @Zgarb for -1 byte!

f=lambda x,s=1:x>x[:s]and(x==2*x[:s])|f(x[:s])&f(x[s:])|f(x,s+1)

Returns True or False.

Try it online!

Any help golfing this would be appreciated.

Answer 14

Racket 230 bytes

(let((sl string-length)(ss substring))(if(odd?(sl s))(printf ".~n")(begin(let p((s s))(if(equal? s "")(printf "!")
(for((i(range 1(add1(/(sl s)2)))))(when(equal?(ss s 0 i)(ss s i(* 2 i)))(p(ss s(* 2 i)(sl s)))))))(printf ".~n"))))

Prints a '!' for each way in which the string is pairable. Prints a '.' at the end.

Ungolfed:

(define (f s)
  (let ((sl string-length)                              ; create short names of built-in fns
        (ss substring))
    (if (odd? (sl s))  (printf ".~n")                   ; odd length strings cannot be pairable; end here.
        (begin
          (let loop ((s s))                             ; start testing here
            (if (equal? s "") (printf "!")              ; if no remaining string, it must be pairable
                (for ((i (range 1 (add1 (/(sl s)2)))))  ; ch lengths varying from 1 to half of string length
                  (when (equal? (ss s 0 i)              ; ch if substrings are same
                                (ss s i (* 2 i)))
                    (loop (ss s (* 2 i) (sl s) ))))))   ; if yes, loop to check remaining string.
          (printf ".~n")))))                            ; End of testing.

Testing:

(println "Following should be pairable")
(f "bbaabbaa")            ; should produce 2 '!' since 2 ways are possible.
(f "aa")
(f "abaaba")
(f "bbababbb")
(f "aabaaababbbaba")
(f "babababa")                    ; should be pairable in 2 ways.
(f "bbbbbbbbbbbb")                ; should be pairable in many ways.
(f "aaababbabbabbbababbaabaabaababaaba")
(f "aaaabaab")
(println "Following should be unpairable")
; (f "a")
(f "ba")
(f "baab")
(f "abaabaaba")
(f "bbbbbbbbbbbbbbb")
(f "baababbabaaaab")
(f "aaaaabbaaaaa")

Output:

"Following should be pairable"
!!.
!.
!.
!.
!.
!!.
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!.
!.
!.
"Following should be unpairable"
.
.
.
.
.
.

Answer 15

Perl, 16 +2 = 18 bytes (with regex)

Run with the -nl flags. -E is free.

say/^((.+)\2)+$/

Run as:

perl -nlE 'say/^((.+)\2)+$/'

Returns a list of the capture groups (a truthy) if pairable, null string if not pairable.

Explanation

The -nl flags will run the code in a loop (-n), putting the input (with trailing newline removed because of -l) into the variable $_ each time, then evaluating the code each time input is entered, until the program is manually terminated. The -E flag lets you evaluate code on the command line, and enables the say command.

say/^((.+)\2)+$/

   /^((.+)\2)+$/  #The regex engine
      (.+)\2      #Find any set of at least one character, followed by itself
     (      )+    #Do this at least one time
   /^         $/  #Make sure that this matches the entire string from start to end
say               #Output the result of the regex

If a match is found (e.g. if the string is pairable), then the regex returns a list of the capture groups, which evaluates to a truthy, which is then passed to say, and output. If no match is found, then the regex returns the empty string, which evaluates to falsy, which is then passed to say, and output.

Sample:

$ perl -nlE 'say/^((.+)\2)+$/'
aaababbabbabbbababbaabaabaababaaba
baababaababaaba                      #Truthy
baababbabaaaab
                                     #Falsy
bbababbb
bbb                                  #Truthy
aabaaababbbaba
bababa                               #Truthy
abaabaaba
                                     #Falsy

Answer 16

GNU Prolog, 49 46 bytes

Probably works in other variants too, although they don't all represent strings the same way; GNU Prolog's representation is a useful one for this problem.

It's unclear whether this counts as using regex or not. It's not using any regex-like feature, but the entire semantics of the language are similar to those of regex.

New version (uses the recursion trick seen in some other answers):

s(X):-append(A,B,X),(A=B;A\=X,B\=X,s(A),s(B)).

Older version:

s(X):-X=[];append(A,B,X),B\=X,append(C,C,A),s(B).

This is a predicate (Prolog's equivalent of a function) called s, not a complete program. Use it like this:

| ?- s("aa").
true ?
yes
| ?- s("aaababbabbabbbababbaabaabaababaaba").
true ?
yes
| ?- s("baababbabaaaab").
no
| ?- s("bbbbbbbbbbbbbbb").
no

An interesting feature of the older solution is that if you ask the interpreter "are there more solutions?" via use of ; at the true ? prompt (rather than asking "is there any solution" via pressing return at the prompt, like I did above), it returns "true" a number of times equal to the number of different ways the string can be expressed in the given form (e.g. it returns "true" twice with s("aaaa")., as this can be parsed as (a a)(a a) or as (aa aa)).

Prolog programs are often reversible (allowing s to generate a list of strings with the given property). The older one isn't (it goes into an infinite loop), but that's because of the golfed method I used to ensure that C is nonempty; if you rewrite the program to specify C as nonempty explicitly, it generates strings of the form "aa", "aabb", "aabbcc", and so on (Prolog being Prolog, it doesn't specify identities for the characters that make them up, just a specification of which characters are the same). The newer one generates strings of the form "aa", "abab", "abcabc", and so on; this is an infinite loop in its own right, and thus never hits the point at which it'd get stuck due to failing to detect a zero-length string.

Answer 17

Brainfuck, 177 bytes

+[<<<<,]>>>>[>+[>+[[>>]<+<[<<]>+>-]<[>+<-]>>>,>>[>>]+<<[<+>>-<-]<[>+<-]>>[,>[-<<
<<]<[<<<<]>]<[[<<]>]>>]>>[[>+>>>]>>>[>]<<<<[>+[-<<<,<]<[<<<[[<<<<]>>]<]>]>>]<[[-
>>>>]>>[<]<]<<]<.

Formatted:

+[<<<<,]
>>>>
[
  >+
  [
    >+
    [
      [>>]
      <+<[<<]
      >+>-
    ]
    <[>+<-]>
    >>,>>[>>]
    +<<[<+> >-<-]
    <[>+<-]>
    >
    [
      not equal
      ,>[-<<<<]
      <[<<<<]
      >
    ]
    <
    [
      equal
      [<<]
      >
    ]
    >>
  ]
  >>
  [
    mismatch
    [>+>>>]
    >>>[>]
    <<<<
    [
      backtrack
      >+[-<<<,<]
      <
      [
        not done yet
        <<<
        [
          [<<<<]
          >>
        ]
        <
      ]
      >
    ]
    >>
  ]
  <
  [
    match
    [->>>>]
    >>[<]
    <
  ]
  <<
]
<.

Expects input without a trailing newline. Prints \x00 for false and \x01 for true.

Try it online.

This implements depth-first search. In particular: check for repeated prefixes of increasing length starting from the current suffix, then move to the next suffix if a match is found, otherwise backtrack.

At the beginning, the string is reversed and a sentinel \x01 is placed at the end.

The tape is divided into 4-cell nodes. The memory layout of a node is:

c h x 0

where c is the character, h is a flag for whether the character is in the first half of a repeated prefix, and x is a flag to keep track of the current pair of characters being compared. The h flags stay in place while the x flags form a moving window.

If the string is pairable, the pointer lands next to the sentinel at the end of the main loop; otherwise, the pointer falls off the left side of the string while backtracking.

Answer 18

Brachylog, 5 bytes

~c~jᵐ

Try it online!

Note that this algorithm can take a very long time, especially on falsey cases, since it checks every possible partition of the input string.

Explanation

~c     Reversed concatenate: find a list that, when concatenated, results in the input string
       This examines all partitions of the input
  ~jᵐ  Map reversed juxtapose: for each string in that list, is it the result of concatenating
       a string to itself?

For an input string like "ababcc", ~c tries different partitions until it comes to ["abab", "cc"], at which point ~j succeeds for both items of the list, ᵐ outputs ["ab", "c"], and the predicate succeeds.

Answer 19

R, 31 bytes

grepl("^((.+)\\2)+$",scan(,""))

Try it online!

Based on Retina answer.

R, 129 bytes

And here’s an original, non-regex answer:

o=(y=utf8ToInt(scan(,"")))<0;for(i in 2*1:(sum(y>0)/2))for(j in 1:(i/2)){w=i:(i-j+1);v=w-j;if(all(y[w]==y[v]))o[c(v,w)]=T};all(o)

Try it online!

Answer 20

Lithp, 57 characters

#S::((? (!= (null) (match S "^((.+)\\2)+$")) true false))

Sample usage:

% pairable_strings.lithp
(
    (def f #S::((? (!= (null) (match S "^((.+)\\2)+$")) true false)))
    (print (f "aa"))
    (print (f "aabaaababbbaba"))
    (print (f "aaababbabbabbbababbaabaabaababaaba"))
    (print (f "ba"))
)

# ./run.js pairable_strings.lithp
AtomValue { value: 2, type: 'Atom', name: 'true' }
AtomValue { value: 2, type: 'Atom', name: 'true' }
AtomValue { value: 2, type: 'Atom', name: 'true' }
AtomValue { value: 3, type: 'Atom', name: 'false' }