Ces listes sont-elles égales?

19

Comme vous le savez très bien, python a des listes. Comme vous ne le savez peut-être pas, ces listes peuvent se contenir.

a = []
a.append(a)

Python 2

Python 3

Ce sont cool et il y a beaucoup de choses intéressantes que vous pouvez faire avec eux, mais vous ne pouvez pas les comparer.

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

Python 2

Python 3

Tâche

Votre travail consiste à écrire une fonction en Python (ou tout autre langage capable de gérer directement des objets python) qui prendra deux listes qui peuvent se contenir et les comparer.

Deux listes sont égales si elles sont de la même longueur et qu'il n'existe pas de séquence de nombres telle que l'indexation des deux listes par cette séquence entraîne deux objets qui ne sont pas égaux selon cette définition d'égalité. Tous les objets non list contenus dans une liste seront des entiers python pour plus de simplicité et devraient être comparés avec l'égalité intégrée de python pour les entiers.

Votre programme ne doit pas s'appuyer sur la profondeur de récursivité de python pour déterminer si une liste est infiniment profonde. C'est:

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

N'est pas un moyen valable de déterminer si deux listes sont auto-référentielles.

Cas de test

Suppose que vous définissez une fonction 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
Assistant de blé
la source
17
Remarque complémentaire pour les électeurs potentiels: notez qu'en général , les défis spécifiques à la langue sont mal vus, sauf dans certaines circonstances (comme les tâches qui ne sont intéressantes que dans certaines langues). OMI, c'est un merveilleux exemple d'un défi spécifique à une langue.
DJMcMayhem
@WheatWizard Ce n'est pas exactement suffisant - les listes imbriquées doivent également avoir les mêmes longueurs.
xnor
@WheatWizard Vous pouvez réellement les comparer. En Python, vous n'obtenez une "limite de récursivité dépassée" que si elles ne sont pas égales. tio.run/nexus/…
mbomb007
@ mbomb007 C'est parce que python compare par défaut les références. Si vous avez deux objets identiques qui ont des références différentes, cela échoue, d'où le défi.
Wheat Wizard
2
Pouvez-vous étendre ce défi à toutes les langues où les listes peuvent se contenir?
CalculatorFeline

Réponses:

9

Python 2 , 94 octets

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)

Essayez-le en ligne!

Une amélioration par rapport à la solution très intelligente d'isaacg qui consiste à stocker les idpaires de listes en cours de traitement et à les déclarer égales si la même comparaison apparaît à un niveau inférieur.

L'étape récursive all(map(...,a,b))dit que aet bsont égaux si toutes les paires d'éléments correspondantes en eux sont égales. Cela fonctionne bien pour rejeter les longueurs inégales car mapremplit la liste la plus courte None, contrairement à zipce qui tronque. Puisqu'aucune des listes réelles ne contient None, ces listes remplies seront toujours rejetées.

xnor
la source
Quel est le but de l' ,après c?
Wheat Wizard
Cela en fait un tuple.
mbomb007
a=[];a+=[a,1];b=[];b+=[b,2];f(a,b)déborde de la pile et a=[1];b=[2];f(a,b);f(a,b)ressemble à un problème de réutilisabilité.
Anders Kaseorg
@AndersKaseorg Je vois, muter la liste demandait des ennuis. Je pense que cela le corrige.
xnor
1
@AndersKaseorg Et je vois que vous avez écrit essentiellement la même solution de fonction dans une fonction. Il y a une solution à 95 octets sans 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. Il y a peut-être une meilleure façon de gérer le map.
xnor
5

Python, 233 218 197 217 octets

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 fonction anonyme sur la dernière ligne exécute la fonction souhaitée.

C'est encore en cours de golf, je voulais juste montrer que c'est possible.

Essentiellement, nous mettons une entrée dans w si nous travaillons sur un chèque donné. Deux choses sont égales si elles sont le même objet, si elles ne sont pas des listes et elles sont égales, ou si tous leurs éléments sont égaux ou en cours d'élaboration.

isaacg
la source
Vous ne pouvez pas utiliser à la a>[]place de i(a,list)?
mbomb007
@ mbomb007 Ceci a été écrit avant l'ajout de la règle "Tout est listes ou entiers". Mettra à jour.
isaacg
Vous pouvez utiliser a>[]<betlen(a)-len(b)
mbomb007
@ETHproductions Oh, son nombre d'octets est faux. C'est pourquoi
mbomb007
Peut- d(a)==d(b)être a is b? Cela réduirait deux utilisations de d.
xnor