Dalam Chinese Checkers , sepotong dapat bergerak dengan melompati bagian lain, atau dengan membuat urutan hop tersebut. Tugas Anda adalah menemukan urutan hop yang terpanjang.
Memasukkan
Urutan 121 nol atau satu, masing-masing mewakili tempat di papan tulis. Nol berarti tempat itu kosong; satu berarti tempat itu ditempati. Posisi terdaftar dari kiri ke kanan; atas ke bawah. Misalnya, input dari pengaturan ini adalah
1011110011000001000000000000000000000000100000000001000000000000000000000000000001000000000000000000000001000001100111111
Penjelasan:
Tempat paling atas ditempati oleh potongan hijau, jadi digit pertama dalam input adalah
1
. Baris kedua memiliki satu posisi kosong dan satu posisi terisi, jadi01
datang berikutnya. Baris ketiga sudah terisi, jadi111
. Baris keempat memiliki dua ruang kosong dan dua yang ditempati (dari kiri ke kanan), jadi0011
. Kemudian muncul lima0
, a1
, dan tujuh0
untuk baris berikutnya, dan seterusnya.
Seperti dalam pengaturan itu, ada sudut yang menunjuk lurus ke atas. Mungkin ada sejumlah potongan di papan tulis (dari 1 hingga 121). Perhatikan bahwa potongan warna yang berbeda tidak terwakili secara berbeda.
Keluaran
Panjang maksimum lompatan legal, menggunakan bagian apa pun di papan tulis. Anda tidak boleh mengunjungi tempat yang sama lebih dari satu kali (termasuk posisi awal dan akhir). Namun, Anda dapat melompati bagian yang sama lebih dari satu kali. Jika tidak ada hop hukum, output 0
. Jangan mempertimbangkan apakah ada langkah hukum non-hop.
Misalnya, output ke pengaturan yang dijelaskan di atas adalah 3
.
Input dan output dapat dilakukan melalui stdin dan stdout, melalui argumen baris perintah, melalui pemanggilan fungsi, atau metode serupa lainnya.
Uji Kasus
Memasukkan:
0100000010000000000000000100000000000000000000000000000001010010000000000000000000000101000000000000000000100000000100001
Output: 0
(tidak ada dua bagian yang bersebelahan)
Memasukkan:
0000000000111100000000011100000000011000000000100000000000000000000000000000000000000000000000000000000000000000000000000
Output: 1
(pengaturan awal untuk satu pemain di sudut kiri atas)
sumber
Jawaban:
Perl,
345322Sunting: golf, sedikit.
Lebih banyak test case akan menyenangkan, tetapi untuk saat ini sepertinya berfungsi. Saya akan menambahkan komentar nanti jika perlu. Dengan baris baru dan lekukan agar mudah dibaca:
sumber
C,
262260Kode golf ( kode debug dan spasi kosong yang tidak perlu dihapus. Berubah dari input melalui stdin ke input melalui baris perintah, dan memanfaatkan peluang untuk mendeklarasikan variabel di sana. Edit terbaru: kode dipindahkan ke dalam kurung
for
loop untuk menyimpan dua titik koma.)Penjelasan
Ini bergantung pada papan 20x21 yang terlihat seperti ini, awalnya diisi dengan nol ketika program dimulai (seni ASCII ini dihasilkan oleh versi program yang dimodifikasi, dan ketika
i
loop menghitung ke bawah, nol ada di sudut kanan bawah):Loop
i
dijalankan melalui papan ini dua kali, menggunakan x dan y untuk menghitung apakah kotak benar-benar milik kotak-kotak atau tidak (ini membutuhkan 6 ketidaksetaraan terpisah dalam x dan y.)Jika ya, putaran pertama mengisi kotak, menempatkan
0
(falsy) untuk1
(diduduki) dan1
(kebenaran) untuk0
(tidak dihuni). Pembalikan ini penting, karena semua kotak di luar batas sudah mengandung 0, yang berarti mereka menyerupai kotak yang diduduki dan jelas mereka tidak dapat dilompati, tanpa perlu pemeriksaan khusus.Putaran waktu kedua, jika kuadrat ditempati (berisi 0) itu memanggil fungsi
f
yang mencari bergerak.f
mencari secara rekursif dalam 6 arah yang mungkin dikodekan oleh +/- 1 (horizontal), +/- 20 (vertikal) dan +/- 19 (diagonal) yang dikodekan dalam ekspresi"AST?-,"[k]-64
. Ketika menemukan hit, itu mengatur sel itu ke 0 (ditempati) sebelum memanggil dirinya secara rekursif, lalu set kembali ke 1 (kosong) ketika fungsi dikembalikan. Nilai sel harus diubah sebelum panggilan rekursif untuk mencegah melompat ke sel itu lebih dari sekali.Kode tidak dikunci
sumber