Tujuan Anda adalah untuk menulis sebuah program yang menciptakan random 10x10 peta menggunakan 0
, 1
dan 2
, dan menemukan jalur terpendek dari atas-kiri ke kanan bawah, dengan asumsi bahwa:
0 mewakili bidang rumput: siapa pun bisa berjalan di atasnya;
1 melambangkan dinding: Anda tidak dapat melewatinya;
2 mewakili portal: saat memasuki portal, Anda dapat pindah ke portal lain di peta.
Spesifikasi:
- Elemen kiri atas dan kanan bawah harus 0 ;
- Saat membuat peta acak, setiap bidang harus memiliki peluang 60% menjadi 0 , 30% menjadi 1, dan 10% menjadi 2 ;
- Anda dapat bergerak di bidang yang bersebelahan (bahkan yang diagonal);
- Program Anda harus menampilkan peta dan jumlah langkah dari jalur terpendek;
- Jika tidak ada jalur yang valid yang mengarah ke bidang kanan bawah, program Anda harus menampilkan peta saja;
- Anda dapat menggunakan sumber daya apa pun yang Anda inginkan;
- Kode terpendek menang.
Langkah-langkah perhitungan:
Langkah adalah gerakan aktual; setiap kali Anda mengubah bidang, Anda menambah penghitung.
Keluaran:
0000100200
0100100010
1000000111
0002001000
1111100020
0001111111
0001001000
0020001111
1100110000
0000020100
9
code-golf
path-finding
maze
Vereos
sumber
sumber
Jawaban:
GolfScript, 182 karakter
Contoh:
sumber
Mathematica (344)
Bonus: menyoroti jalur
Saya membuat grafik dari semua film yang mungkin untuk simpul tetangga dan menambahkan semua kemungkinan "teleport".
sumber
Mathematica,
208202 karakterBerbasis pada solusi David Carraher dan ybeltukov. Dan terima kasih atas saran ybeltukov.
sumber
n/n
alih-alihn/10
:)〚 〛
untuk kurung (itu adalah simbol unicode yang benar)Norm[# - #2] & @@ # < 2 || # \[Union] u == u &
Norm[# - #2] & @@ # < 2
berarti jarak antara dua titik kurang dari 2, sehingga mereka harus berdekatan.# ⋃ u == u
berarti kedua poin ada di dalam kamu.Python 3, 279
Beberapa varian Dijkstra. Jelek, tapi main golf sebanyak mungkin ...
Contoh Jalankan
sumber
Mathematica
316 279275Objek dasarnya adalah array 10x10 dengan sekitar 60 0, 30 1 dan 10 2. Array digunakan untuk memodifikasi 10x10
GridGraph
, dengan semua sisi terhubung. Node-node yang berhubungan dengan sel-sel yang memegang 1 dalam array dihapus dari grafik. Node-node "holding 2's" semuanya terhubung satu sama lain. Kemudian Jalur Terpendek dicari antara titik 1 dan titik 100. Jika jalur seperti itu tidak ada, peta dikembalikan; jika jalur tersebut memang ada, peta dan panjang jalur terpendek akan ditampilkan.Contoh Run :
sumber
Python (1923)
Mundur PencarianDiakuinya bukan yang terpendek atau paling efisien, meskipun ada beberapa memoisasi yang ada.
sumber
JavaScript (541)
Pembuatan grafik terjadi pada lima baris pertama.
f
berisi kolom,p
pegang portal. Pencarian aktual diimplementasikan melalui BFS.Contoh output:
sumber
Python 3 (695)
Dijkstra!
Contoh output:
sumber
Python, 314
Ini implementasi Bellman-Ford yang menjijikkan. Algoritma ini adalah O (n ^ 6)! (Yang tidak apa-apa untuk n = 10)
sumber
print '\n'.join(map(str,a))
; Saya lakukanprint a
demi golf.r*10
memiliki 100 elemen).