W odcinku Futurama The Prisoner of Benda członkowie załogi wymieniają się ciałami, z zastrzeżeniem, że żadna para ciał nie może zamieniać umysłów więcej niż raz.

Wyzwanie

Napisz program lub funkcję, która akceptuje prawidłową kolekcję zamian umysłu-ciała, które już miały miejsce, i wysyła legalny zestaw zamian, które przywrócą każdy umysł do pierwotnego ciała. Identyfikatory tych kolekcji ciało-umysł muszą być łańcuchami, które nie będą zawierać nowych linii. Możesz dodać maksymalnie dwie (wyraźnie nazwane) osoby, które nie miały wcześniej swapów do grupy wejściowej. (Dowód, że potrzebujesz maksymalnie 2 dodatkowych ciał). Musisz jednak dodać minimalną liczbę osób wymaganą do rozwiązania problemu.

Dane wejściowe i wyjściowe mogą przybierać dowolną czytelną formę, jednak nie można w nich przechowywać żadnych dodatkowych informacji. Możesz założyć, że zawsze jest ważny. To jest kod golfowy, więc zwycięzcą jest zgłoszenie z najmniejszą liczbą bajtów.

Przykłady

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

Ten z serialu:

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

Przedstawione poniżej rozwiązanie programu jest nieprawidłowe:

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

Jest to nieważne, ponieważ Ethan i Clyde są niepotrzebni z powodu tego, jak mało Fry Phillip, Zoidberg John i Hermes Hermes używali maszyny. Prawidłowe rozwiązanie dla tego przypadku podano poniżej:

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

Zauważ, że istnieje wiele możliwych odpowiedzi na każde prawidłowe dane wejściowe. Każda jest ważna.

Python 3: 328 znaków (wolny), 470 znaków (szybki)

Prawdopodobnie trochę za długo na poważną odpowiedź.

Wolny i krótki kod:

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)stosuje zamianę sna u. W metodzie głównej f(Q)najpierw generuję listę wszystkich osób nkorzystających z operacji ustawiania i przekształcam wynik z powrotem na listę. while 1-Loop jest oczywiście pętli krawędzi. W nim też próbuję rozwiązać problem, korzystając z osób, w których jestem n. Jeśli to się nie powiedzie, dodaję inną osobę, łącząc wszystkie nazwiska n+=[''.join(n)]. Dlatego while 1pętla jest wykonywana maksymalnie 3 razy (patrz dowód w pytaniu).

Rozwiązanie problemu odbywa się brutalnie. Generuję wszystkie legalne swapy i próbuję wszystkich permutacji for t in permutations(i for i in combinations(n,2)if not set((i,i[::-1]))&set(Q)). Jeśli każda osoba jest w swoim ciele, zwracam sekwencję zamiany.

Stosowanie:

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

Przykład z Futamy trwa zbyt długo. Jest 9 osób, więc jest 36 możliwych zamian, a 28 z nich jest legalnych. Więc jest ich 26! permutacje prawne.

Szybszy kod

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)

Funkcja f(Q)ma iteracyjne podejście do pogłębiania. Najpierw próbuje głębokość = 0, następnie głębokość = 1, aż głębokość = (l * ll) // 2-len (Q), co jest maksymalną liczbą legalnych ruchów. Podobnie jak wolniejszy kod, dodaje kolejną osobę i próbuje ponownie.

Funkcja rekurencyjna r(n,u,Q,t,d)próbuje rozwiązać bieżącą pozycję za upomocą dswapów. noznacza pozycję rozwiązaną, Qruchy wejściowe i truchy już wykonane. Najpierw oblicza mpotrzebną dolną granicę swapów (rozwiązując państwo za pomocą legalnych i nielegalnych swapów). Jeśli m== 0, wszystkie osoby mają prawidłowe ciało, więc drukuje rozwiązanie t. W przeciwnym razie próbuje wszystkich możliwych swapy s, jeśli m<d(przycinanie), d>1(co jest już zawarte w m<d, i//l<i%l(nie pozwalają jak swapy ('A','A')lub ('A','B')i ('B','A')) i not set([s,s[::-1]])&set(Q+t)( snie została jeszcze wykonana).

Stosowanie:

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

Znajduje optymalną zamianę dla problemu futama w około 17 sekundach na moim laptopie za pomocą pypy i około 2 minut bez pypy. Zauważ, że oba algorytmy generują różne rozwiązania, wywołując je z tym samym parametrem. Wynika to z algorytmu mieszającego Pythona set. nprzechowuje osobę za każdym razem w innej kolejności. Dlatego algorytm może być szybszy lub wolniejszy przy każdym uruchomieniu.

Edycja: Oryginalny przypadek testowy Futama był nieprawidłowy, poprawiony przypadek testowy ma optymalne rozwiązanie 9 zamiast 10, a zatem jest szybszy. 2 sekundy z pypy, 7 sekund bez.