Hampir Daftar Perbandingan Lexikografis

9

Memasukkan

Dua daftar Adan Bbilangan bulat tidak negatif.

Keluaran

Entah 1,, 0atau -1, tergantung pada apakah Alebih besar dari, sama dengan, atau lebih kecil dari yang Bberkaitan dengan urutan leksikografis memutar seperti yang didefinisikan di bawah ini. Jika mau, Anda bisa mengganti 1, 0dan -1dengan tiga nilai konstan lainnya.

Urutan leksikografis yang bengkok adalah seperti urutan leksikografis biasa, di mana Anda membandingkan elemen daftar dengan elemen, dan memutuskan urutannya pada indeks yang berbeda pertama. Namun, dalam versi bengkok kami menggunakan pemesanan berbeda untuk bilangan bulat tidak negatif pada setiap indeks. Yaitu, pada setiap indeks i(pengindeksan dimulai dari 1), urutan ibilangan bulat non-negatif pertama (dari 0ke i-1) dibalik, dan mereka dipindahkan di atas semua angka lainnya. Selain itu, "elemen yang hilang" yang menandakan satu daftar lebih pendek dari yang lain dipindahkan langsung di bawah ini i-1. Secara visual, urutan pada indeks iadalah

i < i+1 < i+2 < i+3 < ... < [missing element] < i-1 < i-2 < i-3 < ... < 2 < 1 < 0

Perhatikan bahwa yang pertama ...menunjukkan angka yang tak terhingga banyaknya. Ini berarti bahwa daftar berikut berada dalam urutan menaik sehubungan dengan urutan leksikografis memutar:

[3,2,3,4]
[3,2,3,5]
[3,2,3,10]
[3,2,3,1341]
[3,2,3]
[3,2,3,3]
[3,2,3,2]
[3,2,3,1]
[3,2,3,0]

Aturan

Anda dapat memberikan program atau fungsi lengkap. Hitungan byte terendah menang, dan celah standar tidak diizinkan.

Uji Kasus

Output 1:
[0] []
[] [1]
[] [1,2,1,2]
[2,1] [1,1]
[0,1,2] [0,2,1]
[3,0] [3,1]
[3,1] [3]
[2] [2,2]
[2] [2,23]
[2,24] [2,23]
[2,1] [2,23]

Output 0:
[] []
[0] [0]
[1,1] [1,1]
[2,1,2] [2,1,2]

Output -1:
[1,2,1,1,2] [1,2,1,1,1]
[1,2,1,1,5] [1,2,1,1,4]
[1,2,1,1,5] [1,2,1,1]
[1,2,1] [1,2,1,1]
[1,2,1,1,5] [1,2,1,1,6]
[1,2,1,1,6] [1,2,1,1,7]
Zgarb
sumber
Apakah daftar input diindeks dari 0, dari 1, atau dari mana yang sesuai untuk bahasa kita?
Peter Taylor
@PeterTaylor Mulai 1. Saya akan mengklarifikasi itu.
Zgarb
Bisakah saya menggunakan enum Haskell sendiri untuk hasil perbandingan, bukan -1/0/1 untuk output?
John Dvorak
@ JanDvorak saya akan membiarkan itu, dan mengedit tantangan.
Zgarb

Jawaban:

1

CJam - 57

q:S~=0{S~]:A:,~e>{A{_,I>{I=_I>0{W*2}?}1?[\]}%}fI]z~>2*(}?

Ya itu masih sangat panjang ...

Cobalah online

Penjelasan singkat:
Kode output 0 jika array adalah sama dalam arti tradisional, selain itu mengkonversi setiap item dari masing-masing array ke array 2 elemen: [0 a i ] jika i > i (0-based), [1 terserah] jika i hilang, dan [2 -a i ] jika a i <= i. Dalam prosesnya, array yang lebih pendek juga diperluas ke ukuran yang lebih besar. Kemudian array yang diubah dibandingkan secara leksikografis dan hasilnya disesuaikan dengan -1/1.

aditsu berhenti karena SE adalah JAHAT
sumber
3

Python 2, 76 byte

c=lambda*a:cmp(*[[(max(i-x,-1),x)for i,x in enumerate(L)]+[(0,)]for L in a])

Ini menggantikan setiap bilangan bulat di kedua daftar dengan 2-tupel ke akun untuk pemesanan bengkok. Builtin Python 2 cmpmelakukan sisanya.

Pemakaian:

>>> c([1,2,1,1,6], [1,2,1,1,7])
-1
grc
sumber
1
Bagaimana akun ini untuk daftar yang lebih pendek untuk masuk di antara daftar yang lebih panjang ( [3,2,3,1341] < [3,2,3] < [3,2,3,0]?
nutki
@nutki menambahkan tuple (0,)ke akhir setiap daftar, yang lebih besar dari apa pun (-1, x)dan kurang dari (i-x, x)kapan i-x >= 0.
grc
Oh tentu. Saya tidak melek huruf di Python.
nutki
1

Perl, 74

Tanpa fungsi manipulasi array yang baik, perl bukanlah alat yang optimal untuk pekerjaan itu, tetapi berfungsi.

#!perl -pa
$i=0,s/\d+,?/$s=sprintf"%9d",$&;$&>$i++?$s:~$s/ge for@F;$_=$F[0]cmp$F[1]

Ujilah aku .

nutki
sumber
1

J, 95 byte

(Bukan super pendek tapi apa pun. Jelas golf.)

f=.4 :0
m=.>:>./x,y
t=.(|+(1+m)*0>:*)@(i.@#-~])@(],m$~>&#*-&#)
x(t~(*@-&((m+#x,y)&#.))t)y
)

Lulus semua kasus uji. (Set kasus uji hebat! Terima kasih!)

Metode:

  • Padding daftar yang lebih pendek dengan nilai maksimum +1 ( m=.>:>./x,y).(],m$~>&#*-&#
  • Mengubah elemen daftar sehingga perbandingan normal dapat digunakan. (|+(1+m)*0>:*)@(i.@#-~])
  • Menghitung dua angka baseX dari dua daftar dengan X yang cukup. ((m+#x,y)&#.)
  • Mengembalikan signum dari perbedaan dua angka.*@-&
randomra
sumber
0

Mathematica, 65

f=-Order@@MapIndexed[If[#>Last@#2,#,a-b#]&,PadRight[{##}+1],{2}]&

Pemakaian:

f[{1, 2, 1, 1, 6}, {1, 2, 1, 1, 7}]

-1

alephalpha
sumber