Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I recently saw this question on stackoverflow. It's a great question, but there's one fatal problem with the question. They are asking for the best way to do it. E.g, easiest to read, most idiomatic, neatest etc. Don't they know that isn't what matters? You're supposed to ask about how to do it with the fewest bytes of code!

Since I doubt that question will be appreciated on stackoverflow, I decided to ask it here.

The challenge

You must write the shortest possible program or function that generates all possible ways to interleave any two arbitrary strings. For example, if the two strings are 'ab' and 'cd', the output is:

['abcd', 'acbd', 'acdb', 'cabd', 'cadb', 'cdab']

As you can see, a is always before b, and c is always before d.

IO can be in any reasonable format. Use this python code to verify to check your output. (credit: JeD)

def shuffle(s,t):
    if s=="":
        return [t]
    elif t=="":
        return [s]
    else:
        leftShuffle=[s[0]+val for val in shuffle(s[1:],t)]
        rightShuffle=[t[0]+val for val in shuffle(s,t[1:])]
        leftShuffle.extend(rightShuffle)
        return leftShuffle

Sample IO:

shuffle("$", "1234"):
['$1234', '1$234', '12$34', '123$4', '1234$']

shuffle("az", "by"):
['azby', 'abzy', 'abyz', 'bazy', 'bayz', 'byaz']

shuffle("code", "golf"):
['codegolf', 'codgeolf', 'codgoelf', 'codgolef', 'codgolfe', 'cogdeolf', 'cogdoelf',
'cogdolef', 'cogdolfe', 'cogodelf', 'cogodlef', 'cogodlfe', 'cogoldef', 'cogoldfe',
'cogolfde', 'cgodeolf', 'cgodoelf', 'cgodolef', 'cgodolfe', 'cgoodelf', 'cgoodlef',
'cgoodlfe', 'cgooldef', 'cgooldfe', 'cgoolfde', 'cgoodelf', 'cgoodlef', 'cgoodlfe',
'cgooldef', 'cgooldfe', 'cgoolfde', 'cgolodef', 'cgolodfe', 'cgolofde', 'cgolfode',
'gcodeolf', 'gcodoelf', 'gcodolef', 'gcodolfe', 'gcoodelf', 'gcoodlef', 'gcoodlfe',
'gcooldef', 'gcooldfe', 'gcoolfde', 'gcoodelf', 'gcoodlef', 'gcoodlfe', 'gcooldef',
'gcooldfe', 'gcoolfde', 'gcolodef', 'gcolodfe', 'gcolofde', 'gcolfode', 'gocodelf',
'gocodlef', 'gocodlfe', 'gocoldef', 'gocoldfe', 'gocolfde', 'goclodef', 'goclodfe',
'goclofde', 'goclfode', 'golcodef', 'golcodfe', 'golcofde', 'golcfode', 'golfcode']

As usual, standard loopholes apply, and the shortest answer in bytes wins. Since the question was originally about python, I'd love to see the shortest python answer. (And no, pyth is not python). However, answers in any language are encouraged.

share|improve this question
4  
Fewest bytes of code is the bestest way to do it, every one knows that!* (disclaimer: not CR). – Eᴀsᴛᴇʀʟʏ Iʀᴋ Mar 29 at 0:48
    
Are all characters distinct? Or not necessarily? – aditsu Mar 29 at 1:53
3  
Actually... in your "code", "golf" example you have a duplicate "o" and duplicate results too, e.g. 'gcoodelf'. I'll assume that's what you want. – aditsu Mar 29 at 2:04
    
"I just found this great question. However, there is one fatal flaw: they want it done well!" – Cyoce Mar 30 at 6:43
    
You should provide the sample IO for "aabb","bc". – Taemyr Mar 30 at 8:34

11 Answers 11

up vote 1 down vote accepted

Pyth, 26

M?G?H++LhGgtGH+LhHgGtH]G]H

Try it here

This is a very basic implementation of the given recursive formula. It defines a function g that performs the required task. The link is a modified program that reads the strings from STDIN newline separated, to be more convenient. To call the function do g<string1><string2>.

Expansion:

