¿Son iguales estas listas?

19

Como bien sabrás, Python tiene listas. Como puede que no sepa, estas listas pueden contenerse.

a = []
a.append(a)

Python 2

Python 3

Estos son geniales y hay muchas cosas interesantes que puedes hacer con ellos, sin embargo, no puedes compararlos.

a = []
a.append(a)
b = []
b.append(b)
a == b

Python 2

Python 3

Tarea

Su trabajo es escribir una función en Python (o cualquier lenguaje que pueda manejar objetos de Python directamente) que tomará dos listas que pueden contener y compararlas.

Dos listas son iguales si tienen la misma longitud y no existe una secuencia de números, de modo que indexar ambas listas por esa secuencia da como resultado dos objetos que no son iguales bajo esta definición de igual. Todos los objetos que no están en la lista contenidos en una lista serán enteros de python por simplicidad y deben compararse con la igualdad incorporada de python para enteros.

Su programa no debe confiar en la profundidad de recursión de Python para determinar si una lista es infinitamente profunda. Es decir:

def isInfinite(a,b):
 try:
  a==b
  return False
 except RunTimeError:
  return True

No es una forma válida de determinar si dos listas son autorreferenciales.

Casos de prueba

Asume que define una función equal

a = []
a.append(a)
b = []
b.append(b)
print(equal(a,b))

True

a = []
b = []
a.append(b)
b.append(a)
print(equal(a,b))

True

a = []
b = []
a.append(1)
a.append(b)
b.append(1)
b.append(a)
print(equal(a,b))

True

a = []
a.append(a)
b = [a]
print(equal(a,b))

True

a = []
b = []
c = []
a.append(b)
b.append(c)
c.append(a)
equal(a,b)

True

a=[1,[2]]
b=[1,[2,[1]]]
a[1].append(a)
b[1][1].append(b[1])

True

a = []
a.append(a)
b = [1]
b.append(a)
c = [1]
c.append([c])
print(equal(b,c))

False

a = []
b = []
a.append(1)
a.append(b)
b.append(a)
b.append(1)
print(equal(a,b))

False

a = []
b = []
a.append(a)
b.append(b)
b.append(b)
print f(a,b)

False
Asistente de trigo
fuente
17
Como nota al margen para los votantes potenciales: tenga en cuenta que, en general , los desafíos específicos del idioma están mal vistos, excepto en ciertas circunstancias (como tareas que solo son interesantes en ciertos idiomas). En mi opinión, este es un maravilloso ejemplo de un desafío específico del idioma.
DJMcMayhem
@WheatWizard Eso no es exactamente suficiente: las listas anidadas también deben tener la misma longitud.
xnor
@WheatWizard En realidad puedes compararlos. En Python, solo obtienes un "límite de recursión excedido" si no son iguales. tio.run/nexus/…
mbomb007
@ mbomb007 Eso es porque python por defecto compara las referencias. Si tiene dos objetos idénticos que tienen referencias diferentes, falla, de ahí el desafío.
Wheat Wizard
2
¿Puedes extender este desafío a todos los idiomas en los que las listas pueden contener?
CalculatorFeline

Respuestas:

9

Python 2 , 94 bytes

g=lambda c,*p:lambda a,b:c in p or all(map(g((id(a),id(b)),c,*p),a,b))if a>[]<b else a==b
g(0)

Pruébalo en línea!

Una mejora en la solución muy inteligente de isaacg de almacenar los idpares de listas que se procesan y declararlas iguales si la misma comparación aparece en un nivel inferior.

El paso recursivo all(map(...,a,b))dice eso ay bson iguales si todos los pares de elementos correspondientes en ellos son iguales. Esto funciona muy bien para rechazar la longitud desigual porque maprellena la lista más corta None, a diferencia de la zipque se trunca. Como ninguna de las listas reales contiene None, estas listas rellenadas siempre serán rechazadas.

xnor
fuente
¿Cuál es el propósito de ,después de la c?
Wheat Wizard
Lo hace una tupla.
mbomb007
a=[];a+=[a,1];b=[];b+=[b,2];f(a,b)desborda la pila y a=[1];b=[2];f(a,b);f(a,b)parece un problema de reutilización.
Anders Kaseorg
@AndersKaseorg Ya veo, mutar la lista estaba pidiendo problemas. Creo que esto lo arregla.
xnor
1
@AndersKaseorg Y veo que escribiste básicamente la misma solución de función en función. Hay una solución de 95 bytes y sin que: f=lambda a,b,p=[0]:p[0]in p[1:]or all(map(f,a,b,[[(id(a),id(b))]+p]*len(a)))if a>[]<b else a==b. Tal vez hay una mejor manera de manejar el map.
xnor
5

Python, 233 218 197 217 bytes

d=id
def q(a,b,w):
 w[(d(a),d(b))]=0
 if d(a)==d(b):return 1
 if(a>[]and[]<b)-1:return a==b
 if len(a)!=len(b):return 0
 for x,y in zip(a,b):
  if((d(x),d(y))in w or q(x,y,w))-1:return 0
 return 1
lambda a,b:q(a,b,{})

La función anónima en la última línea realiza la función deseada.

Esto todavía está en proceso de golf, solo quería mostrar que esto es posible.

Esencialmente, ponemos una entrada en w si estamos trabajando en un cheque dado. Dos cosas son iguales si son el mismo objeto, si no son listas y son iguales, o si todos sus elementos son iguales o están siendo trabajados.

isaacg
fuente
¿No puedes usar en a>[]lugar de i(a,list)?
mbomb007
@ mbomb007 Esto se escribió antes de agregar la regla "Todo es listas o entradas". Actualizará.
isaacg
Puedes usar a>[]<bylen(a)-len(b)
mbomb007
@ETHproductions Oh, su número de bytes está mal. Es por eso
mbomb007
lata d(a)==d(b) ser a is b? Eso reduciría dos usos de d.
xnor