No episódio Futurama, os membros da tripulação do Prisioneiro de Benda trocam de corpo entre si, com a intenção de que nenhum par de corpos pode ter suas mentes trocadas mais de uma vez.

Desafio

Escreva um programa ou função que aceite uma coleção válida de trocas mente-corpo que já ocorreram e produza um conjunto legal de trocas que retornarão cada mente ao seu corpo original. Os identificadores para essas coleções mente-corpo devem ser cadeias que não conterão novas linhas. Você pode adicionar até duas pessoas (com nome distinto) que não tiveram trocas anteriores no grupo de entrada. (Prova de que você só precisa de no máximo 2 órgãos adicionais). No entanto, você deve adicionar o número mínimo de pessoas necessárias para resolver o problema.

A entrada e a saída podem assumir qualquer forma clara; no entanto, nenhuma informação adicional também pode ser armazenada. Você pode assumir que é sempre válido. Isso é código de golfe, então o vencedor é o envio com o menor número de bytes.

Exemplos

[('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"

O do show:

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

A solução do programa, apresentada abaixo é inválida:

[("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")]

Isso é inválido porque Ethan e Clyde são desnecessários devido ao pouco uso de Fry Phillip, Zoidberg John e Hermes Hermes. Uma solução válida para este caso é fornecida abaixo:

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

Observe que existem claramente muitas respostas possíveis para qualquer entrada válida. Qualquer um é válido.

Caractere Python 3: 328 (lento), caractere 470 (rápido)

Provavelmente um pouco demais para uma resposta séria.

Código lento e curto:

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)aplica uma troca spara u. No método principal f(Q), eu primeiro giro a lista de todas as pessoas nusando operações definidas e convertendo o resultado em uma lista. O while 1loop-obviamente não é um loop infinito. Nele, também tento resolver o problema usando as pessoas que tenho n. Se não der certo, adiciono outra pessoa combinando todos os nomes n+=[''.join(n)]. Portanto, o while 1loop é executado no máximo 3 vezes (veja a prova na pergunta).

A solução do problema é feita com força bruta. Gero todos os swaps legais e tento todas as permutações for t in permutations(i for i in combinations(n,2)if not set((i,i[::-1]))&set(Q)). Se cada pessoa estiver em seu próprio corpo, retornarei a sequência de trocas.

Uso:

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

O exemplo do futurama leva muito tempo. Existem 9 pessoas, então existem 36 swaps possíveis e 28 delas são legais. Então existem 26! permutações legais.

Código mais rápido

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)

A função f(Q)possui uma abordagem de aprofundamento iterativo. Primeiro, tenta a profundidade = 0, depois a profundidade = 1, até a profundidade = (l * ll) // 2-len (Q), que é o número máximo de movimentos legais. Como o código mais lento, ele adiciona outra pessoa e tenta novamente.

A função recursiva r(n,u,Q,t,d)tenta resolver a posição atual ucom dswaps. né a posição resolvida, Qa entrada se move e tos movimentos já feitos. Primeiro calcula um limite inferior de swaps mnecessários (resolvendo o estado com swaps legais e ilegais). Se m== 0, todas as pessoas estão no corpo correto, por isso imprime a solução t. Caso contrário, ele tenta todos os swaps possíveis s, se m<d(poda), d>1(que já está incluído no m<d, i//l<i%l(não permitem swaps como ('A','A')ou ('A','B')e ('B','A')) e not set([s,s[::-1]])&set(Q+t)( sainda não foi realizado).

Uso:

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

Ele encontra as trocas ideais para o problema do futurama em cerca de 17 segundos no meu laptop usando pypy e cerca de 2 minutos sem pypy. Observe que os dois algoritmos produzem soluções diferentes, ao chamá-lo com o mesmo parâmetro. Isto é devido ao algoritmo de hash de um python- set. narmazena a pessoa cada vez em uma ordem diferente. Portanto, o algoritmo pode ser mais rápido ou mais lento a cada execução.

Edit: O caso de teste do futurama original estava errado, o caso de teste corrigido tem uma solução ideal de 9 em vez de 10 e, portanto, é mais rápido. 2 segundos com pypy, 7 segundos sem.