M                ##  Define a function g taking two arguments: G and H
 ?G?H ... ]G]H   ##  Two ternaries: if G is empty return a list containing H
                 ##  if H is empty return a list containing G
   +             ##  otherwise return these next two lists joined together
   +LhGgtGH      ##  the first letter of G added to each result of a recursive call to g
                 ##  with G missing its first character and H
   +LhHgGtH      ##  the same as above but with G and H swapped

The two recursive calls are very similar, but I haven't been able to find a way to golf them any more.

share|improve this answer

Haskell, 53 48 bytes

a%""=[a]
a%b=[x:t|(x:y,z)<-[(a,b),(b,a)],t<-y%z]

Defines a function % for which a%b with strings a,b gives a list of strings.

Given two strings, we choose one of the two to take the first character from. We then recurse on the remainder of two strings, prepending that character to each result.

When one of the string is empty, the only possible result is the other string. ""%""=[""] would also suffice, but's it's longer.


53 bytes:

a@(b:c)%d@(e:f)=((b:)<$>c%d)++((e:)<$>a%f)
a%d=[a++d]

Defines a function % for which a%d with strings a,d gives a list of strings.

The function is defined recursively. If we take a character from the first string, then it must be prepended to each result of the recursive call on the remained of the first string with the second string. Symmetrically for the other string.

For the base case, if one of the strings is empty, the result is a single-element list of their concatenation. This is shorter than two cases for each string being empty.

share|improve this answer
    
@aditsu Oops, I meant ""%""=[""]. – xnor Mar 29 at 2:27
    
It's weird to have an answer winning over you by exactly one byte in the exact same language – proud haskeller Mar 29 at 21:38

Haskell, 47

(x:s)#b=(x:)<$>s%b
a#b=[]
[]%b=[b]
a%b=a#b++b#a

% is the operator that solves this challenge.

# is an operator that takes in two lists and finds all the ways to interleave them such that the first character is from the first string (with an edge case - if the first list is empty, then the result is an empty list) by recursing to %.

then, % works by just applying # twice.

Edit: The previous version had a bug in which ""%"" returned ["",""], so I fixed it up. It was fixed by adding a base case to %, which then allowed to remove a base case of the same length from # (which really, didn't make much sense).

share|improve this answer
    
