# Pairable strings

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.

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>

• Can we use anything other than ab? – Erik the Outgolfer Nov 2 '16 at 8:50
• If bbababbb is pairable, why are baab and aaaaabbaaaaa not? – rnso Nov 2 '16 at 14:07
• @rnso From my understanding, bbababbb can be spilt as 3 pairs: bb, abab and bb which concatenates in that order to form the original string, whereas the other two cannot. – Sunny Pun Nov 2 '16 at 17:31
• By the question "each of which (substring) is a string repeated twice CONSECUTIVELY" and that is not satisfied with bbababbb. Otherwise, baab can also be split to b a a b, and aaaaabbaaaaa to aaaaa b b aaaaa. – rnso Nov 2 '16 at 18:03
• @rnso Not sure what you mean there. By consecutively, I mean the two repetitions are next to each other. In "b a a b", the two b's are separated by a's, so that doesn't work. – xnor Nov 2 '16 at 21:22

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

• That's a really clean recursion, using the index for both for the center of the double and the center to partition. It's funny that truthiness is checked as being less than something. I do see some improvements... – xnor Nov 2 '16 at 0:43

# 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. • Dangit, I had been waiting for 3 weeks to post this... – ETHproductions Nov 2 '16 at 0:00 • Martin had been waiting too. – xnor Nov 2 '16 at 0:02 • Whoops! I only beat him by 10 seconds, too... Well I'm sure if I write a Hexagony answer he'll forgive me! – FryAmTheEggman Nov 2 '16 at 0:07 • @FryAmTheEggman I'm looking forward to it. :) – Martin Ender Nov 2 '16 at 0:17 • It's exactly the same with Perl : perl -pE '$_=/^((.+)\2)+$/' – Dada Nov 2 '16 at 0:51 # 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.  • This ... seems inefficient. How long inputs can this handle in a reasonable time frame? – John Dvorak Nov 2 '16 at 4:51 • It's extremely unefficient (O(2^n^2), I think). I'd have to check locally. TIO runs out of memory for strings of length 6. – Dennis Nov 2 '16 at 4:57 • A string of length 6 takes 3:20 minutes on my machine and requires 6 GB of memory. – Dennis Nov 2 '16 at 5:25 • @Dennis Let's not do a length 100 input then, because everything will crash. Yes, even TIO. – Erik the Outgolfer Nov 2 '16 at 8:52 • @EriktheGolfer That's a good idea since it will unnecessarily slow down TIO for other uses, but it won't crash it. As soon as the system runs out of memory, the process simply gets killed by the OOM. – Dennis Nov 2 '16 at 15:03 ## 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.  • You can replace or.map with any – BlackCap Nov 2 '16 at 8:38 • @BlackCap Of course, thanks! I initially had any g.map(words.concat) and thought "hey, I can golf the any to or"... – Zgarb Nov 2 '16 at 8:40 # 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. • I tried using strings, but I couldn't get anywhere near my index-based score. That's one clever and you have there. – Dennis Nov 11 '16 at 19:30 • Congrats! Recursing on the partition was the trick I had in mind. – xnor Nov 11 '16 at 23:47 # 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.  # 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./  # 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  ## 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. • Nice! Same count using substr without modifying i. But with slice repeated 3 times you can save 1 byte aliasing it – edc65 Nov 2 '16 at 8:54 • @edc65 How do you get the same count without modifying i? I realise that s.substr(i,i+i) returns the same as s.slice(i,i+=i) but I then use the modified value of i later... – Neil Nov 2 '16 at 9:45 • it's s.substr(i,i) 2 bytes less, then s.slice(i+i) 2 bytes more – edc65 Nov 2 '16 at 10:10 • @edc65 Oh of course it is, I must need more coffee... – Neil Nov 2 '16 at 10:23 ## 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). # JavaScript (ES6), 24 bytes x=>/^((.+)\2)+$/.test(x)


Probably doesn't get shorter than this.

• Shouldn't that be \2? – Neil Nov 2 '16 at 0:25
• @Neil For some reason, I thought it worked with \1, but aab returns true... thanks for the fix. – ETHproductions Nov 2 '16 at 0:28

# PHP, 40 Bytes

prints 0 for false and 1 for true

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


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

## 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"
.
.
.
.
.
.


# 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


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

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

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

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! # 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' }