Tantangan
Kode terpendek berdasarkan jumlah karakter untuk membantu Robot menemukan anak kucing dalam langkah seminimal mungkin.
Para pegolf, ini adalah masa krisis - Kitten hilang dan ini tugas Robot untuk menemukannya! Robot harus mencapai Kitten di jalur sesingkat mungkin. Namun, ada banyak kendala dalam cara Robot, dan dia membutuhkan Anda untuk memprogram solusi untuknya.
Robot dulu punya program melakukannya untuknya, tetapi program itu hilang dan Robot tidak punya cadangan :(.
Robot runtime bukan yang terbaik, dan karakter paling sedikit Robot harus membaca dari kode sumber, paling sedikit waktu yang dihabiskan untuk memproses, dan itu berarti Kitten akan ditemukan lebih cepat!
Memori robot berisi peta lokasi dia saat ini dengan puncak mewakili Utara, bawah mewakili Selatan, kanan mewakili Timur dan kiri mewakili Barat. Robot selalu berada di ruang persegi panjang dengan ukuran yang tidak diketahui dikelilingi oleh dinding, diwakili oleh #
dalam peta radarnya. Area Robot dapat berjalan diwakili oleh sebuah ruang .
Radar robot juga memindai banyak hambatan di ruangan dan menandainya dalam berbagai huruf ASCII. Robot tidak bisa berjalan melewati rintangan itu. Radar akan menandai Kitten sebagai karakter ASCII khusus K
, sementara lokasi Robot ditandai dengan R
.
Sistem navigasi robot bekerja seperti ini: Dia dapat memahami duo arah dan jumlah unit pergerakan yang harus dia N 3
kunjungi - misalnya, berarti 'pergi ke utara 3 unit gerakan'. Peta radar robot dibuat sedemikian rupa sehingga unit gerakan adalah satu karakter ASCII. Robot hanya dapat berjalan dalam 4 arah dan tidak dapat melakukan perjalanan secara diagonal.
Tugas Anda, Kitten saver yang berani, adalah membaca peta radar Robot satu kali, dan menampilkan jumlah arah yang paling sedikit, dengan jarak perjalanan unit pergerakan yang paling sedikit. Robot dijamin memiliki setidaknya satu jalur ke Kitten.
Untuk memastikan Robot tidak membuang-buang waktu menjalankan program yang tidak berfungsi yang tidak akan membantu Robot menemukan Kucing, saya mendorong Anda, berani Penabung Kucing, untuk menggunakan hasil dari program Robot yang lalu untuk memastikan tidak ada waktu yang terbuang untuk menemukan Kucing!
Uji kasus
Input:
######################
# d 3 Kj #
# #
# R #
# q #
######################
Output:
E 13
N 2
Input:
######################
# d r 3 Kj #
# p p #
# T X #
# q s t #
# #
# R o d W #
# #
# g t U #
# #
######################
Output:
N 1
E 10
N 4
E 2
Input:
######################
# spdfmsdlwe9mw WEK3#
# we hi #
# rdf fsszr#
# sdfg gjkti #
# fc d g i #
# dfg sdd #
# g zfg #
# df df #
# xcf R#
######################
Output:
N 1
W 9
N 5
E 4
N 1
E 4
N 1
Hitungan kode termasuk input / output (yaitu program lengkap).
sumber
Jawaban:
C ++
1002899799 charsCatatan membutuhkan penggunaan C ++ 0x untuk menghilangkan ruang antara>> dalam template.
Ia menemukan rute dengan jumlah belokan minimum.
Ini
Dijkstra's Algorithm
untuk memecahkan masalah jalur terpendek.Untuk membedakan antara beberapa rute ukuran yang sama, garis lurus panjang memiliki bobot lebih sedikit daripada banyak jalur pendek (ini mendukung rute dengan putaran lebih sedikit).
Dalam bentuk yang lebih mudah dibaca:
sumber
Scala 2.8 (451 karakter)
... tapi itu tidak menyelesaikan ikatan yang mendukung jumlah arahan paling sedikit (meskipun ia menemukan jumlah langkah paling sedikit).
Scala 2.8, 642 karakter, memecahkan ikatan dengan benar;
Itu menemukan jalan yang lebih pendek untuk contoh kedua daripada yang diberikan dalam masalah:
sumber
Python 2.6 (504 karakter)
sumber
Python 2.6 (535 karakter)
Buka paket ke implementasi A * yang sangat dianiaya. Baca stdin. Mencari solusi dengan jarak total minimal. Memutuskan ikatan dengan memilih jumlah arahan yang minimal. Daftar bergerak ke stdout. Menemukan anak kucing.
Dibongkar :
Sumber telah secara manual anti-golf di beberapa tempat untuk mendapatkan representasi terkompresi yang lebih kecil. Misalnya, lingkaran untuk atas arah kompas tidak dibuka.
sumber
c ++ - 681 karakter yang diperlukan
Pertama menggantikan semua hambatan pada peta menjadi
#
s (dan mengubah nilai-nilaiK
danR
, untuk meninggalkan ruang kepala di ruang karakter untuk jalur yang sangat panjang. Kemudian itu mencoret-coret peta. Proses berulang menandai semua kotak yang dapat diakses secara berturut-turut sampai itu dapat mencapai anak kucing dalam satu langkah. Setelah itu menggunakan rutinitas pemeriksaan aksesibilitas yang sama untuk menemukan string posisi yang mengarah kembali ke awal dalam instruksi minimal. Instruksi ini dimuat ke dalam string dengan pra-pending, sehingga mereka cetak dengan urutan yang benar.Saya tidak berniat untuk bermain golf lebih jauh karena tidak menyelesaikan ikatan dengan benar dan tidak dapat dengan mudah diadaptasi untuk melakukannya.
Gagal menyala
memproduksi
Versi lebih atau kurang terbaca:
sumber
Ruby - 539 karakter
Bisa dilakukan dengan banyak perbaikan, tetapi bekerja untuk langkah-langkah terpendek serta arah.
sumber
Ruby - 648 karakter
Satu lagi yang gagal paling sedikit tes arah karena saya tidak bisa memikirkan cara mudah untuk menanamkannya dalam A *.
sumber