Terinspirasi oleh We do tower hopping dan terkait dengan 2D Maze Minus 1D
pengantar
Tugas Anda adalah menemukan jalur terpendek untuk keluar dari labirin array mengikuti aturan yang ditentukan.
Tantangan
Array 1D a dengan n elemen dapat dianggap sebagai labirin yang terdiri dari n titik, di mana titik dengan indeks k terhubung ke titik-titik dengan k + a [ k ] dan k - a [ k ] dengan cara satu arah. Dengan kata lain, Anda dapat melompat maju atau mundur persis langkah [ k ] dari titik dengan indeks k . Poin dengan indeks di luar batas array dianggap di luar labirin.
Untuk menggambarkan ini, pertimbangkan array berikut,
[0,8,5,9,4,1,1,1,2,1,2]
Jika kita berada di elemen ke-5 sekarang, karena elemennya adalah 4, kita dapat melompat 4 langkah ke depan ke elemen 9, atau 4 langkah mundur ke elemen 1. Jika kita melakukan yang terakhir, kita berakhir dengan elemen 0, yang menunjukkan tidak ada gerakan lebih lanjut yang mungkin. Jika kita melakukan yang pertama, karena elemen ke-9 adalah 2, kita dapat memilih untuk melompat ke elemen ke-11, yang merupakan 2, dan kemudian kita dapat melompat lagi ke "elemen ke-13", yang berada di luar batas dari array dan dianggap sebagai jalan keluar ke labirin.
Jadi jika kita mulai dari elemen di tengah, salah satu cara untuk keluar dari labirin adalah melompat 1 langkah mundur, 4 langkah maju, 2 langkah maju dan 2 langkah maju, yang dapat dinyatakan sebagai array [-1,4,2,2]
. Atau Anda dapat mengekspresikannya dengan array [4,8,10,12]
yang mencatat indeks berbasis nol dari semua poin perantara dan akhir (indeks berbasis 1 juga baik-baik saja), atau hanya tanda-tanda [-1,1,1,1]
,.
Lolos dari labirin dari ujung indeks rendah juga OK.
Menggunakan notasi pertama dan mulai dari elemen yang sama, [1,1,1,2,2]
juga merupakan solusi tetapi tidak optimal karena ada 5 langkah, bukannya 4.
Tugasnya adalah untuk menemukan jalur terpendek untuk keluar dari labirin array dan menampilkan jalur. Jika ada lebih dari satu jalur optimal, Anda dapat menampilkan salah satu atau semuanya. Jika tidak ada solusi, Anda harus menampilkan nilai palsu yang dipilih oleh Anda yang dapat dilihat dari jalur yang valid (tidak menghasilkan keluaran sama sekali juga OK).
Untuk mempermudah, jumlah elemen dalam array selalu angka ganjil dan kami selalu mulai dari elemen di tengah.
Uji kasus
Kasing uji menggambarkan berbagai bentuk keluaran, tetapi Anda tidak terbatas pada ini.
Input
Output
[0,8,5,9,4,1,1,1,2,1,2]
[-1,4,2,2]
[2,3,7,1,2,0,2,8,9]
[2,9] (or [2,-5] or [[2,9],[2,-5]])
[0,1,2,2,3,4,4,4,3,2,2,3,0]
[1,-1,1,1]
[0,1,2,2,4,4,6,6,6,6,6,4,2,1,2,2,0]
[]
Spesifikasi
Anda dapat menulis fungsi atau program lengkap.
Array hanya berisi bilangan bulat tidak negatif.
Anda dapat mengambil input dan output melalui formulir standar apa pun , tetapi harap tentukan dalam jawaban Anda formulir mana yang Anda gunakan.
Ini adalah kode-golf , jumlah byte terendah yang menang.
Seperti biasa, celah default berlaku di sini.
sumber
[0,8,5,9,4,1,1,1,2,1,2]
, keluaran[[-1,4,2,2]]
)[1,1,1,-1]
bukannya[-1,1,1,1]
?Jawaban:
JavaScript (ES6), 117 byte
Mengembalikan array titik menengah dan akhir yang diindeks 0, atau array kosong jika tidak ada solusi.
Cobalah online!
Berkomentar
sumber
Sekam , 22 byte
Mengembalikan daftar tanda, atau daftar kosong jika solusi tidak ada. Cobalah online!
Penjelasan
Ini adalah solusi brute force yang memeriksa daftar dengan
-1,0,1
panjang yang bertambah, dan mengembalikan yang pertama yang menghasilkan lompatan keluar dari array. Karena panjangnya minimal, tidak akan berisi 0s.sumber
Python 3 ,
195188179 byteCobalah online!
Edit:
all(..)and s => all(..)*s
,if u not in x => if{u}-x
Eksploitasi sebelumnya
boolean * list == int * list
, yang terakhir menggunakan perbedaan set (set kosong juga palsu).Format output: Array bersarang dari semua jawaban optimal, diberikan sebagai indeks berbasis nol untuk poin tengah dan akhir.
Sebagai contoh:
f([0,8,5,9,4,1,1,1,2,1,2]) == [[4, 8, 10, 12]]
.Algoritma ini adalah BFS sederhana.
s
mencatat semua kemungkinani
jalur-panjangi
iterasi, tidak termasuk indeks yang sudah dikunjungi. Perhatikan bahwa notasi extended star digunakan (ab) karena akses array berulang mahal. Saya menemukan bahwa notasi seperti itu juga dapat mengurangi ruang kosong jika digunakan dengan benar.Saya juga membuat versi rekursif (tetapi lebih lama) dari solusi di atas. Keduanya
s and
danor s
dibutuhkan, jika tidak, tidak akan berhasil.Python 3 , 210 byte
Cobalah online!
sumber
Haskell ,
207202 byte5 byte disimpan berkat BMO .
Cobalah online!
Ini adalah fungsi yang mengambil daftar
Int
sebagai parameter dan mengembalikan daftar jalur di mana setiap jalur adalah daftar lompatan relatif yang diambil untuk keluar dari array.Versi ungolfed:
sumber
C (gcc) , 269 byte
Cobalah online!
Awalnya mencoba pencarian backtracking rekursif, karena menggunakan pernyataan mengambil banyak karakter. Output yang sesuai dengan contoh uji pertama di atas adalah
main
untuk rekursi selalu menyenangkan. Pada akhirnya, meskipun pencarian pertama yang luas non-rekursif dapat dibuat lebih kecil, yang merupakan versi ini. Program ini menggunakan array input sebagai argumen baris perintah, tanpa kawat gigi, misalnya0 8 5 9 4 1 1 1 2 1 2
untuk contoh pertama yang diberikan. Output program pada stdout daftar 1-diindeks indeks array , dibatasi koma dalam urutan terbalik, mulai dari indeks akhir, di luar batas / 'lolos' dan bekerja kembali melalui indeks menengah yang dicapai (tidak menghasilkan output pusat, indeks awal). Program tidak menampilkan kawat gigi di sekitar array dan meninggalkan koma karena terpisahprintf
13,11,9,5,
, misalnya.Jika tidak ada jalan keluar dari labirin array, program tidak menghasilkan apa-apa.
Degolfed dan dijelaskan di bawah ini (sangat degolfed dengan beberapa perubahan untuk dibaca):
Seperti biasa untuk kode C golf, keluaran kompilasi tentu saja akan mencakup dinding peringatan dan catatan yang ramah.
sumber
Perl 5 , -a: 73 byte
(penghitungan gaya lama: 75 byte,
+1
untuka
dan+1
untuk menggantikan-//
dengan-/$/
dan menggunakan$`
untuk$'
)Berikan input array sebagai satu baris pada STDIN misalnya
0 8 5 9 4 1 1 1 2 1 2
mencetak posisi yang dikunjungi dalam urutan terbalik termasuk titik awal, lalu macet
Mencetak apa pun jika tidak ada solusi
Cobalah online!
sumber
Ruby , 102 byte
Cobalah online!
Mengambil labirin input sebagai larik, menghasilkan dengan mencetak jalur keluar secara terbalik, dari pintu keluar ke titik awal (inklusif). Mencetak apa pun jika tidak ada jalan keluar.
Pendekatan ini menyalahgunakan metode peta untuk beralih melalui larik sementara yang menyimpan sejarah jalur, yang terus-menerus diperluas dengan cepat setiap kali ada langkah lain yang mungkin diambil.
Pada prinsipnya, saya bisa menyimpan byte lain dengan menggunakan
return x
alih-alihbreak p x
, tetapi itu berarti mengklaim bahwa nilai kepalsuan saya sama dengan semua sampah mengerikan yang disimpan dib
. Mungkin, ini akan terlalu banyak, bahkan mengingat fleksibilitas yang diizinkan dari output ...Panduan
sumber