Dalam menyortir pancake , satu-satunya operasi yang diizinkan adalah membalik elemen dari beberapa awalan urutan. Atau, pikirkan tumpukan pancake: Kami memasukkan spatula di suatu tempat di tumpukan dan membalik semua pancake di atas spatula.
Sebagai contoh, urutan 6 5 4 1 2 3
dapat diurutkan dengan pertama membalik 6
elemen pertama (seluruh urutan), menghasilkan hasil antara 3 2 1 4 5 6
, dan kemudian membalik 3
elemen pertama , sampai pada 1 2 3 4 5 6
.
Karena hanya ada satu operasi, seluruh proses penyortiran dapat dijelaskan oleh urutan bilangan bulat, di mana setiap bilangan bulat adalah jumlah elemen / pancake untuk menyertakan pr flip. Untuk contoh di atas, urutan pengurutannya adalah 6 3
.
Contoh lain: 4 2 3 1
bisa disortir dengan 4 2 3 2
. Inilah hasil antara:
4 2 3 1
flip 4: 1 3 2 4
flip 2: 3 1 2 4
flip 3: 2 1 3 4
flip 2: 1 2 3 4
Tugas:
Tulis program yang mengambil daftar bilangan bulat dan mencetak urutan penyortiran pancake yang valid.
Daftar untuk disortir dapat berupa daftar yang dipisahkan spasi dari stdin, atau argumen baris perintah. Cetak daftar itu bagaimanapun nyaman, asalkan terbaca.
Ini adalah codegolf!
Edit:
Seperti yang saya katakan di komentar, Anda tidak perlu mengoptimalkan output (menemukan urutan terpendek adalah NP-hard ). Namun , saya baru menyadari bahwa solusi yang murah adalah membuang angka acak sampai Anda mendapatkan hasil yang diinginkan (jenis bogosort [baru?]). Sejauh ini tidak ada jawaban yang telah melakukan ini, jadi saya sekarang menyatakan bahwa algoritma Anda tidak harus bergantung pada keacakan (pseudo-) .
Saat Anda semua menendang diri sendiri, inilah varian bogopancakeort di Ruby 2.0 (60 karakter), untuk digosokkan ke:
a=$*.map &:to_i
a=a[0,p(v=rand(a.size)+1)].reverse+a[v..-1]while a!=a.sort
4 3 2 1
bukan4 2 3 1
Jawaban:
GolfScript, 34/21 karakter
(Terima kasih @PeterTaylor untuk memotong 4 karakter)
Tes online
Versi yang lebih pendek, 21 karakter hanya berfungsi untuk daftar dengan item unik
Tes online
Kedua versi menghasilkan solusi sub-optimal.
Penjelasan untuk solusi yang lebih pendek:
Ini menggunakan algoritma yang berbeda untuk sebagian besar yang diposting. Pada dasarnya itu mengambil elemen terkecil dari daftar, dan dengan dua membalik bergerak ke depan, menjaga urutan elemen lainnya.
Untuk memindahkan elemen ke-n ke depan:
Itu mengulangi operasi ini untuk setiap elemen secara berurutan, dan berakhir dengan daftar diurutkan terbalik. Kemudian membalik seluruh daftar untuk membiarkannya sepenuhnya diurutkan.
Sebenarnya algoritma ini adalah variasi dari solusi Python 90-char (milik saya sendiri, tentu saja):
sumber
&
di mana saja, sehingga Anda harus dapat menggantikans
sementara&
dan menghapus spasi.^
sebagai variabel dalam tantangan fibonacci;) Terima kasih atas tipnya!3 2 1
saya mendapatkan131211
yang tidak benar.2 1 1
tidak bisa disortir lagi.Python,
9190 karakterBalikkan pancake terbesar ke atas, lalu balikkan seluruh tumpukan. Angkat pancake terbesar dari bawah dan ulangi.
i
adalah indeks pancake terbesar.L=L[:i:-1]+L[:i]
membaliki+1
pancake, membaliklen(L)
pancake, lalu menjatuhkan pancake terakhir.sumber
print
wont membuat output tidak terbaca (1 byte disimpan :)Ruby 1.9 -
1098879 karakterVersi yang jauh lebih ringkas berdasarkan pada solusi python Keith:
Versi asli:
Jika Anda tidak peduli dengan operasi palsu (membalikkan tumpukan ukuran 1, atau membalik tumpukan yang sama dua kali berturut-turut) Anda bisa membuatnya sedikit lebih pendek (96 karakter):
Mengambil daftar yang tidak disortir sebagai argumen baris perintah. Contoh penggunaan:
sumber
GolfScript,
3129 karakterSolusi GolfScript lainnya, juga dapat diuji secara online .
Versi sebelumnya:
Bagaimana cara kerjanya: itu membalik item terbesar ke atas dan kemudian ke tempat terakhir dalam daftar. Karena sekarang berada di posisi yang benar, kami dapat menghapusnya dari daftar.
sumber
Perl,
103100 karakterMengharapkan input pada baris perintah.
Solusi yang dicetaknya jelas kurang optimal. (Saya memiliki program dengan output yang jauh lebih baik sekitar 24 karakter yang lalu ....)
Logikanya agak menarik. Dimulai dengan katalog indeks setiap item, apakah itu dalam urutan. Kemudian beralih melalui katalog ini dari kanan ke kiri. Jadi menerapkan flip melibatkan penyesuaian indeks di bawah nilai cutoff, bukannya benar-benar memindahkan nilai. Setelah beberapa penyelesaian saya juga berhasil menyelamatkan beberapa karakter dengan melakukan kedua membalik per iterasi secara bersamaan.
sumber
Python 2 (254)
Pencarian BFS sederhana, beberapa hal digarisbawahi, mungkin bisa dikompresi lebih banyak tanpa mengubah gaya pencarian. Semoga ini menunjukkan mungkin bagaimana memulai bermain golf sedikit (terlalu banyak untuk di komentar sederhana).
Menggunakan:
(2 spasi = tab)
sumber
sys.exit()
dengan1/0
(dalam codegolf Anda tidak pernah peduli dengan apa yang dicetak di stderr ...).print s[::-1];1/0
untuk mencukur beberapa karakter.4 2 3 1
memberi2 3 2 4
, yang sebenarnya tidak valid.4 2 3 1
->2 4 3 1
->3 4 2 1
->4 3 2 1
->1 2 3 4
Python2: 120
Itu tidak efisien: ia tidak akan menemukan urutan penyortiran terbaik, dan urutan yang diberikan bahkan dapat berisi no-ops (yaitu hanya membalik elemen pertama), namun hasilnya valid.
Outputnya diberikan dalam bentuk:
Yang harus dibaca sebagai urutan membalik:
n_1 n_2 n_3 n_4 n_5 n_6 ...
. Jika Anda ingin mendapatkan output seperti:n_1 n_2 n_3 n_4 n_5 n_6 ...
Cukup tambahkan koma dalam
print
pernyataan.sumber
[:i][::-1]
->[i-1::-1]
,[:u][::-1]
->[u-1::-1]
, menghemat 2 karakterL[:i]=L[i-1::-1];L[:u]=[u-1::-1]
simpan 3 karakter lagiPython - 282 karakter
Golf kode pertama saya; Saya tidak punya ilusi bahwa saya akan menang , tetapi saya bersenang-senang. Memberi segalanya nama-nama satu karakter tentu membuatnya menakutkan untuk dibaca, izinkan saya memberi tahu Anda! Ini dijalankan dari baris perintah, contoh implementasi di bawah ini:
Tidak ada yang khusus atau inventif tentang cara saya melakukan hal ini, tetapi FAQ menyarankan untuk memposting versi non-golf untuk pembaca yang tertarik, jadi saya melakukannya di bawah ini:
Algoritma dasar yang saya gunakan adalah yang disebutkan dalam artikel wiki yang tertaut dalam pertanyaan :
sumber
t=p[:x]
t=t[::-1]
(16+ indentasi) dapat dikurangi menjadit=p[:x][::-1]
(13), atau bahkant=p[x-1::-1]
(12). Sebariskan semua yang Anda bisa:p=p[x-1::-1]+p[x:]
len(a)-n
menjadi-n
;p=p[-n-1::-1]+p[-n:]
. Lebih lanjut golf dengan menggunakan operasi yang tepat:p=p[~n::-1]+p[-n:]
map(int,sys.argv[1:])
lakukan apa yang dilakukan 6 baris pertama Anda sekarang.i=x=g=0
berfungsi, tetapi Anda harus memangkas jumlah variabel. Saya akan memberi Anda satu hal: Ini adalah satu-satunya entri python yang paling saya mengerti: DC # -
264 259 252237 karakterMenggunakan algoritma paling sederhana dan menghasilkan output yang benar tanpa membalik berlebihan. Bisa mencukur 7 karakter jika saya mengizinkannya memasukkan 1 (non-flips) dalam output, tapi itu jelek.
Saya menggunakan
goto
untuk golf maksimum. Juga menyimpan beberapa karakter dengan membiarkannya melakukan non-flip (tetapi tidak mencetaknya).Peningkatan terbaru: menjaga array input sebagai string alih-alih mengonversi ke int.
Tidak Terkumpul:
Inilah solusi awal saya, ungolfed (264 karakter golf):
sumber
Haskell ,
7271 byteCobalah online! Menemukan maksimum, membalikkannya ke belakang dan secara rekursif mengurutkan daftar yang tersisa.
Sunting: -1 byte berkat BMO
sumber
Perl 5.10 (atau lebih tinggi), 66 byte
Termasuk
+3
untuk-n
Theuse 5.10.0
untuk membawa bahasa ke level perl 5.10 dianggap gratisJalankan dengan input sebagai satu baris pada STDIN:
Urutkan daftar dengan berulang kali menemukan inversi, membalikkannya ke depan lalu membalikkan inversi dan membalikkan semuanya kembali ke posisi semula. Dan itu setara dengan bertukar inversi jadi saya tidak perlu membalikkan (yang canggung pada string karena akan membalikkan digit nilai yang dikonversi misalnya
12
ke21
)sumber
C # - 229
versi yang mudah dibaca
sumber