Bad News, Someone

Question

In the Futurama episode The Prisoner of Benda members of the crew swap bodies with each other, with the catch that no pair of bodies can have their minds swapped more than once.

Challenge

Write a program or function that accepts a valid collection of mind-body swaps that have already occurred, and outputs a legal set of swaps that will return each mind to its original body. The identifiers for these mind-body collections must be strings which will not contain newlines. You may add up to two (distinctly named) people who have had no prior swaps to the input group. (Proof that you only need at most 2 additional bodies) However, you must add the minimum number of people required to solve the problem.

The input and output may take any clear form, however, no additional information can be stored in either. You may assume it is always valid. This is code golf, so the winner is the submission with the fewest bytes.

Examples

[('A','B'),('C','D')] -> [('A','C'),('B','D'),('A','D'),('B','C')]

['A','B'] -> ['C','D','A','C','B','D','A','D','B','C']

[('A','B'),('C','D'),('A','C'),('A','D')] -> [('B', 'E'), ('A', 'E'), ('C', 'B'), ('C', 'E')]

"A\nB\nC\nD\n" -> "A\nC\nB\nD\nA\nD\nB\nC\n"

The one from the show:

[("Amy","Hubert"),("Bender","Amy"),("Hubert","Turanga"),("Amy","Wash Bucket"),("Wash Bucket","Nikolai"),("Phillip","John"),("Hermes","Turanga")]

The show's solution, given below is invalid:

[("Clyde","Phillip"),("Ethan","John"),("Clyde","John"),("Ethan",Phillip"),("Clyde","Hubert"),("Ethan","Wash Bucket"),("Clyde","Leela"),("Ethan","Nikolai"),("Clyde","Hermes"),("Ethan","Bender"),("Clyde","Amy"),("Ethan","Hubert"),("Clyde","Wash Bucket")]

This is invalid because Ethan, and Clyde are unnecessary because of how little Fry Phillip, Zoidberg John and Hermes Hermes used the machine. A valid solution for this case is provided below:

[("Philip","Hubert"),("John","Wash Bucket"),("Philip","Turanga"),("John","Nikolai"),("Philip","Hermes"),("John","Bender"),("Philip","Amy"),("John","Hubert"),("Philip","Wash Bucket")]

Note that there are clearly many possible answers for any valid input. Any is valid.

Answer 1

Python 3: 328 character (slow), 470 character (fast)

Probably a bit too long for a serious answer.

Slow and short code:

from itertools import*
def d(u,s):i,j=map(u.index,s);u[i],u[j]=u[j],u[i]
def f(Q):
 n=set()
 for s in Q:n|=set(s)
 n=list(n)
 while 1:
  for t in permutations(i for i in combinations(n,2)if not set((i,i[::-1]))&set(Q)):
   u=n[:];j=0
   for s in Q:d(u,s)
   for s in t:
    j+=1;d(u,s)
    if n==u:return t[:j]
  n+=[''.join(n)]

d(u,s) applies a swap s to u. In the main method f(Q), I first generate the list of all persons n using set operations and converting the result back to a list. The while 1-loop is of course not a infinity loop. In it, I try too solve the problem using the persons I have in n. If it is not successful, I add another person by combining all names n+=[''.join(n)]. Therefore the while 1-loop is executed at most 3 times (see proof in the question).

The solving of the problem is done bruteforce. I generate all swaps that are legal and try all permutations for t in permutations(i for i in combinations(n,2)if not set((i,i[::-1]))&set(Q)). If each person is in it's own body, I return the sequence of swaps.

Usage:

print(f([('A','B'),('C','D')]))
print(f([('A','B')]))
print(f([('A','B'),('C','D'),('A','C'),('A','D')]))

The example from futurama takes way too long. There are 9 persons, so there are 36 possible swaps and 28 of them are legal. So there are 26! legal permutations.

Faster code

def w(u,s):i,j=map(u.index,s);u[i],u[j]=u[j],u[i]
def f(Q):
 n=set()
 for s in Q:n|=set(s)
 while 1:
  n=list(n);u=n[:];l=len(n)
  for s in Q:w(u,s)
  for d in range((l*l-l)//2-len(Q)+1):r(n,u,Q,[],d)
  n+=[''.join(n)]
def r(n,u,Q,t,d):
 m=0;v=u[:];l=len(u)
 for i in range(l):
  if n[i]!=v[i]:m+=1;w(v,(n[i],v[i]))
 if m<1:print(t);exit()
 for i in range(l*l):
  s=n[i//l],n[i%l]
  if m<=d and i//l<i%l and not set([s,s[::-1]])&set(Q+t):v=u[:];w(v,s);r(n,v,Q,t+[s],d-1)

The function f(Q) has an iterative deepening approach. It first tries depth=0, then depth=1, until depth=(l*l-l)//2-len(Q), which is the maximal number of legal moves. Like the slower code it then adds another person and tries again.

The recursive function r(n,u,Q,t,d) tries to solve the current position u with d swaps. n is the solved position, Q the input moves and t the moves already done. It first calculates an lower bound of swaps m needed (by solving the state with legal and illegal swaps). If m == 0, all persons are in the correct body, so it prints the solution t. Otherwise it tries all possible swaps s, if m<d (pruning), d>1 (which is already included in m<d, i//l<i%l (don't allow swaps like ('A','A') or ('A','B') and ('B','A')) and not set([s,s[::-1]])&set(Q+t) (s hasn't been performed yet).

Usage:

f([("Amy","Hubert"),("Bender","Amy"),("Hubert","Turanga"),("Amy","Wash Bucket"),("Wash Bucket","Nikolai"),("Philip","John"),("Hermes","Turanga")])

It finds the optimal swaps for the futurama problem in about 17 seconds on my laptop using pypy and about 2 minutes without pypy. Notice that both algorithms outputs different solutions, when calling it with the same parameter. This is because of the hashing algorithm of a python-set. n stores the person each time in a different order. Therefore the algorithm may be faster or slower each run.

Edit: The original futurama test case was wrong, the corrected test case has an optimal solution of 9 instead of 10, and is therefore faster. 2 seconds with pypy, 7 seconds without.