Latar Belakang
Hex adalah gim strategi abstrak dua pemain yang dimainkan pada K×K
belah ketupat ubin heksagonal. Dua sisi yang berlawanan dari belah ketupat berwarna putih, dan dua lainnya hitam, dan dua pemain, hitam dan putih, secara bergiliran menempatkan token warna mereka pada ubin kosong. Pemain yang pertama kali berhasil membangun jalur antara sisi yang berlawanan dari warna mereka adalah pemenangnya. Diketahui bahwa permainan tidak dapat berakhir imbang, dan bahwa pemain pertama memiliki strategi kemenangan terlepas dari ukuran papan (lihat halaman Wikipedia untuk detailnya).
Tugas
Dalam tantangan ini, kami memperbaiki ukuran papan di K = 4
, dan mewakili papan sebagai kisi berikut. Garis tebal menunjukkan ubin yang berdekatan.
Tugas Anda adalah menghasilkan strategi kemenangan untuk pemain pertama, yang dapat Anda pilih untuk menjadi hitam atau putih. Ini berarti bahwa tindakan legal apa pun yang dilakukan pemain lawan, permainan Anda harus menghasilkan kemenangan. Input Anda adalah posisi permainan (pengaturan token di papan tulis), dan output Anda adalah langkah hukum, dalam format yang ditentukan di bawah ini. Jika Anda ingin menemukan strategi pemenang sendiri, jangan baca spoiler ini:
Garis besar satu strategi kemenangan yang mungkin, dengan anggapan putih menjadi yang utama. Pertama pilih 5. Setelah itu, jika Anda memiliki jalur dari 5 ke baris bawah ATAU hitam memilih 0 atau 1 di titik mana pun, balas dengan memilih mana dari 0 atau 1 yang kosong. Jika hitam memilih 9 atau 13, pilih 10 lalu 14 atau 15 mana yang kosong. Jika hitam tidak memilih 9, 13 atau 14, maka pilih 9 dan selanjutnya 13 atau 14 mana yang kosong. Jika hitam memilih 14, balas dengan memilih 15. Berikutnya, pilih 10 jika kosong; jika hitam memilih 10, jawab dengan 11. Jika hitam lalu pilih 6, jawab dengan 7, dan selanjutnya 2 atau 3 mana yang kosong. Jika hitam tidak memilih 6, pilih itu, sehingga Anda memiliki jalur dari 5 ke baris bawah.
Masukan dan keluaran
Input Anda adalah string 16 karakter WBE
, yang berarti putih, hitam dan kosong. Mereka mewakili ubin papan, sebagaimana disebutkan di atas. Anda dapat memilih metode input (yang juga menentukan metode output Anda) dari yang berikut:
- Input dari STDIN, output ke STDOUT.
- Input sebagai satu argumen baris perintah, output ke STDOUT.
- Input sebagai 16 argumen argumen perintah karakter tunggal, output ke STDOUT.
- Input sebagai argumen fungsi bernama, output sebagai nilai balik.
Output Anda mewakili ubin tempat Anda meletakkan token berikutnya, karena giliran Anda untuk bergerak. Anda dapat memilih dari format output berikut:
- Indeks berbasis nol (seperti yang digunakan dalam gambar di atas).
- Indeks berbasis satu.
- String input dengan satu
E
diganti oleh yang manaW
atauB
Anda pilih untuk pemain Anda.
Aturan
Strategi Anda harus deterministik. Anda tidak diharuskan untuk menangani posisi permainan dengan benar yang tidak dapat dijangkau dari papan kosong menggunakan strategi Anda, atau posisi yang sudah menang untuk salah satu pemain, dan Anda mungkin menabraknya. Sebaliknya, di papan yang dapat dijangkau menggunakan strategi Anda, Anda harus mengembalikan langkah hukum.
Ini adalah kode-golf, sehingga jumlah byte terendah menang. Celah standar tidak diijinkan.
Pengujian
Saya telah menulis kontroler Python 3 untuk memvalidasi entri, karena akan sangat membosankan untuk dilakukan dengan tangan. Anda dapat menemukannya di sini . Ini mendukung tiga format input pertama dan fungsi Python 3 (fungsi dalam bahasa lain harus dimasukkan ke dalam program), ketiga format output, dan kedua pemain. Jika sebuah strategi tidak menang, itu akan menghasilkan permainan yang hilang itu ditemukan, sehingga Anda dapat mengubah program Anda.
Incorrect response 'WWWWWWWWBBBBBBBB' to message 'WWWWWWWWBBBBBBBB'.
Saya seharusnya menang sejak lama, atau saya salah?Jawaban:
Marbelous, 973b
Ini adalah implementasi yang naif dari strategi yang diisyaratkan dalam pertanyaan. Itu mengharapkan papan akan diberikan sebagai 16 commandline / parameter mainboard suka
hex.mbl B W E E E W E E E B E E E E E E
dan itu akan menampilkan posisi nol-diindeks dari langkah selanjutnya putih.Saya pikir saya mungkin bisa bermain golf sekitar 200 karakter dari ini dengan percabangan yang lebih baik dan penghapusan penggunaan kembali kode.
sumber
Python 3, 100b
Strateginya adalah pertama mencari
B
di papan tulis. Jika tidak ada yang kembali-1
, yang dalam python sama denganlast index
. Jadi di papan kosong indeks pertama saya akanindex=-1
, di situlah saya mulai bergerak.Jika bidang di sebelah kiri saya (
index-1
) gratis, langkah saya berikutnya ada di sana. Jika diambil, saya naik ke kiri. Saya tidak pernah harus naik: jika saya lakukan, saya kehilangan tempo dan akan kehilangan permainan.Di papan penuh (tidak ada
E
tempat) saya tidak bergerak.The
print
tampaknya sedikit aneh pada awalnya: Saya harus membangun dewan baru (yang saya lakukan melalui mengiris) tapi kemudian saya harus memotong 16 karakter. Ini adalah peninggalan karena saya bekerja dengan indeks negatif danb[i+1:]
dengan demikian akan mengembalikan papan lubang dan sisanya yang saya harapkan, sehingga penting untuk memotong sisanya. Cara lain adalah bekerja dengan indeks positif, misalnya dengan mengambil(b.find('B')+16)%16
, tetapi(+16)%16
satu byte lebih dari()[:16]
.Tidak Disatukan:
Uji
Saat menjalankan suite tes hex controller, saya menemukan beberapa perilaku aneh:
Saya pikir saya seharusnya menang setelah giliran ke-4 atau menjawab dengan papan yang sama untuk papan penuh harus menjadi jawaban yang benar. Tidak yakin apa yang salah di sana, tidak menyelam jauh lebih dalam - saya hanya ingin memeriksa apakah saya memiliki semua kasus "khusus" yang tertutup. Tapi karena saya tidak harus menutupi situasi di mana seseorang mulai di ruang 4 atau lebih, itu tidak masalah.
85b
Namun, jika saya membiarkan diri saya tidak memeriksa papan penuh (yaitu meninggalkan,
'E' in b
saya selanjutnya dapat menyederhanakan kode untuk hanya menggunakan 85 byte:Ini akan mengarah pada yang berikut:
Ini mungkin atau mungkin tidak dihitung, dan karena saya menemukan itu bukan langkah yang valid saya memutuskan untuk mencari jawaban yang lebih lama tetapi lebih benar.
sumber