Apakah daftar ini sama?

19

Seperti yang Anda ketahui, python memiliki daftar. Karena Anda mungkin tidak tahu daftar ini dapat memuat diri mereka sendiri.

a = []
a.append(a)

Python 2

Python 3

Ini keren dan ada banyak hal menarik yang dapat Anda lakukan dengannya, namun Anda tidak dapat membandingkannya.

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

Python 2

Python 3

Tugas

Tugas Anda adalah menulis fungsi dengan Python (atau bahasa apa pun yang dapat menangani objek python secara langsung) yang akan mengambil dua daftar yang mungkin berisi dirinya sendiri dan membandingkannya.

Dua daftar sama jika panjangnya sama dan tidak ada urutan angka sehingga indeks kedua daftar dengan urutan itu menghasilkan dua objek yang tidak sama di bawah definisi yang sama ini. Semua objek non-daftar yang terkandung dalam daftar akan menjadi bilangan bulat python untuk kesederhanaan dan harus dibandingkan dengan persamaan builtin python untuk bilangan bulat.

Program Anda seharusnya tidak mengandalkan kedalaman rekursi dari python untuk menentukan apakah suatu daftar memiliki kedalaman tak terhingga. Itu adalah:

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

Bukan cara yang valid untuk menentukan apakah dua daftar adalah referensial sendiri.

Testcases

Asumsikan Anda mendefinisikan suatu fungsi 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
Wisaya Gandum
sumber
17
Sebagai catatan tambahan bagi pemilih potensial: Perhatikan bahwa umumnya tantangan khusus bahasa disukai kecuali dalam keadaan tertentu (seperti tugas yang hanya menarik dalam bahasa tertentu). IMO, ini adalah contoh luar biasa dari tantangan khusus bahasa.
DJMcMayhem
@WheatWizard Itu tidak cukup tepat - daftar yang disarangkan juga harus sama panjangnya.
xnor
@ WoatWizard Anda sebenarnya bisa membandingkannya. Dalam Python, Anda hanya mendapatkan "rekursi terbatas terlampaui" jika mereka tidak sama. tio.run/nexus/…
mbomb007
@ mbomb007 Thats karena python secara default membandingkan referensi. Jika Anda memiliki dua objek identik yang memiliki referensi berbeda maka gagal, maka tantangannya.
Wheat Wizard
2
Bisakah Anda memperluas tantangan ini ke semua bahasa tempat daftar dapat memuat dirinya?
CalculatorFeline

Jawaban:

9

Python 2 , 94 byte

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)

Cobalah online!

Peningkatan pada solusi cerdas isaacg untuk menyimpan idpasangan daftar yang sedang diproses dan menyatakannya sama jika perbandingan yang sama muncul pada level yang lebih rendah.

Langkah rekursif all(map(...,a,b))mengatakan bahwa adan bsama jika semua pasangan elemen yang sesuai di dalamnya sama. Ini berfungsi dengan baik untuk menolak panjang yang tidak sama karena mapberisi daftar terpendek None, tidak seperti zipyang terpotong. Karena tidak ada daftar aktual yang berisi None, daftar empuk ini akan selalu ditolak.

Tidak
sumber
Apa tujuan dari ,setelah c?
Wheat Wizard
Itu membuatnya menjadi tuple.
mbomb007
a=[];a+=[a,1];b=[];b+=[b,2];f(a,b)meluap tumpukan, dan a=[1];b=[2];f(a,b);f(a,b)terlihat seperti masalah usabilitas.
Anders Kaseorg
@AndersKaseorg begitu, mutasi daftar itu meminta masalah. Saya pikir ini memperbaikinya.
xnor
1
@AndersKaseorg Dan saya melihat Anda menulis pada dasarnya fungsi-dalam-fungsi-solusi yang sama. Ada solusi 95-byte tanpa bahwa: 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. Mungkin ada cara yang lebih baik untuk menangani map.
xnor
5

Python, 233 218 197 217 byte

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

Fungsi anonim pada baris terakhir melakukan fungsi yang diinginkan.

Ini masih dalam proses menjadi golf, saya hanya ingin menunjukkan bahwa ini mungkin.

Intinya, kami memasukkan entri jika kami sedang mengerjakan cek yang diberikan. Dua hal sama jika mereka objek yang sama, jika mereka tidak daftar, dan mereka sama, atau jika semua elemen mereka sama atau sedang dikerjakan.

isaacg
sumber
Tidak bisakah Anda menggunakan a>[]bukan i(a,list)?
mbomb007
@ mbomb007 Ini ditulis sebelum aturan "Semuanya daftar atau int" ditambahkan. Akan diperbarui.
isaacg
Anda dapat menggunakan a>[]<bdanlen(a)-len(b)
mbomb007
@ ETProduksi Oh, jumlah byte-nya salah. Itu sebabnya
mbomb007
Bisa d(a)==d(b)menjadi a is b? Itu akan memotong dua penggunaan d.
xnor