Check if a string is a shuffle of twins

Question

Explanation

Two strings can be shuffled by interspersing their letters to form a new string, much like two piles of cards can be shuffled to form a single pile.

For example, the strings HELLO and WORLD can be shuffled to form HWEOLRLLOD, or HEWORLLLDO, or perhaps simply HELLOWORLD.

It is not a shuffle if the original order of letters is not preserved. For example, the D in WORLD cannot ever appear before the R after being shuffled. This means that EHLLOWRDLO, for instance, is not a shuffle of HELLO and WORLD, even though it contains all the original letters.

A string is a shuffle of twins if it can be formed by shuffling two identical strings. For example, ABACBDECDE is a shuffle of twins because it can be formed by shuffling ABCDE and ABCDE. DBEACBCADE is not a shuffle of twins because it cannot be formed by shuffling two identical strings.

Program Details

Given an input string, output 0 if it is not a shuffle of twins, and output one of the twin strings if it is a shuffle of twins.

You may assume that the input string has a length inclusively between four and twenty characters and is composed entirely of uppercase alphabetic characters. It should be able to run in a reasonable amount of time, say, under 10 minutes.

This is code golf, so the shortest solution wins.

Example I/O

> ABACBDECDE
ABCDE

> DBEACBCADE
0

> FFFFFF
FFF

> FFGGG
0

> ABBA
0

> AABB
AB

> AABAAB
AAB

I have an example (non-golfed) implementation.

Answer 1

Haskell, 114

main=getLine>>=putStrLn.f.p;f x=head$[a|(a,b)<-x,a==b]++["0"]
p[]=[([],[])];p(x:y)=do(a,b)<-p y;[(x:a,b),(a,x:b)]

Ungolfed:

main :: IO ()
main = getLine >>= putStrLn . findMatch . partitions

-- | Find the first partition where the two subsequences are
-- equal. If none are, return "0".
findMatch :: [(String, String)] -> String
findMatch ps = head $ [a | (a,b) <- ps, a == b] ++ ["0"]

-- | Return all possible partitions of the input into two
-- subsequences. Preserves the order of each subsequence.
--
-- Example:
-- partitions "AB" == [("AB",""),("B","A"),("A","B"),("","AB")]
partitions :: [a] -> [([a], [a])]
partitions []     = [([], [])]
partitions (x:xs) = do (a, b) <- partitions xs
                       [(x:a, b), (a, x:b)]

Explanation:

Most of the work is being done in the partitions function. It works by recursively generating all partitions (a, b) of the tail of the list, and then using the list monad to prepend the initial element x to each of them and gather all the results.

findMatch works by filtering this list so that only partitions where the subsequences are equal remain. It then returns the first subsequence in the first partition. If none remain, the list is empty, so the "0" appended at the end gets returned instead.

main just reads the input, feeds it through these two functions and prints it.

Answer 2

R, 113 chars

l=length(x<-charToRaw(scan(,'')));max(apply(combn(l,l/2),2,function(i)if(all(x[i]==x[-i]))rawToChar(x[i])else 0))

Ungolfed (and instead a function that takes the string):

untwin <- function(x) {
  x <- charToRaw(x)
  indMtx <- combn(length(x),length(x)/2)
  res <- apply(indMtx, 2, function(i) {
    if (all(x[i]==x[-i]))
      rawToChar(x[i])
    else
      0
  })
  max(res)
}

untwin("ABACBDECDE") # "ABCDE"
untwin("DBEACBCADE") # 0

The solution relies on the combn function that generates all combinations of indices as columns in a matrix. apply then applies a function to each column (dimension 2) in the matrix and returns a vector of strings or zeroes. max then find the biggest string (which trumps 0).

A cool feature in R is the ability to select a subset of a vector given a vector of indices, and to then select the complement of that subset by negating the indices: x[i] == x[-i]

Answer 3

Mathematica, 87

This is directly based on hammar's post, but hopefully it is distinct enough to merit posting.