@nimi But the types mismach - (#) :: [a]->[a]->[[a]], so a::[a] and the result should be of type [[a]] – proud haskeller Mar 29 at 17:09
    
Oops, you're right. Sorry. – nimi Mar 29 at 17:12

Python 2, 71 bytes

f=lambda*p:[x[0]+t for x,y in p,p[::-1]for t in x and f(x[1:],y)]or['']

Example run:

>> f('ab','AB')
['abAB', 'aABb', 'aAbB', 'ABab', 'AabB', 'AaBb']

Given two strings x,y we can take the first character of x and prepend it to each result of the recursive call with it missing f(x[1:],y). Or, we can do the same with x and y switched. By taking x,y as either the input p or its reversal `p[::-1], we get both possibilities.

To avoid taking from an empty string x, we logical short-circuit with x and. If both strings are empty, neither string can be x and we get and empty list of possibilities, which we fix with or to the correct base case [''].

A similar generative strategy in Python 3 (73 bytes):

f=lambda p,s='':[f((x[1:],y),s+x[0])for x,y in[p,p[::-1]]if x]or print(s)
share|improve this answer
    
What kind of sorcery is this?! (+1) – aditsu Mar 29 at 15:49

Python, 80

As requested, here's a python answer:

f=lambda a,b,c='':[c+x for x in[a+b][a>''<b:]or f(a[1:],b,a[0])+f(a,b[1:],b[0])]

Thanks Sp3000 for eating 4 bytes :)

share|improve this answer

CJam, 38

q~L{_2$e&{_2$(\@jf+@@(@@jf++}{+a}?}2jp

Try it online

Dynamic programming (using memoized recursion).

Explanation:

q~         read and evaluate the input (2 strings)
L{…}2j     calculate with memoized recursion with no initial cache and 2 arguments
  _2$      copy the 2 strings
  e&{…}    if they are both non-empty
    _2$    copy the strings again (they're in reverse order)
    (      take out the first character of the first string
    \@     move the strings after the character
    j      solve recursively
    f+     prepend the character to all results
    @@     bring the other copy of the strings on top (in order)
    (      take out the first character of the second string
    @@     move the strings after the character
    j      solve recursively
    f+     prepend the character to all results
    +      concatenate the 2 sets of results
  {…}      else
    +      concatenate the 2 strings (at least one is empty)
    a      put the result in an array
  ?        end if
p          pretty-print the results for the input strings
share|improve this answer

JavaScript (Firefox 30+), 88 84 81 bytes

(s,t,g=(v,w)=>v[1]?f(v.slice(1),w).map(x=>v[0]+x):[v+w])=>[...g(s,t),...g(t,s)]

Edit: Saved 4 bytes by improving my termination condition. Saved 3 bytes thanks to @edc65.

share|improve this answer
    
Too close to publish, but have a look - it's shorter: f=(a,b,z=(v,w)=>v[1]?f(v.slice(1),w).map(x=>v[0]+x):[v+w])=>z(a,b).concat(z(b,a‌​)) – edc65 Mar 29 at 13:51
    
@edc65 Very nice; I'd tried and failed to use v as the condition, but it never occurred to me to use v[1]. – Neil Mar 29 at 19:03

CJam, 32 bytes

qN/_:,eeWf%e~e!\f{\{_2$=(ot}/No}

Test it here.

This feels really golfable, but so far I've only found 4 alternative solutions that all have the same byte count:

qN/_ee{),*~}%e!\f{\{_2$=(ot}/No}
l_:!l_0f>@+])e!\f{\{_2$=(ot}/No}
ll__3$:!+.=])e!\f{\{_2$=(ot}/No}
qN/[_:,2,]ze~e!\f{\{_2$=(ot}/No} (found by Sp3000)

The basic idea is to generate all permutations of 0s and 1s corresponding to which string to take each character in the result from. That's everything up to and including the e!. The rest simply pulls out characters in that order from the two strings then.

share|improve this answer
    
Nice, I thought about that idea but didn't think it can golf that well. – aditsu Mar 29 at 16:50
    
@aditsu What we really need is a mix between e* and .* which repeats each element by a different amount. ;) (I.e. an operator to do :a.*:~. I suppose e* could be used for that since it currently errors if given two lists.) – Martin Ender Mar 29 at 16:51

MATL, 34 30 bytes

h1Mgw~hY@Xu!ttYs*w~tYs1Gn+*+!)

This uses an idea from this answer: if the lenghts of the strings are m and n, enumerate all m+n bit patterns with m bits set. One way do that that enumeration is: generate all permutations of a vector with m ones and n zeros and then remove duplicates.

Try it online!

Explanation

h     % implicitly input the two strings of lengths m and n. Concatenate
1M    % push the two strings again
g     % convert the second strings into ones
w~    % swap. Convert the second string into zeros
h     % concatenate: vector of zeros and ones
Y@    % 2D array with all permutations of that vector, each on a row
Xu    % remove duplicate rows
!     % transpose
ttYs  % duplicate twice. Cumulative sum along each column
*     % element-wise product. Produces, in each column, indices for
      % elements of the first string; 1, 2,...,m. The rest are 0
w~    % swap, negate
tYs   % duplicate. Cumulative sum along each column
1Gn+  % add length of first input
*     % element-wise product. Produces, in each column, indices for
      % elements of the second string: m+1,...,m+n. The rest are 0
+     % add. This gives indices into the concatenated string created initially
!     % transpose back
)     % index into concatenated string. Implicitly display
share|improve this answer

Batch, 154 bytes

@if "%~1%~2"=="" echo %3
@set t=%~1
@if not "%t%"=="" call %0 "%t:~1%" "%~2" %3%t:~0,1%
@set t=%~2
@if not "%t%"=="" call %0 "%~1" "%t:~1%" %3%t:~0,1%
share|improve this answer

Ruby, 83 bytes

A recursive function that returns [a+b] if either of those strings are empty. Otherwise, it returns a list of strings a[0] + every string in v[a[1..-1],b] added to a list of string b[0] + every string in v[a,b[1..-1]]

v=->a,b{a[0]&&b[0]?v[a[1..-1],b].map{|i|a[0]+i}+v[a,b[1..-1]].map{|i|b[0]+i}:[a+b]}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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