Dengan jendela yang mirip dengan yang digambarkan di bawah ini, Anda diberikan daftar string, yang ingin Anda masukkan dalam urutan abjad.
Seperti yang ditunjukkan, Anda memiliki lima operasi:
- Move up [U] - memindahkan string yang dipilih ke atas satu tempat
- Move down [D] - memindahkan string yang dipilih ke satu tempat
- Pindahkan dulu [F] - pindahkan string yang dipilih ke atas daftar
- Pindahkan [L] terakhir - memindahkan string yang dipilih ke bagian bawah daftar
- Reverse [R] - membalik urutan daftar
Dengan menggunakan STDIN, terima nomor (berapa banyak string), diikuti oleh daftar string yang tidak diurutkan. Setiap string terdiri dari 2-99 huruf bahasa Inggris huruf kecil. (Contoh di atas tidak akan menjadi input yang valid.)
Dengan menggunakan STDOUT, cetak cara untuk mengatur daftar. Pertama, sebutkan item untuk dipilih, dan kemudian operasi untuk dilakukan untuk menempatkan daftar dalam urutan abjad.
Sebagai contoh: February U December F May D D June D R D...
Penjelasan: Klik Februari, naikkan 1. Pilih Desember, pindah ke atas. Mungkin, gerakkan ke bawah dua kali. June, mundur satu kali, balik daftar, turun lagi ...
Karena jelas ada banyak solusi yang valid, Anda harus memilih yang sesingkat mungkin. Yaitu, pilih metode dengan jumlah operasi paling sedikit (7 pada contoh di atas).
Jika ada kaitan antara output yang benar dengan input, atasi dalam urutan berikut.
Pilih satu dengan pilihan string paling sedikit (4 pada contoh di atas).
Pilih satu dengan operasi paling sedikit, hitung operasi identik berurutan (pada satu string) sebagai satu (6 dalam contoh di atas).
Pilih satu dengan output terpendek (paling sedikit jumlah karakter, penghitungan spasi).
Pilih satu dengan output yang muncul lebih dulu menurut abjad.
Ini adalah kode-golf; pengajuan terpendek yang selalu menghasilkan output yang benar akan menang.
Contohnya
- DI
2 zz abc
- DI LUAR
zz D
- DI LUAR
- DI
3 cc bb aa
- DI LUAR
aa R
- DI LUAR
- DI
4 abc def cd ccc
- DI LUAR
abc L R
- DI LUAR
- DI
6 rr mm nn oo qq pp
- DI LUAR
pp U rr L
- DI LUAR
Contoh tambahan (disediakan oleh Scott Leadley, setiap kesalahan adalah milik saya dan bukan milik ypnypn)
Beberapa kasus sulit:
- IN => OUT
6 xx aa dd bb ee cc
=>dd L ee L xx L
7 aa bb ee cc dd ff gg
=>ee D D
8 dd ww aa bb cc xx yy zz
=>ww D D D dd D D D
- ( bukan jumlah minimum gerakan, yang akan menjadi
cc F bb F aa F
)
- ( bukan jumlah minimum gerakan, yang akan menjadi
Permutasi 4 item aa bb cc dd
dengan panjang jalur sortir> 1:
- IN => OUT
4 aa cc dd bb
=>bb F D
4 aa dd cc bb
=>aa L R
4 bb aa dd cc
=>aa F cc U
4 bb dd aa cc
=>aa F cc U
4 bb dd cc aa
=>bb D D R
4 cc aa bb dd
=>cc D D
4 cc aa dd bb
=>bb F aa F
4 cc bb aa dd
=>dd F R
4 cc bb dd aa
=>dd F R
4 cc dd aa bb
=>bb F aa F
4 cc dd bb aa
=>cc D R
4 dd aa cc bb
=>aa L R
4 dd bb aa cc
=>cc F D R
4 dd bb cc aa
=>bb D R
4 dd cc aa bb
=>aa D R
Variasi pada tema, 4 item di aaaaa bbbb ccc dd
mana panjang string membuat perbedaan:
- IN => OUT
4 ccc dd aaaaa bbbb
=>ccc L dd L
4 bbbb aaaaa dd ccc
=>bbbb D dd D
4 bbbb dd aaaaa ccc
=>dd L bbbb D
4 ccc aaaaa dd bbbb
=>ccc L dd L
4 ccc dd bbbb aaaaa
=>dd F R
4 dd bbbb ccc aaaaa
=>ccc R D
4 dd ccc aaaaa bbbb
=>bbbb R D
A
yang tidak ada.ddkP
, D =ddp
, F =ddggP
, L =ddGp
, R =:g/^/m0
. : PJawaban:
Python 2 -
593521Ini sangat kasar dengan beberapa efisiensi sehingga benar-benar akan selesai. Daftar 6 item yang saya uji dengan mengambil sekitar 5 detik di laptop saya.
Perhatikan bahwa saya mengabaikan nomor di input. Saya merasa itu tidak berguna.
Ugh, saya baru sadar saya tidak menangani banyak operasi dengan nilai yang sama dengan benar. Saya akan mencoba memperbaikinya.
sumber
Ruby 2.0
Dengan set operator [U, D, F, L], jumlah string yang paling sedikit dipilih untuk mengurutkan daftar adalah jumlah item dalam daftar dikurangi urutan umum terpanjang. Untuk menambahkan operator R, balikkan string dan terapkan aturan yang sama. Sayangnya, meminimalkan string yang dipilih tidak sama dengan meminimalkan jumlah operasi. Misalnya, untuk input
8 dd ww aa bb cc xx yy zz
, jawaban yang benar adalahww D D D dd D D D
, tetapi jumlah operasi paling sedikit (yang memenuhi kriteria lain dalam pertanyaan) adalahcc F bb F aa F
. Ini berarti bahwa bagian yang jauh lebih besar dari set jalur pengurutan yang mungkin perlu dieksplorasi.Solusi ini menggunakan strategi pencarian mendalam-pertama dan pemangkasan alpha-beta. Sangat penting untuk menurunkan nilai alpha dengan cepat untuk meminimalkan kedalaman pencarian, jika tidak pohon pencarian akan meledak secara eksponensial. Misalnya untuk menentukan jalur pengurutan dengan skor minimum untuk contoh pengantar OP, mengurutkan bulan dalam urutan kalender ke urutan leksikal, mungkin akan memakan waktu beberapa dekade dengan metode penilaian saat ini dalam program ini. Program ini menemukan jumlah minimum string yang dipilih, 8, sangat cepat. Sayangnya, itu masih menyisakan pohon besar untuk dilalui.
Saya menggunakan gnome sort sebagai fungsi penilaian saya karena:
Angka 4 sudah cukup. Yang lainnya adalah bonus.
Untuk pencarian mendalam-pertama, urutan operasi dieksplorasi memiliki dampak signifikan pada waktu pencarian. Karena setiap set item N yang tidak kosong dapat diurutkan dengan operasi ≤ N-1 F (pertama) atau L (ast), operasi tersebut dicoba terlebih dahulu.
Itu melewati perl test TAP ini :
sumber