<<Combinatorica`

f=Catch[Cases[Characters@#~KSetPartitions~2,{x_,x_}:>Throw[""<>x]];0]&

Test:

f /@ {"ABACBDECDE", "DBEACBCADE", "FFFFFF", "FGG", "ABBA", "AABB", "AABAAB"}

{"ABCDE", 0, "FFF", 0, 0, "AB", "AAB"}

Answer 4

Brachylog, 11 bytes

{;Ẹp}ᵐzcᵛ.∨

Try it online!

Using an unbound output variable as 0 might be cheating, so +1 byte if that's a problem (even though ideally it could just be allowed to fail and we could drop the .∨).

{   }ᵐ         For each character of the input,
 ;Ẹ            pair it with an empty string
   p           in either order.
      z        The zipped pairs
       cᵛ      concatenate to the same thing,
         .     which is output.
          ∨    If that's not possible, leave the output unbound instead of failing.

Answer 5

D

string c(string in,string a=[],string b=[]){
    if(in.length==0)return a==b?a;"0";
    auto r=c(in[1..$],a~in[0],b);
    return r=="0"?c(in[1..$],a,b~in[0]):r;
}
void main(){writeln(c(readline));}

using depth first recursive search

I can make it faster with a int i = min(a.length,b.length);if(a[0..i]!=b[0..i])return "0"; guard clause

Answer 6

Ruby, 89 characters

s=->a,x,y{a=="\n"?x==y ?x:?0:[s[b=a[1..-1],x+c=a[0],y],s[b,x,y+c]].max}
$><<s[gets,'','']

This code implements a plain recursive search algorithm. The input must be given on STDIN.

Answer 7

Perl, 68 chars

/^((.+)(?{local($x,$,)=($,,$x.$^N)}))+$(?(?{$o=$,eq$x&&$,})|x)/?$o:0

The input string assumed to be in the $_ variable, the output is the value of the expression. Trailing newlines in input are ignored. You can run this from the command line like this:

perl -lne 'print /^((.+)(?{local($x,$,)=($,,$x.$^N)}))+$(?(?{$o=$,eq$x&&$,})|x)/?$o:0'

This code makes use of Perl's regexp engine (and specifically its embedded code execution feature) to do the backtracking. Basically, it matches the input string against the regexp ^((.+))+$, keeping track of the odd- and even-numbered submatches in $x and $,, and rejecting the match at the end if the two aren't equal.

Answer 8

Python, 168 characters

def f(s):
 c=s[0]
 d=i=r=0
 if s==c+c:r=c
 while i+1 and i<=len(s)/2 and not r:
  if i:d=f(s[1:i]+s[i+1:])
  if d:r=c+d
  i=s.find(c,i+1)
 return r
print f(raw_input())

Answer 9

05AB1E, 11 bytes

.œ€ιJ.ΔË}θ<

Try it online or verify all test cases.

If a more flexible output would have been allowed which outputs -1 instead of 0, and ["ABCDE","ABCDE"] instead of "ABCDE", it could have been 8 bytes instead:

.œ€ιJ.ΔË

Try it online or verify all test cases.

Explanation:

.œ         # Get all partitions of the (implicit) input-string
           #  i.e. "AABB" → [["A","A","B","B"],["A","A","BB"],["A","AB","B"],["A","ABB"],
           #   ["AA","B","B"],["AA","BB"],["AAB","B"],["AABB"]]
  €ι       # Uninterleave each partition
           #  → [[["A","B"],["A","B"]],[["A","BB"],["A"]],[["A","B"],["AB"]],[["A"],["ABB"]],
           #   [["AA","B"],["B"]],[["AA"],["BB"]],[["AAB"],["B"]],[["AABB"],[]]]
    J      # Join the inner lists together to a single string
           #  → [["AB","AB"],["ABB","A"],["AB","AB"],["A","ABB"],
           #   ["AAB","B"],["AA","BB"],["AAB","B"],["AABB",""]]
     .Δ    # Find the first result for which:
           # (will result in -1 if none are valid)
       Ë   #  Both strings are equal, thus a twin
      }θ   # Afterwards, only leave the last value (the single string if we've found a
           # twin; or 1 if it resulted in -1)
           #  i.e. ["AB","AB"] → "AB"
           #  i.e. -1 → 1
        <  # And decrease by 1 (no-op if it was a string with just uppercase letters)
           #  i.e. "AB" → "AB"
           #  i.e. 1 → 0
           # (after which the result is output implicitly)

Answer 10

JavaScript (Node.js), 54 bytes

g=([c,...x],p,q)=>c?g(x,[p]+c,q)||g(x,[q]+c,p):p==q&&p

Try it online!

Try each split

Answer 11

Scala, 431 bytes

431 bytes, it can be golfed much more.

---

Golfed version. Try it online!

def g(n:Int)={
def l(n:Int,r:Int):ArrayBuffer[List[Int]]=if(r==0)ArrayBuffer(List())else if(r==n)ArrayBuffer((0 until n).toList)else l(n-1,r-1).map(n-1::_)++l(n-1,r)
l(n,n/2)}
def u(s:String)={
val l=s.length
if(l%2!=0)"0"
else{
val c=g(l)
var r="0"
var m=0
for(b<-c){
val i=b.toSet
val a=(0 until l).filterNot(i)
val h=i.toList.sorted.map(s.charAt)
val d=a.sorted.map(s.charAt)
if(h==d&&h.length>m){
m=h.length
r=h.mkString
}}
r}}

Ungolfed version. Try it online!

import scala.collection.mutable.ArrayBuffer

object Main {

  def getCombinations(n: Int): ArrayBuffer[List[Int]] = {
    def loop(n: Int, r: Int): ArrayBuffer[List[Int]] = {
      if (r == 0) ArrayBuffer(List())
      else if (r == n) ArrayBuffer((0 until n).toList)
      else loop(n - 1, r - 1).map(n - 1 :: _) ++ loop(n - 1, r)
    }

    loop(n, n / 2)
  }

  def untwin(s: String): String = {
    val length = s.length
    if (length % 2 != 0) {
      return "0"
    }

    val combinations = getCombinations(length)

    var result: String = "0"
    var maxLen = 0
    for (comb <- combinations) {
      val i = comb.toSet
      val rest = (0 until length).filterNot(i)
      val firstHalf = i.toList.sorted.map(s.charAt)
      val secondHalf = rest.sorted.map(s.charAt)
      if (firstHalf == secondHalf && firstHalf.length > maxLen) {
        maxLen = firstHalf.length
        result = firstHalf.mkString
      }
    }

    result
  }

  def main(args: Array[String]): Unit = {
    println(untwin("ABACBDECDE")) // "ABCDE"
    println(untwin("DBEACBCADE")) // "0"
    println(untwin("FFFFFF")) // "FFF"
    println(untwin("FFGGG")) // "0"
    println(untwin("ABBA")) // "0"
    println(untwin("AABB")) // "AB"
    println(untwin("AABAAB")) // "AAB"
  }
}