Mari bermain petak umpet!

12

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.

JKonowitz
sumber
1
Jika saya bersembunyi A1dan komputer menebak B9, apakah respons yang tepat NWatau W?
Greg Martin
@GregMartin Ini akan menjadi NW .... N, W, S, E semua harus lurus sedangkan apa pun pada baris / kolom yang berbeda harus NW, NE, SW, SE
JKonowitz
Apakah ada fleksibilitas dalam format spesifik input dan output? Jika ada lebih dari 26 baris, apa namanya?
Greg Martin
@GregMartin Anda bisa fleksibel dengan output tetapi cobalah untuk membuatnya tetap sederhana. Tidak harus persis sama tetapi harus memiliki gaya yang sama. Anda tidak perlu memperhitungkan apa pun di atas 26, saya akan mengeditnya.
JKonowitz
Saya tidak tahu apa artinya "gaya serupa". Bisakah kita mengambil input sebagai pasangan integer yang terurut (baris #, col #)? (PS: Pertanyaan-pertanyaan semacam ini adalah alasan mengapa memposting tantangan di Sandbox adalah ide yang bagus.)
Greg Martin

Jawaban:

3

Python 3.6 , 466 398 392 byte, minimax

x, y = 1, 1
w, h = [int(x) for x in input('Grid?\n').split('x')]


def split_factor(a, b):
    N = b-y
    W = a-x
    S = h+~N
    E = w+~W
    return max(1, N, W, S, E, N*W, S*W, S*E, N*E)


def move(a, b):
    *Z, = zip([a, x, a, a+1, x, x, a+1, a+1],
              [y, b, b+1, b, y, b+1, b+1, y],
              [1, a-x, 1, w+x+~a, a-x, a-x, w+x+~a, w+x+~a],
              [b-y, 1, h+y+~b, 1, b-y, h+y+~b, h+y+~b, b-y])
    return Z[['N', 'W', 'S', 'E', 'NW', 'SW', 'SE', 'NE'].index(d)]

d = ''
while d != 'y':
    print()
    splits = {(a, b): split_factor(a, b) for a in range(x, x+w) for b in range(y, y+h)}
    a, b = min(splits, key=splits.get)
    d = input(f'{a}{"ABCDEFGHIJKLMNOPQRSTUVWXYZ"[b]}?\n')
    x, y, w, h = move(a, b)

Input 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:

x=y=d=1
w,h=map(int,input('Grid?\n').split('x'))
while d!='y':print();s={(a,b):max(b-y,h+y+~b)*max(w+x+~a,a-x)for a in range(x,x+w)for b in range(y,y+h)};a,b=min(s,key=s.get);d=input(f'{a}{chr(64+b)}?\n');*z,=zip([a+1,x,a+1,x,a,a,a+1,x],[b+1,b+1,y,y,b+1,y,b,b],[w+x+~a,a-x,w+x+~a,a-x,1,1,w+x+~a,a-x],[h+y+~b,h+y+~b,b-y,b-y,h+y+~b,b-y,1,1]);x,y,w,h=z[~'WENS'.find(d)or-'NWNESWSE'.find(d)//2-5]
Ben Frankel
sumber
2

Mathematica, perilaku optimal pada kasus uji, 260 byte

For[a=f=1;{c,h}=Input@Grid;z=Characters;t=<|Thread[z@#->#2]|>&;r="";v=Floor[+##/2]&;b:=a~v~c;g:=f~v~h,r!="y",r=Input[g Alphabet[][[b]]];{{a,c},{f,h}}={t["NSu",{{a,b-1},{b+1,c},{b,b}}]@#,t["uWX",{{g,g},{f,g-1},{g+1,h}}]@#2}&@@Sort[z@r/.{c_}:>{c,"u"}/."E"->"X"]]

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 cbukan C2, 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.)

1  For[a = f = 1; z = Characters; t = <|Thread[z@# -> #2]|> &;
2      v = Floor[+##/2] &; b := a~v~c; g := f~v~h;
3      r = ""; {c, h} = Input@Grid, 
4    r != "y", 
5    r = Input[g Alphabet[][[b]]];
6      {{a, c}, {f, h}} = {t["NSu", {{a, b - 1}, {b + 1, c}, {b, b}}]@#, 
7        t["uWX", {{g, g}, {f, g - 1}, {g + 1, h}}]@#2} & @@ 
8        Sort[z@r /. {c_} :> {c, "u"} /. "E" -> "X"]
   ]

Baris 1-3 menginisialisasi Forloop, yang sebenarnya hanya Whileloop 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 baris c-maksimum dan kolom-maksimum hdari input pengguna, dan juga menginisialisasi ryang 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 definisi tpada baris 1) berkembang menjadi

<| "N" -> {a, b - 1}, "S" -> {b + 1, c}, "u" -> {b, b}|>

di 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 memungkinkan Sortbekerja 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).

Greg Martin
sumber
0

Batch, bagi-dan-taklukkan

@echo off
set z = ABCDEFGHIJKLMNOPQRSTUVWXYZ
set /p g = Grid?
set /a w = 0, n = 0, e = %g :x= + 1, s = % + 1
:l
set /a x = (w + e) / 2, y = (n + s) / 2
call set c = %%z :~%y%,1%%
set /p g = %c %%x%?
if %g :w=.% == %g % set /a w = x
if %g :n=.% == %g % set /a n = y
if %g :e=.% == %g % set /a e = x
if %g :s=.% == %g % set /a s = y
if %g :y=.% == %g % goto l

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.

Neil
sumber
Nah, bagi-dan-taklukkan biasanya berguna untuk testcases besar tetapi tidak untuk kasus kecil, ada algoritma yang lebih baik?
Matius Roh
@SIGSEGV Tidak yakin apa yang Anda maksud; Jawaban Greg dan Ben juga menggunakan metode center of the box.
Neil
Kami masih membutuhkan algoritma yang lebih baik.
Matius Roh
@SIGSEGV Pusat metode kotak optimal. Tidak ada algoritma yang lebih baik.
TheNumberOne