Como você deve saber, python possui listas. Como você talvez não saiba, essas listas podem se conter.

a = []
a.append(a)

Python 2

Python 3

Isso é legal e há muitas coisas interessantes que você pode fazer com elas, mas não pode compará-las.

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

Python 2

Python 3

Tarefa

Seu trabalho é escrever uma função no Python (ou qualquer linguagem que possa manipular objetos python diretamente) que pegue duas listas que possam se conter e as compare.

Duas listas são iguais se tiverem o mesmo comprimento e não existir uma sequência de números, de modo que a indexação de ambas as listas por essa sequência resulte em dois objetos que não sejam iguais nessa definição de igual. Todos os objetos que não constam de uma lista serão inteiros python por simplicidade e devem ser comparados com a igualdade interna de python para números inteiros.

Seu programa não deve contar com a profundidade de recursão do python para determinar se uma lista é infinitamente profunda. Isso é:

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

Não é uma maneira válida de determinar se duas listas são auto-referenciais.

Casos de teste

Supõe que você define uma função 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

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)

Experimente online!

Uma melhoria na solução muito inteligente de isaacg de armazenar os idpares de listas que estão sendo processados ​​e declará-los iguais se a mesma comparação ocorrer em um nível inferior.

A etapa recursiva all(map(...,a,b))diz que ae bé igual se todos os pares correspondentes de elementos forem iguais. Isso funciona bem para rejeitar o comprimento desigual, porque mappreenche a lista mais curta None, ao contrário do zipque trunca. Como nenhuma das listas reais contém None, essas listas preenchidas sempre serão rejeitadas.

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,{})

A função anônima na última linha executa a função desejada.

Ainda está em processo de golfe, eu só queria mostrar que isso é possível.

Basicamente, colocamos uma entrada em w se estivermos trabalhando em uma determinada verificação. Duas coisas são iguais se são o mesmo objeto, se não são listas e são iguais, ou se todos os seus elementos são iguais ou estão sendo trabalhados.