Diberikan urutan angka, temukan jumlah minimum lompatan untuk pergi dari posisi awal ke akhir dan kembali ke posisi awal lagi.
Setiap elemen dari urutan menunjukkan jumlah maksimum gerakan yang dapat bergerak dari posisi itu.
Di posisi mana pun, Anda dapat melakukan lompatan pada gerakan maks k, di mana k adalah nilai yang disimpan di posisi itu. Setelah mencapai akhir, Anda hanya dapat menggunakan posisi tersebut untuk melompat yang belum pernah digunakan sebelumnya untuk melompat.
Input akan diberikan sebagai urutan angka yang dipisahkan oleh spasi tunggal. Output harus berupa angka tunggal yang merupakan jumlah minimum lompatan yang digunakan. Jika tidak mungkin untuk pergi ke ujung dan kembali ke posisi awal, maka cetak -1
Memasukkan:
2 4 2 2 3 4 2 2
Keluaran:
6 (3 untuk mencapai ujung dan 3 untuk kembali)
Memasukkan
1 0
Keluaran
-1
Catatan
- Anggap semua angka urutannya adalah non-negatif
EDIT 1
Garis "Jadi, harus jelas bahwa seseorang selalu dapat melompat dari posisi terakhir." mungkin membingungkan, jadi saya menghapusnya dari pertanyaan. Itu tidak akan berpengaruh pada pertanyaan.
Kriteria Menang:
Pemenang akan menjadi orang dengan kode terpendek.
sumber
Thus, it should be clear that one can always jump from the last position.
- bukankah1 0
sampel balik?Jawaban:
APL (Dyalog), 116
Uji kasus
Pendekatan
Pendekatannya adalah pencarian brute force menggunakan fungsi rekursif.
Mulai dari posisi 1, tetapkan nilai pada posisi saat ini ke 0 dan hasilkan array posisi yang dapat dilompati dari posisi saat ini. Pass posisi baru dan array yang dimodifikasi itu sendiri. Kasus dasar adalah ketika nilai pada posisi saat ini adalah 0 (tidak bisa melompat) atau mencapai akhir.
Kemudian, untuk setiap array yang dihasilkan, balikkan dan lakukan pencarian lagi. Karena posisi melompat diatur ke 0, kita tidak bisa melompat dari sana lagi.
Untuk array yang kami capai akhirnya, cari yang memiliki jumlah minimum 0's. Dengan mengurangkannya, angka 0 pada larik awal memberikan jumlah lompatan aktual yang dilakukan.
sumber
Mathematica,
197193 karakterPaksaan.
sumber
Mathematica 351
[Catatan: Ini belum sepenuhnya bermain golf; Juga, input perlu disesuaikan agar sesuai dengan format yang diperlukan. Dan aturan no-jumping-on-the-same-position-2x perlu diimplementasikan. Ada juga beberapa masalah pemformatan kode yang perlu diatasi. Tapi ini awal.]
Grafik dibuat dengan simpul yang sesuai dengan setiap posisi, yaitu setiap digit input mewakili lompatan.
DirectedEdge[node1, node2]
menandakan bahwa adalah mungkin untuk melompat dari node1 ke node 2. Jalur terpendek ditemukan dari awal hingga akhir dan kemudian dari ujung ke awal.Pemakaian
sumber
Python 304
Saya pikir pendekatan baru ini menyelesaikan (saya harap!) Semua masalah tentang kasus [2,0] dan yang serupa:
Dalam versi ini urutan input dilalui (jika mungkin) sampai akhir dan kemudian kita memulai proses lagi dengan urutan terbalik. Sekarang kita dapat menjamin bahwa untuk setiap solusi yang valid salah satu lompatan mendarat pada elemen terakhir.
Ini adalah versi golfnya:
Dan beberapa contoh:
sumber
R - 195
Simulasi:
De-golf:
sumber
Python 271
ini solusi saya:
Contoh:
Dan ini adalah versi golf (sebagian sekarang):
Beberapa contoh:
sumber
Ruby - 246
Simulasi:
sumber
Ruby - sekitar 700 golf. Saya memulai versi golf, dengan nama karakter tunggal untuk variabel dan metode, tetapi setelah beberapa saat saya lebih tertarik pada algoritma daripada golf, jadi berhenti mencoba mengoptimalkan panjang kode. Saya juga tidak khawatir tentang mendapatkan string input. Usaha saya di bawah.
Untuk membantu Anda memahami cara kerjanya, saya menyertakan komentar yang menunjukkan bagaimana string tertentu (u = "2 1 4 3 0 3 4 4 3 5 0 3") dimanipulasi. Saya menghitung kombinasi "batu di sungai" yang tersedia untuk naik. Ini diwakili dengan string biner. Saya memberi contoh 0b0101101010 di komentar dan menunjukkan bagaimana itu akan digunakan. Angka 1 sesuai dengan posisi batu yang tersedia untuk perjalanan awal; 0 untuk perjalanan kembali. Untuk setiap alokasi tersebut, saya menggunakan pemrograman dinamis untuk menentukan jumlah minimal hop yang diperlukan di setiap arah. Saya juga melakukan beberapa optimasi sederhana untuk menghilangkan beberapa kombinasi sejak dini.
Saya sudah menjalankannya dengan string yang diberikan dalam jawaban lain dan mendapatkan hasil yang sama. Berikut beberapa hasil lain yang saya peroleh:
Saya akan tertarik mendengar apakah orang lain mendapatkan hasil yang sama untuk string ini. Performanya lumayan bagus. Misalnya, butuh waktu kurang dari satu menit untuk mendapatkan solusi untuk string ini:
"3 4 3 0 4 3 4 4 5 3 5 3 0 4 3 3 0 3 4 5 3 2 0 3 4 1 6 3 2 0 4 5 3 2 0 3 4 1 6 3 0 4 3 4 4 5 0 1"
Kode berikut.
sumber
Haskell,
173166 byte, 159 byte di GHCiIni versi normal:
impor Data.List
Inilah jawaban GHCi (letakkan baris satu per satu):
Hanya bruteforce. Hasilkan jawaban yang mungkin. (Yaitu permutasi [0..n-1] dengan nol dan elemen berikut dijatuhkan. Kemudian periksa apakah jawabannya benar. Dapatkan panjang minimum dan tambahkan satu. (Karena nol di depan dan di belakang dihapus).
Cara menggunakan:
j[3,4,0,0,6]
->3
sumber
Data.List.permutations
tidak bekerja di GHC, tetapi hanya di GHCi. Menurut Panduan kami untuk Aturan Golf di Haskell , Anda harus menambahkan impor atau menandai jawaban Anda sebagai "Haskell GHCi". Opsi pertama umumnya disukai oleh pegolf Haskell di situs ini.a<-permutations[0..t l-1],let f=takeWhile(/=0)a
, Anda bisa menulisf<-map(takeWhile(/=0))(permutations[0..t l-1])
, yang lagi-lagi bisa di-golf-kanf<-fst.span(>0)<$>permutations[0..t l-1]
. Dengan ini, Anda kembali ke 166 byte bahkan dengan menambahkan impor: Coba online!