Driftsort adalah cara sederhana untuk "mengurutkan" sebuah array. Ia bekerja dengan "geser" atau "memutar" elemen-elemen dalam array sampai array diurutkan, atau sampai array gagal diurutkan.
Mari kita telusuri dua contoh. Pertama, pertimbangkan array [10, 2, 3, 4, 7]
. Karena array tidak diurutkan, kami memutarnya sekali. (Ini bisa terjadi di kedua arah, asalkan tetap arah yang sama.) Kemudian, array menjadi:
[7, 10, 2, 3, 4]
Ini tidak diurutkan, jadi kami memutar lagi.
[4, 7, 10, 2, 3]
Dan lagi:
[3, 4, 7, 10, 2]
Dan terakhir kali:
[2, 3, 4, 7, 10]
Dan itu disortir! Jadi array [10, 2, 3, 4, 7]
dapat di-driftsortable. Berikut ini semua rotasi array, untuk kejelasan:
[10, 2, 3, 4, 7]
[7, 10, 2, 3, 4]
[4, 7, 10, 2, 3]
[3, 4, 7, 10, 2]
[2, 3, 4, 7, 10]
Pertimbangkan sekarang array [5, 3, 9, 2, 6, 7]
. Lihatlah rotasinya:
[5, 3, 9, 2, 6, 7]
[7, 5, 3, 9, 2, 6]
[6, 7, 5, 3, 9, 2]
[2, 6, 7, 5, 3, 9]
[9, 2, 6, 7, 5, 3]
[3, 9, 2, 6, 7, 5]
Tidak satu pun dari array ini yang diurutkan, sehingga array [5, 3, 9, 2, 6, 7]
tidak dapat dipindahkan.
Objective Diberikan array kosong / daftar bilangan bulat sebagai input untuk suatu program / fungsi, mengimplementasikan driftsort pada input dan output itu, atau output nilai falsey ( atau array / daftar kosong) jika tidak dapat driftsort. Bilangan bulat terikat ke bahasa Anda maks / mnt, tetapi ini harus minimal 255 untuk maks, dan 0 untuk mnt.
Anda dapat menggunakan metode pemilahan bawaan, tetapi bukan bawaan yang memecahkan tantangan.
Ini adalah kode-golf , jadi program terpendek dalam byte.
Uji kasus
input => output
[1] => [1]
[5, 0, 5] => [0, 5, 5]
[3, 2, 1] => false
[0, 9, 3] => false
[1, 2, 3, 4] => [1, 2, 3, 4]
[4, 1, 2, 3] => [1, 2, 3, 4]
[0, 2, 0, 2] => false
[5, 3, 9, 2, 6, 7] => false
[0, 0, 0, 0, 0, 0, 0] => [0, 0, 0, 0, 0, 0, 0]
[75, 230, 30, 42, 50] => [30, 42, 50, 75, 230]
[255, 255, 200, 200, 203] => [200, 200, 203, 255, 255]
sorted(l)
adalah sublist yang berdekatan daril+l
.shiftsort
?shift
operasi yang menghapus elemen pertama dari sebuah array.Jawaban:
Jelly , 6 byte
Cobalah online! atau verifikasi semua kasus uji .
Bagaimana itu bekerja
sumber
Ruby, 33
a.any?
dijalankan hingga satu kali untuk setiap elemen dalam array, kecuali itu berhenti (dan mengembalikan true) segera setelah array telah dimutasi menjadi keadaan diurutkan. Jika ini terjadi, kami mengembalikan array yang dimutasi. Kalau tidak, kami mengembalikan nilai palsu yangany?
mengembalikan.sumber
Python 2, 51 byte
Tidak repot berputar. Alih-alih, susun daftar, lalu lihat apakah dokumen aslinya dapat diurutkan berdasarkan drift dengan memeriksa apakah ada paling banyak satu penurunan di antara elemen berurutan dari daftar yang dikurifikasi. Hitungannya adalah
<3
karenamap
mengisi daftar yang lebih pendek denganNone
di akhir, menambahkan penurunan palsu.sumber
[1, 3, 2, 4]
hanya memiliki satu penurunan di antara elemen berurutan tetapi tidak dapat diurutkan berdasarkan drift.<3
juga<3
untuk menghindari harus memutar daftar dengan tepat.Pyth, 9 byte
Penjelasan:
Coba di sini!
Atau gunakan test suite!
sumber
.:
. Kombinasi akan mencakup elemen yang tidak bersebelahan.Matlab,
614741 byteTerima kasih @Suever untuk -6 byte!
Jika
strfind([a,a],sort(a))
mencoba untuk menemukan vektor input yang diurutkan sebagai 'substring' dari yang tidak disortir, itu ditambahkan ke dirinya sendiri. Jika benar, input adalah driftsortable dan kita mendapatkan vektor dengan panjang 2, jika tidak kita mendapatkan vektor kosong.min
hanya mentransformasikannya ke angka / vektor kosong. Menambahkan vektor yang disortir ke 0 hanya menampilkannya, menambahkannya ke vektor kosong melempar kesalahan.sumber
[2, 3]
tidak menjadi sublist[12, 34]
?strfind
dapat bekerja secara langsung dengan angka, tidak hanya dengan karakter (meskipun itu tidak didokumentasikan). Jika angka-angka itu ditafsirkan sebagai karakter mereka akan terbatas pada65535
(coba misalnya+char(1e5)
)Julia,
716652 byteIni adalah fungsi anonim yang menerima array dan mengembalikan array atau boolean. Untuk menyebutnya, tetapkan ke variabel.
Untuk larik input x , kami membangun set semua rotasi x dan memeriksa apakah versi x yang diurutkan adalah elemen dari daftar itu. Jika ya, kita kembalikan x diurutkan, kalau tidak kita kembalikan salah.
Disimpan 19 byte berkat Dennis!
sumber
Pip , 15 + 1 =
1716 byteUgh, bahasa golf lainnya meniup ini keluar dari air. Namun, karena saya sudah menulisnya ...
Mengambil input sebagai argumen baris perintah yang dipisahkan oleh spasi. Membutuhkan
-p
atau flag pemformatan array lain untuk menampilkan hasil secara jelas dan bukan gabungan. Kasing palsu menghasilkan string kosong, yang terlihat berdasarkan baris baru yang tertinggal.sumber
JavaScript (ES6),
727065 bytePengembalian
0
gagal. Sebelumnya8583versi 80-byte dihindari panggilansort
:Sunting: Disimpan 2 byte dengan menginisialisasi
c
ke-1
alih-alih0
. Disimpan 5 byte dengan beralih darireduce
kemap
, ...sumber
[10, 2, 3, 4, 7]
.[1]
,[0, 0, 0, 0, 0, 0, 0]
dan[75, 230, 30, 42, 50]
.sort
pengawasan, yang menyebabkan kegagalan pengujian ketiga. Dua kegagalan tes lainnya disebabkan oleh saya terlalu bermain golf; Saya telah kembali ke versi sebelumnya.05AB1E , 12 byte
Kode:
Menggunakan pengodean CP-1252 . Cobalah online! .
sumber
Snowman 1.0.2 , 27 byte
Ini adalah subrutin yang mengambil input dari dan output ke permavar saat ini.
Cobalah online!
sumber
MATL,
1312109 byteGagasan yang sama dengan jawaban @ flawr mana kami membajak
strfind
(Xf
) untuk menemukan versi input yang diurutkan dalam gabungan dua salinan input.Cobalah secara Online!
Penjelasan
sumber
g
? Atau ganting
dengana
n
karenan
bisa> 1.a
pasti berfungsi. Saya pikir ada cara yang lebih baik. Terima kasih!Julia, 33 byte
Cobalah online!
Bagaimana itu bekerja
Ini menggabungkan larik x dengan dirinya sendiri dan menghitung jumlah pasangan yang tidak berurutan, yaitu jumlah sub-susun yang berdekatan [a, b] dengan b - a <0 . Jika c adalah jumlah pasangan unordered dari x itu sendiri dan t adalah 1 jika elemen terakhir x lebih besar dari yang pertama,
sum
akan mengembalikan 2c + t .Array x adalah driftsortable iff (c, t) = (1, 0) ( x harus diputar ke nilai yang lebih kecil dari satu-satunya pasangan yang tidak terurut), (c, t) = (0, 1) ( x diurutkan) atau (c, t) = (0, 0) ( x diurutkan dan semua elemennya sama), yang benar iff 2c + t <3 .
sumber
Javascript ES6,
484543 karakterUji:
sumber
(x+[,x])
dan byte lebih lanjut dengan menggunakan~
daripada1+
dalam kondisi Anda.Brachylog , 39 byte
Saya benar-benar perlu menambahkan argumen opsional ke
$( - circular permute left
untuk permutasi lebih dari sekali ... ini akan menjadi 13 byte. Ini akan menunggu setelah menerapkan transpiler baru yang stabil di Prolog.Penjelasan
sumber
Ruby, 47 byte
Fungsi rekursif. Kembali
nil
jika array input tidak dapat diseret.sumber
CJam,
1713 byteTerima kasih kepada Dennis karena telah menghemat 4 byte.
Blok (fungsi) tanpa nama yang mengambil dan mengembalikan daftar.
Suite uji.
Penjelasan
Ini pada dasarnya menggunakan observasi xnor bahwa daftar yang diurutkan muncul dua kali dari daftar aslinya jika driftnya dapat diurutkan:
sumber
C ++ 14, 242 karakter
Jika saya tidak dapat membiarkan output kosong, 252 karakter http://ideone.com/HAzJ5V
Versi tidak resmi http://ideone.com/Dsbs8W
PS: Berdasarkan ide @ MichelfrancisBustillos .
sumber
Java 7, 207 byte
Detail coba di sini
sumber
Jawa 175
mencetak output sebagai nilai yang dipisahkan ruang, atau mencetak
f
untuk nilai falsey.melewati semua kombinasi array bilangan bulat sampai menemukan urutan yang valid atau kehabisan kombinasi. array tidak dimodifikasi, melainkan urutan driftsorted disimpan sebagai string dibatasi ruang.
sedikit lebih mudah dibaca:
coba online
sumber
C, 105 byte
Ini menerima integer input sebagai argumen baris perintah yang terpisah dan mencetak daftar output sebagai satu integer per baris.
Jika daftar tidak dapat dipindahkan, program keluar sebelum waktunya karena pengecualian floating point, sehingga output kosongnya mewakili daftar kosong.
Verifikasi
sumber
Ruby, 28
Mengembalikan array yang diurutkan, atau
nil
(yang merupakan nilai falsy) jika input tidak drift-sortable.sumber
Python, 53 byte
Jika Anda ingin menguji kepala ini ke https://www.repl.it/languages/python3 dan salin tempel ini:
Bagaimana itu bekerja:
s
adalah variabel yang menyimpansorted
fungsi python yang mengurutkan daftarN
adalah fungsi utamas(x)
dikalikan dengan apakah daftar tersebut driftsortable atau tidakstr(s(x))[1:-1]in str(x+x)
(terima kasih kepada @xnor)[1,2,3,4]*false
menghasilkan daftar kosong[]
[1,2,3,4]*true
menghasilkan[1,2,3,4]
sumber
lambda x,s=sorted:(`s(x)`[1:-1]in`x+x`)*s(x)
44 byte.Python, 83 byte
Hal ini dipermalukan oleh jawaban python lainnya, tapi saya mungkin juga mempostingnya. Saya sangat tidak suka
bagian. Apakah ada cara yang lebih cepat untuk beralih melalui daftar?
sumber
l.append(l.pop(0))or g==l for _ in l
menyimpan byte lebih dari pendekatan range-len. Menggunakan alambda
akan menghemat 14 byte tambahan.MATLAB / Oktaf, 118 byte
sumber
input('')
. Juga hindari spasi dan tanda kurung yang tidak perlu! Dan Anda dapat kembali menumpahkan beberapa byte dengan terlebih dahulu mendefinisikanf=@issorted
.PowerShell v2 +,
8780 byteLangkah-langkah melalui daftar input
$a
, memeriksa setiap elemen berpasangan (termasuk yang terakhir dan yang pertama) untuk melihat apakah ada lebih dari satu pasangan yang menurun. Jika pasangan tertentu menurun, kami menurun$c
. Keluaran baik daftar diurutkan, atau elemen tunggal0
, berdasarkan pada nilai$c
di akhir. Jika lebih dari satu pasangan "buruk" hadir, maka++$c
akan tetap negatif, jika tidak setidaknya akan ada0
, maka elemen kedua dari pseudo-ternary dipilih ($a|sort
).Saya melihat xnor melakukan sesuatu yang serupa , tetapi saya datang dengan ini secara mandiri.
sumber
Faktor, 47 byte
gabungkan urutan ke dirinya sendiri, lalu periksa apakah rendisi yang diurutkan dari yang asli adalah urutan.
sumber
dup dup append \\ natural sort \\ dip subseq?
Bahkan cocok dengan pola 4-4-3 :)C ++, 313
359370byteTeriakan besar ke @Qwertiy karena berhasil dan mengajari saya beberapa metode bermain golf yang hebat!
Golf:
Tidak Disatukan:
sumber
using namespace std;
adalah 20 karakter saatstd::
6 kali 30.bool s = False;
- mengapa tidak=0
? Anda bisa jatuhreturn 0;
. Mengapa tanda kurung ada di sini!s&&(c<=v.size())
? Figur kawat gigi dan tidak ada koma ...std::
danreturn 0;
) telah menjadi kebiasaan dari kelas pemrograman. Saya benar-benar harus mulai memeriksa program saya dengan lebih baik.True
danFalse
bukannyatrue
danfalse
. ideone.com/kVTI25 - versi Anda, ideone.com/y8s44A - diperbaiki dan disiapkan untuk versi golf.True
danFalse
dari Python. Aku bahkan tidak tahu kamu bisa menulisif
seperti itu!Mathcad, TBD
Dalam Mathcad, 0 (skalar) == false.
Penghitungan byte (Setara) adalah TBD sampai metode penghitungan disetujui. Kira-kira 52 byte menggunakan byte = operator / simbol keyboard equivalence.
sumber
Mathematica
55 50 6158 byteDengan 3 byte disimpan, terima kasih kepada Martin Büttner.
Upaya saya sebelumnya tidak lulus semua test case. Saya perlu menambahkan
Union
untuk menghindari pengulangan dalam daftar yang dimasukkan secara berurutan.Tes
Penjelasan
Putar kanan daftar input dari 1 hingga
n
kali, di manan
panjang daftar input. Jika daftar input yang diurutkan adalah di antara daftar yang diputar, kembalikan; jika tidak, kembalikan daftar kosong.sumber
@@
dan/@
daftar kosong.Join@@
seharusnya masih lebih pendek dari ituFlatten@
.PHP, 98 byte
Outputs
1
jika driftsortable, kalau tidak apa-apasumber