Sind diese Listen gleich?

19

Wie Sie vielleicht wissen, hat Python Listen. Wie Sie vielleicht nicht wissen, können sich diese Listen selbst enthalten.

a = []
a.append(a)

Python 2

Python 3

Diese sind cool und es gibt viele interessante Dinge, die Sie damit machen können, die Sie jedoch nicht vergleichen können.

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

Python 2

Python 3

Aufgabe

Ihre Aufgabe ist es, eine Funktion in Python (oder einer beliebigen Sprache, die Python-Objekte direkt verarbeiten kann) zu schreiben, die zwei Listen aufnimmt, die sich möglicherweise selbst enthalten, und diese vergleicht.

Zwei Listen sind gleich, wenn sie gleich lang sind und es keine Folge von Zahlen gibt, so dass die Indizierung beider Listen nach dieser Folge zu zwei Objekten führt, die unter dieser Definition von gleich nicht gleich sind. Alle in einer Liste enthaltenen Nicht-Listenobjekte sind der Einfachheit halber Python-Ganzzahlen und sollten mit der in Python integrierten Gleichheit für Ganzzahlen verglichen werden.

Ihr Programm sollte sich nicht auf die Rekursionstiefe von Python verlassen, um festzustellen, ob eine Liste unendlich tief ist. Das ist:

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

Ist keine gültige Methode, um festzustellen, ob zwei Listen selbstreferenziell sind.

Testfälle

Angenommen, Sie definieren eine Funktion 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
Weizen-Assistent
quelle
17
Als Randnotiz für potenzielle Wähler: Beachten Sie, dass sprachspezifische Herausforderungen im Allgemeinen mit Ausnahme bestimmter Umstände (wie Aufgaben, die nur in bestimmten Sprachen interessant sind) verpönt sind. IMO, dies ist ein wunderbares Beispiel für eine sprachspezifische Herausforderung.
DJMcMayhem
@ WheatWizard Das ist nicht genau genug - die verschachtelten Listen müssen auch die gleiche Länge haben.
xnor
@ WheatWizard Sie können sie tatsächlich vergleichen. In Python erhalten Sie nur dann eine "Rekursionsbeschränkung überschritten", wenn sie nicht gleich sind. tio.run/nexus/…
mbomb007
@ mbomb007 Das liegt daran, dass Python standardmäßig die Referenzen vergleicht. Wenn Sie zwei identische Objekte mit unterschiedlichen Referenzen haben, schlägt dies fehl, daher die Herausforderung.
Weizen-Assistent
2
Können Sie diese Herausforderung auf alle Sprachen ausweiten, in denen sich Listen selbst enthalten können?
CalculatorFeline

Antworten:

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)

Probieren Sie es online!

Eine Verbesserung gegenüber der sehr cleveren Lösung von isaacg, die verarbeiteten Listenpaare zu speichern idund für gleich zu erklären, wenn derselbe Vergleich auf einer niedrigeren Ebene erfolgt.

Der rekursive Schritt all(map(...,a,b))besagt, dass aund bgleich sind, wenn alle entsprechenden Elementpaare in ihnen gleich sind. Dies funktioniert gut, um ungleiche Längen abzulehnen, da mapdie kürzeste Liste mit aufgefüllt wird None, im Gegensatz zu zipdenen , die abgeschnitten werden. Da keine der tatsächlichen Listen enthält None, werden diese aufgefüllten Listen immer zurückgewiesen.

xnor
quelle
Was ist der Zweck des ,nach dem c?
Weizen-Assistent
Es macht es zu einem Tupel.
mbomb007
a=[];a+=[a,1];b=[];b+=[b,2];f(a,b)Überläuft den Stapel und a=[1];b=[2];f(a,b);f(a,b)scheint ein Wiederverwendbarkeitsproblem zu sein.
Anders Kaseorg
@AndersKaseorg Ich verstehe, die Liste zu mutieren, verlangte nach Ärger. Ich denke, das behebt es.
xnor
1
@AndersKaseorg Und ich sehe, Sie haben im Grunde die gleiche Funktion-in-Funktion-Lösung geschrieben. Es gibt eine 95-Byte - Lösung ohne dass: 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. Vielleicht gibt es eine schönere Art, mit dem Problem umzugehen 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,{})

Die anonyme Funktion in der letzten Zeile führt die gewünschte Funktion aus.

Dies ist noch in der Entwicklung, ich wollte nur zeigen, dass dies möglich ist.

Im Wesentlichen setzen wir einen Eintrag in w, wenn wir an einem bestimmten Scheck arbeiten. Zwei Dinge sind gleich, wenn sie dasselbe Objekt sind, wenn sie keine Listen sind und wenn sie gleich sind oder wenn alle ihre Elemente gleich sind oder bearbeitet werden.

isaacg
quelle
Kannst du nicht a>[]statt verwenden i(a,list)?
mbomb007
@ mbomb007 Dies wurde geschrieben, bevor die Regel "Alles sind Listen oder Ints" hinzugefügt wurde. Werde dich auf den neuesten Stand bringen.
Isaacg
Sie können a>[]<bundlen(a)-len(b)
mbomb007
@ETHproductions Oh, seine Byteanzahl ist falsch. Deshalb
mbomb007
Kann d(a)==d(b)sein a is b? Das würde zwei Verwendungszwecke einschränken d.
xnor