Как вы, наверное, очень хорошо знаете, у python есть списки. Как вы, возможно, не знаете, эти списки могут содержать сами.

a = []
a.append(a)

Python 2

Python 3

Это круто, и есть много интересных вещей, которые вы можете сделать с ними, однако вы не можете их сравнить.

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

Python 2

Python 3

задача

Ваша задача - написать функцию на Python (или любом другом языке, который может напрямую обрабатывать объекты Python), который возьмет два списка, которые могут содержать себя, и сравнит их.

Два списка равны, если они имеют одинаковую длину и не существует последовательности чисел, так что при индексировании обоих списков с помощью этой последовательности получаются два объекта, которые не равны согласно этому определению равенства. Все не перечисленные объекты, содержащиеся в списке, будут простыми числами python и должны сравниваться со встроенным равенством python для целых чисел.

Ваша программа не должна полагаться на глубину рекурсии python, чтобы определить, является ли список бесконечно глубоким. То есть:

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

Не является допустимым способом определения, являются ли два списка самоссылочными.

Testcases

Предполагается, что вы определяете функцию 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 байта

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)

Попробуйте онлайн!

Усовершенствование очень умного решения isaacg - сохранение idпар списков, которые обрабатываются, и объявление их равными, если такое же сравнение подходит к более низкому уровню.

Рекурсивный шаг all(map(...,a,b))говорит о том, что aи bравны, если все соответствующие пары элементов в них равны. Это прекрасно работает для отклонения неравной длины, потому что mapдополняет кратчайший список None, в отличие от zipусеченного. Поскольку ни один из фактических списков не содержит None, эти дополненные списки всегда будут отклонены.

Python, 233 218 197 217 байт

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

Анонимная функция в последней строке выполняет желаемую функцию.

Это все еще в процессе игры в гольф, я просто хотел показать, что это возможно.

По сути, мы помещаем запись в w, если мы работаем над данной проверкой. Две вещи равны, если это один и тот же объект, если они не списки и они равны, или если все их элементы равны или работают над ними.