Pengguna CarpetPython memposting pandangan baru tentang masalah ini yang menempatkan fokus yang jauh lebih besar pada solusi heuristik, karena peningkatan ruang pencarian. Saya pribadi berpikir bahwa tantangan jauh lebih baik daripada tantangan saya, jadi pertimbangkan untuk mencoba yang itu!
Balap vektor adalah permainan adiktif yang bisa dimainkan dengan pena dan selembar kertas yang dikuadratkan. Anda menggambar arena pacuan kuda sewenang-wenang di atas kertas, menentukan awal dan akhir dan kemudian Anda mengarahkan mobil berukuran titik Anda dengan cara berbasis giliran. Selesaikan secepat mungkin, tetapi berhati-hatilah agar tidak berakhir di dinding!
Jalanan
- Peta adalah kisi dua dimensi, di mana setiap sel memiliki koordinat bilangan bulat.
- Anda memindahkan sel-sel kisi.
- Setiap sel kisi adalah bagian dari lintasan atau dinding.
- Satu sel track yang tepat adalah koordinat awal.
- Setidaknya satu sel trek ditetapkan sebagai tujuan. Mendarat pada salah satu dari ini melengkapi balapan. Banyak sel tujuan tidak selalu terhubung.
Mengemudikan Mobil
Mobil Anda mulai dari koordinat yang diberikan dan dengan vektor kecepatan (0, 0)
. Di setiap belokan, Anda dapat menyesuaikan setiap komponen kecepatan dengan ±1
atau membiarkannya apa adanya. Kemudian, vektor kecepatan yang dihasilkan ditambahkan ke posisi mobil Anda.
Sebuah gambar dapat membantu! Lingkaran merah adalah posisi terakhir Anda. Lingkaran biru adalah posisi Anda saat ini. Kecepatan Anda adalah vektor dari lingkaran merah ke biru. Pada gilirannya ini, tergantung pada bagaimana Anda menyesuaikan kecepatan Anda, Anda dapat pindah ke lingkaran hijau mana saja.
Jika Anda mendarat di dinding, Anda langsung kalah.
Tugas Anda
Anda dapat menebaknya: tulis sebuah program yang, diberi lintasan pacuan kuda sebagai input, mengarahkan mobil ke salah satu sel gawang dalam beberapa putaran sebanyak mungkin. Solusi Anda harus dapat menangani trek sewenang-wenang dengan cukup baik dan tidak secara khusus dioptimalkan terhadap kasus uji yang disediakan.
Memasukkan
Ketika program Anda dipanggil, baca dari stdin :
target
n m
[ASCII representation of an n x m racetrack]
time
target
adalah jumlah belokan maksimum yang dapat Anda ambil untuk menyelesaikan trek, dan time
merupakan total waktu anggaran Anda untuk trek, dalam detik (tidak harus bilangan bulat). Lihat di bawah untuk detail tentang waktu.
Untuk trek yang dibatasi baris baru, karakter berikut digunakan:
#
- dindingS
- yang start*
- sebuah tujuan.
- semua sel trek lainnya (yaitu jalan)
Semua sel di luar n x m
grid yang disediakan tersirat sebagai dinding.
Asal koordinat berada di sudut kiri atas.
Ini adalah contoh sederhana:
8
4.0
9 6
###...***
###...***
###...***
......###
S.....###
......###
Menggunakan pengindeksan berbasis 0, koordinat awal adalah (0,4)
.
Setelah setiap gerakan, Anda akan menerima masukan lebih lanjut:
x y
u v
time
Dimana x
, y
, u
, v
semua bilangan bulat 0 berbasis. (x,y)
adalah posisi (u,v)
Anda saat ini dan kecepatan Anda saat ini. Catat itu x+u
dan / atau y+v
bisa di luar batas.
time
apa pun yang tersisa dari anggaran waktu Anda, dalam hitungan detik. Jangan ragu untuk mengabaikan ini. Ini hanya untuk peserta yang benar-benar ingin membawa implementasi mereka ke batas waktu.
Saat permainan berakhir (karena Anda mendarat di dinding, keluar dari batas, melewati target
putaran, kehabisan waktu, atau mencapai tujuan), Anda akan menerima garis kosong.
Keluaran
Untuk setiap belokan, tulis ke stdout :
Δu Δv
mana Δu
dan Δv
setiap adalah salah satu -1
, 0
, 1
. Ini akan ditambahkan ke (u,v)
untuk menentukan posisi baru Anda. Hanya untuk memperjelas, petunjuknya adalah sebagai berikut
(-1,-1) ( 0,-1) ( 1,-1)
(-1, 0) ( 0, 0) ( 1, 0)
(-1, 1) ( 0, 1) ( 1, 1)
Solusi optimal untuk contoh di atas adalah
1 0
1 -1
1 0
Perhatikan bahwa pengontrol tidak melekat pada stderr , jadi Anda bebas menggunakannya untuk segala jenis hasil debug yang mungkin Anda perlukan saat mengembangkan bot Anda. Harap hapus / komentari output apa pun dalam kode yang Anda kirimkan.
Bot Anda mungkin membutuhkan setengah detik untuk merespons di setiap belokan. Untuk belokan yang membutuhkan waktu lebih lama, Anda akan memiliki anggaran waktu (per track) target/2
detik. Setiap kali belokan membutuhkan waktu lebih dari setengah detik, waktu tambahan akan dikurangkan dari anggaran waktu Anda. Ketika anggaran waktu Anda mencapai nol, balapan saat ini akan dibatalkan.
Baru: Untuk alasan praktis, saya harus menetapkan batas memori (karena memori tampaknya lebih membatasi daripada waktu untuk ukuran trek yang masuk akal). Oleh karena itu, saya harus membatalkan semua uji coba di mana pembalap menggunakan lebih dari 1GB memori yang diukur oleh Process Explorer sebagai Private Bytes .
Mencetak gol
Ada patokan 20 lagu. Untuk setiap lagu:
- Jika Anda menyelesaikan trek, skor Anda adalah jumlah gerakan yang Anda butuhkan untuk mencapai sel tujuan yang dibagi
target
. - Jika Anda kehabisan waktu / memori atau tidak mencapai tujuan sebelum
target
belokan telah berlalu atau Anda mendarat di dinding / di luar batas setiap saat, skor Anda adalah2
. - Jika program Anda tidak deterministik, skor Anda adalah rata-rata lebih dari 10 kali berjalan di trek itu (sebutkan dalam jawaban Anda)
Skor keseluruhan Anda adalah jumlah skor trek individu. Menang skor terendah!
Selain itu, setiap peserta dapat (dan sangat disarankan untuk) memberikan track benchmark tambahan , yang akan ditambahkan ke daftar resmi. Jawaban sebelumnya akan dievaluasi kembali termasuk trek baru ini. Ini untuk memastikan bahwa tidak ada solusi yang dirancang terlalu dekat dengan kasus uji yang ada dan untuk memperhitungkan kasus tepi yang menarik yang mungkin saya lewatkan (tetapi Anda mungkin melihat).
Tie tie
Sekarang sudah ada solusi optimal, ini mungkin akan menjadi faktor utama untuk skor peserta.
Jika ada dasi (karena beberapa jawaban menyelesaikan semua trek secara optimal atau tidak), saya akan menambahkan tambahan (lebih besar) kasus uji untuk memutus ikatan. Untuk menghindari bias manusia saat membuat tie-breaker, ini akan dihasilkan secara tetap:
- Aku akan menambah panjang sisi
n
oleh10
dibandingkan dengan lagu terakhir yang dihasilkan dengan cara ini. (Saya dapat melewati ukuran jika mereka tidak memutuskan dasi.) - Dasarnya adalah vektor-grafis ini
- Ini akan dirasterisasi pada resolusi yang diinginkan menggunakan potongan Mathematica ini .
- Awal adalah di sudut kiri atas. Khususnya, itu akan menjadi sel paling kiri dari baris paling atas dari ujung trek.
- Tujuannya ada di sudut kanan bawah. Khususnya, itu akan menjadi sel paling kanan dari baris paling bawah dari ujung trek.
- Surat
target
wasiat4*n
.
Lagu terakhir dari tolok ukur awal sudah dibuat seperti ini, dengan n = 50
.
Pengendali
Program yang menguji pengiriman ditulis dalam Ruby dan dapat ditemukan di GitHub bersama dengan file benchmark yang akan saya gunakan. Ada juga bot contoh yang disebut randomracer.rb
di sana, yang hanya mengambil gerakan acak. Anda dapat menggunakan struktur dasarnya sebagai titik awal untuk bot Anda untuk melihat bagaimana komunikasi bekerja.
Anda dapat menjalankan bot Anda sendiri terhadap file trek pilihan Anda sebagai berikut:
ruby controller.rb track_file_name command to run your racer
misalnya
ruby controller.rb benchmark.txt ruby randomracer.rb
Repositori juga mengandung dua kelas Point2D
dan Track
. Jika kiriman Anda ditulis dalam Ruby, silakan menggunakannya kembali untuk kenyamanan Anda.
Sakelar baris perintah
Anda dapat menambahkan switch baris perintah -v
, -s
, -t
sebelum nama file patokan. Jika Anda ingin menggunakan beberapa sakelar, Anda juga bisa, misalnya -vs
,. Inilah yang mereka lakukan:
-v
(verbose): Gunakan ini untuk menghasilkan lebih sedikit keluaran debug dari pengontrol.
-s
(diam): Jika Anda lebih suka melacak posisi dan kecepatan Anda sendiri dan tidak peduli dengan anggaran waktu, Anda dapat mematikan tiga jalur output tersebut setiap belokan (dikirim ke kiriman Anda) dengan bendera ini.
-t
(trek): Memungkinkan Anda memilih masing-masing trek untuk diuji. Misalnya -t "1,2,5..8,15"
akan menguji trek 1, 2, 5, 6, 7, 8 dan 15 saja. Terima kasih banyak kepada Ventero untuk fitur ini dan parser opsi.
Kiriman Anda
Singkatnya, harap sertakan yang berikut dalam jawaban Anda:
- Nilai Anda.
- Jika Anda menggunakan keacakan, sebutkan ini, jadi saya bisa menilai skor Anda selama beberapa kali.
- Kode untuk kiriman Anda.
- Lokasi kompiler atau juru bahasa gratis untuk bahasa pilihan Anda yang berjalan pada mesin Windows 8.
- Instruksi kompilasi jika perlu.
- String baris perintah Windows untuk menjalankan kiriman Anda.
- Apakah kiriman Anda memerlukan
-s
benderanya atau tidak. - (opsional) Lagu baru yang dapat dipecahkan yang akan ditambahkan ke tolok ukur. Saya akan menentukan wajar
target
untuk trek Anda secara manual. Saat trek ditambahkan ke tolok ukur, saya akan mengeditnya dari jawaban Anda. Saya berhak meminta trek berbeda dari Anda (kalau-kalau Anda menambahkan trek besar yang tidak proporsional, sertakan seni ASCII cabul di trek, dll.). Ketika saya menambahkan test case ke set benchmark, saya akan mengganti trek di jawaban Anda dengan tautan ke track di file benchmark untuk mengurangi kekacauan dalam posting ini.
Seperti yang Anda lihat, saya akan menguji semua pengiriman pada mesin Windows 8. Jika sama sekali tidak ada cara agar kiriman Anda berjalan di Windows, saya juga dapat mencoba di VM Ubuntu. Ini akan jauh lebih lambat, jadi jika Anda ingin memaksimalkan batas waktu, pastikan program Anda berjalan pada Windows.
Semoga pembalap terbaik muncul vectorious!
Tapi saya ingin bermain!
Jika Anda ingin mencoba permainan sendiri untuk mendapatkan rasa yang lebih baik untuk itu, ada implementasi ini . Aturan yang digunakan di sana sedikit lebih canggih, tetapi cukup mirip untuk berguna, saya pikir.
Papan peringkat
Terakhir diperbarui: 01/09/2014, 21:29 UTC
Track dalam benchmark: 25
Ukuran tie-breaker: 290, 440
- 6.86688 - Kuroi Neko
- 8.73108 - user2357112 - pengiriman ke-2
- 9,86627 - nneonneo
- 10.66109 - user2357112 - pengiriman pertama
- 12.49643 - Ray
- 40.0759 - pseudonym117 (probabilistic)
Hasil tes terperinci . (Nilai untuk pengiriman probabilistik telah ditentukan secara terpisah.)
sumber
400
, karena itu sejalan dengan cara saya menentukan semua target lainnya (kecuali tie breaker). Saya akan memperbarui posting utama setelah saya mengulang semua kiriman lainnya.C ++, 5.4 (deterministik, optimal)
Solusi pemrograman dinamis. Terbukti optimal. Sangat cepat: menyelesaikan semua 20 testcases dalam 0,2s. Seharusnya sangat cepat pada mesin 64-bit. Asumsikan dewan kurang dari 32.000 tempat di setiap arah (yang semoga benar).
Pembalap ini sedikit tidak biasa. Itu menghitung jalur optimal di garis awal, dan kemudian mengeksekusi jalur dihitung secara instan. Ini mengabaikan kontrol waktu dan menganggap itu dapat menyelesaikan langkah optimasi tepat waktu (yang seharusnya berlaku untuk perangkat keras yang cukup modern). Pada peta yang terlalu besar, ada kemungkinan kecil bahwa pembalap dapat melakukan segmentasi. Jika Anda dapat meyakinkan itu untuk segfault, Anda mendapatkan titik brownies, dan saya akan memperbaikinya untuk menggunakan loop eksplisit.
Kompilasi dengan
g++ -O3
. Mungkin membutuhkan C ++ 11 (untuk<unordered_map>
). Untuk menjalankan, jalankan executable yang dikompilasi (tidak ada flag atau opsi yang didukung; semua input diambil pada stdin).Hasil
Testcase Baru
sumber
Python 2 , deterministik, optimal
Ini pembalap saya. Saya belum mengujinya pada benchmark (masih bingung tentang apa versi dan installer Ruby untuk menginstal), tetapi harus menyelesaikan semuanya secara optimal dan di bawah batas waktu. Perintah untuk menjalankannya adalah
python whateveryoucallthefile.py
. Membutuhkan-s
flag controller.Setelah memeriksa pembalap nneonneo (tetapi tidak benar-benar mengujinya, karena saya juga tidak memiliki kompiler C ++), saya telah menemukan bahwa tampaknya melakukan pencarian yang hampir lengkap dari ruang keadaan, tidak peduli seberapa dekat tujuan atau seberapa pendek sebuah jalan telah ditemukan. Saya juga menemukan bahwa aturan waktu berarti membangun peta dengan solusi yang panjang dan rumit membutuhkan batas waktu yang lama dan membosankan. Dengan demikian, pengiriman peta saya cukup sederhana:
Testcase Baru
(GitHub tidak dapat menampilkan garis panjang. Treknya adalah
*S.......[and so on].....
)Pengajuan tambahan: Python 2, pencarian dua arah
Ini adalah pendekatan yang saya tulis sekitar dua bulan lalu, ketika mencoba untuk mengoptimalkan pengiriman pertama saya yang luas. Untuk kasus uji yang ada pada saat itu, itu tidak menawarkan perbaikan, jadi saya tidak mengirimkannya, tetapi untuk peta baru kuroi, tampaknya hanya sedikit terjepit di bawah tutup memori. Saya masih mengharapkan pemecah kuroi untuk mengalahkan ini, tapi saya tertarik pada bagaimana ia bertahan.
sumber
n = 400
.) Tolong beri tahu saya jika Anda menerapkan optimasi, sehingga saya dapat menjalankan kembali tes.Python 3: 6.49643 (Optimal, BFS)
Untuk file benchmark 20 kasus lama, mendapat skor 5,35643. Solusi oleh @nneonneo tidak optimal karena mendapat 5.4. Beberapa bug mungkin.
Solusi ini menggunakan BFS untuk mencari Grafik, setiap keadaan pencarian dalam bentuk (x, y, dx, dy). Lalu saya menggunakan peta untuk memetakan dari negara ke jarak. Dalam kasus terburuk, kompleksitas waktu dan ruangnya adalah O (n ^ 2 m ^ 2). Ini jarang terjadi karena kecepatan tidak akan terlalu tinggi atau pembalap akan crash. Sebenarnya, harganya 3 detik di mesin saya untuk menyelesaikan semua 22 testcases.
# Hasil
sumber
O(√n)
yang akan membuat implementasi AndaO(n³)
pada kotak persegi (sama seperti yang lain, saya kira). Saya akan menambahkan tie breaker untuk menilai kiriman Anda dibandingkan dengan pengguna2357112 hari ini.n=270
, itulah sebabnya Anda sekarang berada di belakang dua kiriman "optimal" lainnya. Yang sedang berkata, kiriman Anda juga paling lambat dari ketiganya, jadi akan menjadi yang ketiga, hanya dengan tie-breaker yang lebih besar.RandomRacer, ~ 40.0 (rata-rata lebih dari 10 berjalan)
Bukan berarti bot ini tidak pernah menyelesaikan trek, tapi jelas jauh lebih jarang dari sekali dalam 10 upaya. (Saya mendapatkan skor kasus terburuk setiap 20 hingga 30 simulasi.)
Ini sebagian besar untuk bertindak sebagai kasus dasar dan untuk menunjukkan kemungkinan implementasi (Ruby) untuk pembalap:
Jalankan dengan
sumber
Pembalap Acak 2.0, ~ 31
Yah ini tidak akan mengalahkan pemecah optimal yang diposting, tetapi ini adalah sedikit peningkatan pada pembalap acak. Perbedaan utama adalah bahwa pembalap ini hanya akan mempertimbangkan secara acak pergi di mana tidak ada dinding, kecuali itu kehabisan tempat yang valid untuk bergerak, dan jika itu dapat pindah ke tujuan yang berbelok, itu akan. Itu juga tidak akan bergerak untuk tetap di tempat yang sama, kecuali tidak ada langkah lain yang tersedia (tidak mungkin, tetapi mungkin).
Diimplementasikan di Jawa, dikompilasi dengan java8, tetapi Java 6 harus baik-baik saja. Tidak ada parameter baris perintah. Ada hirarki clusterfuck yang cukup bagus, jadi saya pikir saya melakukan java dengan benar.
Hasil (Kasus terbaik yang pernah saya lihat)
sumber
.class
file itu untuk beberapa alasan (bukan direktori di mana controller berada). Ping saya (dengan komentar) jika Anda memutuskan untuk menambahkan testcase, jadi saya dapat menambahkannya ke patokan. Skor Anda adalah sekitar 33 lebih dari 10 kali jalan (lihat papan peringkat), tetapi ini mungkin berubah dengan setiap jalur tes baru yang ditambahkan ke tolok ukur.java -cp path/to/class/file VectorRacing