Objektif
Hasilkan daftar orak asli, dari gerakan yang akan dilakukan Sortasi Sortir untuk mengurutkannya. Daftar asli akan memiliki semua angka dari 0
hingga N-1
(inklusif) di mana N
ukuran input.
Memasukkan
Daftar berisi gerakan yang diperlukan untuk mengurutkan daftar. Setiap nilai mewakili jumlah slot yang dipindahkan oleh nomor asli (diacak) untuk berada di posisi kanannya, perlu diingat bahwa proses ini dari kiri ke kanan.
Nilai pada posisi (0-diindeks)i
dalam daftar input akan berada di antara 0
dan i
inklusif.
Anda tidak perlu menangani input yang tidak valid, perilaku apa pun dapat diterima dalam kasus ini (crash, infinite loop, dll).
Keluaran
Daftar acak
Langkah demi langkah untuk menghasilkan gerakan
Scrambled List | Moves to sort
[4,0,2,1,3,5] | [0, , , , , ] #4 stay in place
[4,0,2,1,3,5] | [0,1, , , , ] #0 is moved 1 slot to the left
[0,4,2,1,3,5] | [0,1,1, , , ] #2 is moved 1 slot
[0,2,4,1,3,5] | [0,1,1,2, , ] #1 is moved 2 slot
[0,1,2,4,3,5] | [0,1,1,2,1, ] #3 is moved 1 slot
[0,1,2,3,4,5] | [0,1,1,2,1,0] #5 is in the right place already
[0,1,2,3,4,5]
Jadi, untuk input, [0,1,1,2,1,0]
program Anda perlu meng-output[4,0,2,1,3,5]
.
Perlu diingat bahwa pergerakannya tidak ke posisi dalam daftar (akhir) yang diurutkan, tetapi pada segmen yang diurutkan (bagian yang dicetak tebal)
Uji Kasus
[0,0,0] -> [0,1,2]
[0,1,0,1] -> [1,0,3,2]
[0,0,0,0,0,5] -> [1,2,3,4,5,0]
[0,1,2,3] -> [3,2,1,0]
[0,1,1,1] -> [3,0,1,2]
[0,1,1,2,1,0] -> [4,0,2,1,3,5]
Kemenangan
Ini kode-golf , jadi jawaban terpendek menang.
sumber
Jawaban:
Jelly , 12 byte
Cobalah online!
Penjelasan
Kita pada dasarnya dapat melihat dua daftar (input dan output) sebagai pengkodean bilangan bulat; input mengkodekan integer dalam basis faktorial, dan output mengkodekan integer sebagai permutasi. Untungnya, Jelly memiliki builtin yang sudah sangat dekat dengan kedua pengkodean ini, jadi itu hanya masalah menulis potongan kecil kode untuk dikonversi ke integer, lalu kembali ke pengkodean lainnya.
Dalam kasus faktorial dasar, kita dapat mengamati bahwa elemen pertama dari daftar harus 0, yang kedua dapat 0 atau 1, yang ketiga harus 0/1/2, dan seterusnya. Jadi, kita harus membalikkan input agar elemen-elemennya menjadi urutan penulisan normal untuk konversi basis.
Selain itu, untuk perintah relatif konversi faktorial dan konversi permutasi agar sesuai dengan operasi yang digunakan penyortiran jenis, kita perlu melakukan dua penyesuaian: membalik urutan permutasi, dan membalik urutan urutan output. Membalikkan daftar output cukup mudah, hanya perlu
U
di akhir program. Untuk membalik urutan permutasi, kita kurangi dari faktorial panjang input (ini berfungsi karena faktorial dasar menghasilkan angka dalam kisaran 0 hingga (panjang! -1), sedangkan permutasi diberi nomor oleh Jelly dari 1 hingga panjang! , menghasilkan off-by-one implisit yang membatalkan off-by-one yang biasanya Anda dapatkan ketika mengurangi indeks permutasi dari faktorial).Jelly , 9 byte, bekerja sama dengan @JonathanAllan
Versi program ini sangat mirip, tetapi menggunakan metode berbeda untuk membalik urutan permutasi; cukup meniadakan input dengan
N
cukup untuk membuatœ?
memperlakukan pesanan secara terbalik. Selain itu, ia bekerja secara identik dengan program sebelumnya.Cobalah online!
sumber
Æ¡
danœ?
akan bekerja untuk ini (saya sudah mulai mencoba menggunakannya untuk tantangan ini sebelumnya - saya sangat dekat, hanya perluL!
di sana).UÆ¡Nœ?L’U
karena saya menerapkanœ?
(dan serupa) untuk bertindak secara modular (seolah-olah mereka menggunakan daftar Jelly). TheN
hanya indeks dengan nilai negatif. Catatan: Saya mengubahJ
keL
- ini hanya karena diberi nomor itu tetap membuat kisaran di bawah-the-kap).Mathematica, 92 byte
Fungsi murni mengambil daftar bilangan bulat negatif sebagai masukan dan mengembalikan daftar bilangan bulat negatif. Kode di atas berisi a
©
, yang tidak benar: itu adalah pengganti untuk simbol 3-byte U + F3DE, yang Mathematica wakili oleh lingkaran dengan titik di dalamnya, dan yang mewakili komposisi permutasi.c=Cycles@{#}&
mendefinisikan fungsi yang mengubah daftar bilangan bulat menjadiCycles
objek yang mewakili permutasi; misalnya,c[{3,4}]
adalah elemen swapping transposisi 3 dan 4 dari daftar.c[i-0~Range~#[[i]]]~Table~{i,l,1,-1}]
mengambil daftar input dan menghasilkan permutasi yang diperlukan untuk membatalkan jenis penyisipan. Kemudianc@{}©##&@@
menyusun semua permutasi ini bersama-sama, dimulai dengan permutasi identitasc@{}
. Akhirnya,Permute[Range[l=Length@#]-1,...]
terapkan permutasi ini ke daftar panjang indeks yang diindeks 0.sumber
@{#}&)@{}©##&@@
terlihat menakutkan.Python 2,
7968 byteTerima kasih kepada Krazor karena telah menghemat 10 byte
Terima kasih kepada TuukkaX untuk menghemat 1 byte
Bekerja dengan menghasilkan gerakan secara terbalik
sumber
a=input();b=range(len(a));print[b.pop(j-a[j]) for j in b[::-1]][::-1]
. Daftar pemahaman ftw!for
, jadi buatlah 65 Saya kira: DJavaScript (ES6),
696563 byteMengganggu input dan output berada dalam urutan yang salah. Sunting: Disimpan 4 byte berkat @Arnauld. Disimpan 2 byte berkat produk @ETH.
sumber
i
, bukan?i
...o=>+b.splice(~o,1)
JavaScript (ES6),
7371 byteDisimpan 2 byte berkat produk ETH
Uji kasus
Tampilkan cuplikan kode
sumber
a=m.map(_=>j++,j=0)
, tapi itu panjang yang sama dan saya yakin Anda sudah mencobanya.j
menjadia.length
daripadaa.length-1
dan akan membutuhkana.splice(--j,0,a.splice(j-m[j],1)[0])
)+a.splice(j-m[j--],1)
Haskell , 85 byte
Cobalah online! Contoh penggunaan:
f [0,1,1,2,1,0]
hasil[4,0,2,1,3,5]
.f x
memanggil fungsi#
dengan daftarx
terbalik dan daftar[length x - 1, length x - 2, ... , 0]
.(n:r)#l
melakukan penyisipan terbalik dengan mengambiln
elemen th secara keluarl
, di manal!!n
menghasilkann
elemen th dantake n l++drop(n+1)l
menghasilkan daftarl
dengann
elemen th dihapus.sumber
perl, 61 byte
Output berakhir di array @o. Contoh dengan larik input sebagai argumen baris perintah:
sumber
Ruby, 49 byte
Lakukan "penyisipan terbalik" pada tempatnya di dalam daftar, dimulai dengan jumlah terbesar.
sumber