Pengguna akan bersembunyi, dan komputer akan mencoba menemukannya.
Pertama, program akan mengambil input, untuk ukuran grid. Seperti 5x5, 10x10, 15x15, dll. Kotak tidak akan selalu menjadi kotak yang sempurna.
Kotaknya seperti papan catur:
_______________________________
| | | | | |
| A1 | | | | | A
|_____|_____|_____|_____|_____|
| | | | | |
| | B2 | | | | B
|_____|_____|_____|_____|_____|
| | | | | |
| | | C3 | | | C
|_____|_____|_____|_____|_____|
| | | | | |
| | | | D4 | | D
|_____|_____|_____|_____|_____|
| | | | | |
| | | | | E5 | E
|_____|_____|_____|_____|_____|
1 2 3 4 5
Sekarang, pengguna akan memilih kotak, seperti B2
(tanpa memberi tahu komputer)
Komputer akan mulai menebak kotak. Jika memilih kotak yang benar, pengguna akan merespons y
. Jika tidak, mereka akan memasukkan arah ubin mereka dari yang dipilih (N, NE, E, SE, S, SW, W).
Jadi jika pengguna memilih B2
, dan komputer menebak C3
, pengguna akan memasukkan NW
.
Berikut ini adalah contoh dari output dan input:
Grid?
5x5
C3?
NW
C2?
N
B2?
y
Mencetak:
Ini akan dinilai sedikit berbeda dari tantangan normal.
Pemenangnya adalah program yang mengambil jumlah tebakan terendah (rata-rata) yang dibutuhkan untuk menebak kuadrat yang benar. Kasus uji yang akan dirata-ratakan akan menjadi semua kotak yang mungkin dalam 5x5 dan kemudian dalam 10x10.
Namun, ini juga harus bekerja dengan setiap pola kisi hingga 26 baris (yaitu 5x8, 6x2, 20x5, dll.).
Harap sertakan cara untuk diuji, seperti JSFiddle.
Dan terakhir, dalam kasus seri, program terpendek menang.
sumber
A1
dan komputer menebakB9
, apakah respons yang tepatNW
atauW
?Jawaban:
Python 3.6 ,
466398392 byte, minimaxInput dan output harus dalam bentuk yang ditunjukkan pada contoh. Ini menemukan kotak dengan "faktor split" minimal - yang merupakan area tersisa terbesar yang dapat dihasilkan dari jawaban pemain (yaitu NW, E, y, dll.) - dan menebaknya. Ya, itu selalu menjadi pusat area yang tersisa dalam game ini, tetapi teknik meminimalkan kasus terburuk ini akan bekerja lebih umum di game serupa dengan aturan yang berbeda.
Versi tidak terbaca:
sumber
Mathematica, perilaku optimal pada kasus uji, 260 byte
Program ini dapat diuji dengan memotong dan menempelkan kode di atas ke dalam Wolfram Cloud . (Namun, tes dengan cepat: Saya pikir ada batas waktu untuk setiap program yang dijalankan.) Tebakan program ini terlihat seperti
2 c
bukanC2
, tetapi jika tidak berjalan sesuai dengan spesifikasi di atas. Kotak harus dimasukkan sebagai pasangan bilangan bulat yang dipesan, seperti{26,100}
, dan respons terhadap dugaan program harus berupa input sebagai string, suka"NE"
atau"y"
.Program melacak nomor baris dan kolom terkecil dan terbesar yang konsisten dengan input sejauh ini, dan selalu menebak titik pusat dari kemungkinan subgrid (pembulatan NW). Program ini bersifat deterministik, sehingga mudah untuk menghitung jumlah tebakan yang dibutuhkan rata-rata di atas jaringan tetap. Pada kisi 10x10, program ini membutuhkan 1 tebakan untuk satu kotak, 2 tebakan untuk delapan kotak, 3 tebakan untuk 64 kotak, dan 4 tebakan untuk 27 kotak yang tersisa, dengan rata-rata 3,17; dan ini adalah minimum teoritis, mengingat berapa banyak urutan 1-tebakan, 2-tebakan, dll. dapat menghasilkan tebakan yang benar. Memang, program harus mencapai minimum teoritis pada ukuran kisi apa pun untuk alasan yang sama. (Pada kisi 5x5, jumlah rata-rata tebakan adalah 2.6.)
Penjelasan kode sedikit, meskipun itu cukup mudah selain golf. (Saya menukar urutan beberapa pernyataan inisialisasi untuk tujuan ekspositori — tidak berpengaruh pada jumlah byte.)
Baris 1-3 menginisialisasi
For
loop, yang sebenarnya hanyaWhile
loop yang menyamar, jadi hei, dua byte lebih sedikit. Kemungkinan jumlah baris dan nomor kolom setiap saat disimpan{{a, c}, {f, h}}
, dan tebakan terpusat pada subgrid itu dihitung oleh fungsi yang{b, g}
didefinisikan dalam baris 2. Baris 3 menginisialisasi barisc
-maksimum dan kolom-maksimumh
dari input pengguna, dan juga menginisialisasir
yang merupakan variabel loop-diuji dan juga input pengguna selanjutnya.Sementara tes pada baris 4 puas, baris 5 mendapat input dari pengguna, di mana prompt berasal dari tebakan saat ini
{b, g}
(Alphabet[][[b]]]
mengubah nomor baris menjadi huruf). Kemudian baris 6-8 perbarui subgrid-of-kemungkinan (dan karenanya secara implisit menebak berikutnya). Misalnya,t["NSu", {{a, b - 1}, {b + 1, c}, {b, b}}]
(diberi definisit
pada baris 1) berkembang menjadidi mana Anda dapat melihat nomor baris minimum dan baris maksimum diperbarui sesuai dengan input terakhir pengguna. Baris 8 mengonversi input apa pun yang mungkin menjadi pasangan karakter yang dipesan
{ "N" | "S" | "u", "u" | "W" | "X"}
; di sini"u"
singkatan dari baris atau kolom yang benar, dan"X"
singkatan dari East (hanya untuk memungkinkanSort
bekerja dengan baik). Ketika pengguna akhirnya menginput"y"
, garis-garis ini melempar kesalahan, tetapi kemudian tes loop gagal dan kesalahan tidak pernah dipropogasi (program tetap saja terhenti).sumber
Batch, bagi-dan-taklukkan
Bekerja dengan membuat kotak pembatas area yang masih harus dicari. Tebakan berikutnya selalu menjadi pusat kotak. Untuk titik kompas yang tidak termasuk dalam respons, kotak dikurangi ke arah itu. Misalnya untuk respons
N
, kiri, kanan dan bawah kotak diatur ke kotak yang ditebak.Pada 369 byte saya tidak berharap untuk mengalahkan siapa pun jadi saya telah meninggalkan ruang untuk readibility.
sumber