Malas noticias, alguien

10

En el episodio de Futurama, los miembros de la tripulación de The Prisoner of Benda intercambian cuerpos entre ellos, con la trampa de que ningún par de cuerpos puede intercambiar sus mentes más de una vez.

Desafío

Escriba un programa o función que acepte una colección válida de intercambios de mente y cuerpo que ya hayan ocurrido, y genere un conjunto legal de intercambios que devolverá cada mente a su cuerpo original. Los identificadores para estas colecciones de cuerpo y mente deben ser cadenas que no contendrán nuevas líneas. Puede agregar hasta dos personas (con nombres distintos) que no hayan tenido intercambios previos al grupo de entrada. (Prueba de que solo necesita como máximo 2 cuerpos adicionales) Sin embargo, debe agregar el número mínimo de personas necesarias para resolver el problema.

La entrada y la salida pueden tomar una forma clara, sin embargo, tampoco se puede almacenar información adicional. Puede suponer que siempre es válido. Este es el código de golf, por lo que el ganador es el envío con la menor cantidad de bytes.

Ejemplos

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

El del show:

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

La solución del programa, dada a continuación, no es vá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")]

Esto no es válido porque Ethan y Clyde son innecesarios por lo poco que Fry Phillip, Zoidberg John y Hermes Hermes usaron la máquina. A continuación se proporciona una solución válida para este caso:

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

Tenga en cuenta que claramente hay muchas respuestas posibles para cualquier entrada válida. Cualquiera es valido.

FryAmTheEggman
fuente
¿Hay algunos nombres que podemos asumir que no se usarán?
feersum
@feersum Nope, parte del desafío;)
FryAmTheEggman
1
@feersum ¿Quieres decir si tomaste toda la entrada como una cadena? Entonces sí, sin embargo, puede asumir que los nombres no tendrán nuevas líneas entre ellos. (editando esto ahora)
FryAmTheEggman
1
Su solución para la entrada del programa no funciona. Amy y Bender se intercambian al final. Una solución correcta sería[('Nikolai', 'Phillip'), ('Nikolai', 'Hubert'), ('Nikolai', 'Turanga'), ('Nikolai', 'Bender'), ('Phillip', 'Amy'), ('John', 'Wash Bucket'), ('Nikolai', 'John'), ('Phillip', 'Wash Bucket'), ('Hubert', 'John'), ('Bender', 'Hermes')]
Jakube el
1
@Jakube Lo siento, parece que cometí un error tipográfico al entrar en la situación para el espectáculo. Creo que ya está solucionado, y la solución está bien.
FryAmTheEggman

Respuestas:

3

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

Probablemente demasiado largo para una respuesta seria.

Código lento y corto:

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 un intercambio sa u. En el método principal f(Q), primero genero la lista de todas las personas que nutilizan operaciones de conjuntos y vuelven a convertir el resultado en una lista. El while 1bucle no es, por supuesto, un bucle infinito. En él, trato de resolver el problema usando a las personas que tengo dentro n. Si no tiene éxito, agrego otra persona combinando todos los nombres n+=[''.join(n)]. Por lo tanto, el while 1bucle se ejecuta como máximo 3 veces (ver prueba en la pregunta).

La resolución del problema se hace con fuerza bruta. Genero todos los swaps que son legales y pruebo todas las permutaciones for t in permutations(i for i in combinations(n,2)if not set((i,i[::-1]))&set(Q)). Si cada persona está en su propio cuerpo, devuelvo la secuencia de intercambios.

Uso:

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

El ejemplo de futurama lleva demasiado tiempo. Hay 9 personas, por lo que hay 36 intercambios posibles y 28 de ellos son legales. ¡Entonces hay 26! permutaciones legales.

Código más 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)

La función f(Q)tiene un enfoque de profundización iterativo. Primero intenta profundidad = 0, luego profundidad = 1, hasta profundidad = (l * ll) // 2-len (Q), que es el número máximo de movimientos legales. Al igual que el código más lento, agrega a otra persona e intenta nuevamente.

La función recursiva r(n,u,Q,t,d)intenta resolver la posición actual ucon dswaps. nes la posición resuelta, Qlos movimientos de entrada y tlos movimientos ya realizados. Primero calcula un límite inferior de swaps mnecesarios (resolviendo el estado con swaps legales e ilegales). Si m== 0, todas las personas están en el cuerpo correcto, por lo que imprime la solución t. De lo contrario, intenta todos los intercambios posibles s, si m<d(poda), d>1(que ya está incluido en m<d, i//l<i%l(no permite intercambios como ('A','A')o ('A','B')y ('B','A')) y not set([s,s[::-1]])&set(Q+t)( saún no se ha realizado).

Uso:

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

Encuentra los intercambios óptimos para el problema futurama en aproximadamente 17 segundos en mi computadora portátil usando pypy y aproximadamente 2 minutos sin pypy. Tenga en cuenta que ambos algoritmos generan diferentes soluciones cuando se llama con el mismo parámetro. Esto se debe al algoritmo de hash de un python- set. nalmacena a la persona cada vez en un orden diferente. Por lo tanto, el algoritmo puede ser más rápido o más lento en cada ejecución.

Editar: El caso de prueba futuro futurama estaba equivocado, el caso de prueba corregido tiene una solución óptima de 9 en lugar de 10 y, por lo tanto, es más rápido. 2 segundos con pypy, 7 segundos sin.

Jakube
fuente