Jak zapewne wiesz, python ma listy. Ponieważ możesz nie wiedzieć, te listy mogą się zawierać.

a = []
a.append(a)

Python 2

Python 3

Są fajne i istnieje wiele ciekawych rzeczy, które możesz z nimi zrobić, ale nie możesz ich porównać.

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

Python 2

Python 3

Zadanie

Twoim zadaniem jest napisanie funkcji w Pythonie (lub dowolnym języku, który może bezpośrednio obsługiwać obiekty Pythona), który pobierze dwie listy, które mogą je zawierać i porówna je.

Dwie listy są równe, jeśli mają taką samą długość i nie istnieje taka sekwencja liczb, że indeksowanie obu list według tej sekwencji daje w wyniku dwa obiekty, które nie są równe w tej definicji równości. Wszystkie obiekty nie znajdujące się na liście zawarte na liście będą liczbami całkowitymi Pythona dla uproszczenia i powinny być porównane z wbudowaną równością Pythona dla liczb całkowitych.

Twój program nie powinien polegać na głębokości rekurencji Pythona w celu ustalenia, czy lista jest nieskończenie głęboka. To jest:

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

To nie jest poprawny sposób ustalania, czy dwie listy są referencyjne.

Przypadki testowe

Zakłada zdefiniowanie funkcji 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 bajty

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)

Wypróbuj online!

Ulepszenie bardzo sprytnego rozwiązania isaacga polegającego na przechowywaniu idpar przetwarzanych list i uznawaniu ich za równe, jeśli to samo porównanie pojawi się na niższym poziomie.

Krok rekurencyjny all(map(...,a,b))mówi to ai bsą równe, jeśli wszystkie odpowiadające im pary elementów są równe. Działa to dobrze, aby odrzucić nierówną długość, ponieważ mapwstawia najkrótszą listę None, w przeciwieństwie do tego, zipktóra obcina. Ponieważ żadna z rzeczywistych list nie zawiera None, te wypełnione listy zawsze będą odrzucane.

Python, 233 218 197 217 bajtów

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

Funkcja anonimowa w ostatnim wierszu wykonuje żądaną funkcję.

To jest wciąż w trakcie gry w golfa, chciałem tylko pokazać, że jest to możliwe.

Zasadniczo umieszczamy wpis w, jeśli pracujemy nad danym czekiem. Dwie rzeczy są równe, jeśli są tym samym obiektem, jeśli nie są listami i są równe, lub jeśli wszystkie ich elementy są równe lub nad nimi pracuje.