Użytkownik ukryje się, a komputer spróbuje je znaleźć.

Najpierw program pobierze dane wejściowe dotyczące wielkości siatki. Jak 5x5, 10x10, 15x15 itd. Siatka nie zawsze będzie idealnym kwadratem.

Siatka przypomina swego rodzaju szachownicę:

_______________________________
|     |     |     |     |     |
| A1  |     |     |     |     | A
|_____|_____|_____|_____|_____|
|     |     |     |     |     |
|     | B2  |     |     |     | B
|_____|_____|_____|_____|_____|
|     |     |     |     |     |
|     |     | C3  |     |     | C
|_____|_____|_____|_____|_____|
|     |     |     |     |     |
|     |     |     | D4  |     | D
|_____|_____|_____|_____|_____|
|     |     |     |     |     |
|     |     |     |     | E5  | E
|_____|_____|_____|_____|_____|
   1     2     3     4     5

Teraz użytkownik wybierze kwadrat, taki jak B2 (bez powiadamiania komputera)

Komputer zacznie zgadywać kwadraty. Jeśli wybierze właściwy kwadrat, użytkownik odpowie za pomocąy . Jeśli nie, wprowadzą kierunek, w którym znajduje się ich kafelek od wybranego (N, NE, E, SE, S, SW, W).

Więc jeśli użytkownik wybrał B2, a komputer zgadłC3 , użytkownik wprowadziłby dane NW.

Oto przykład danych wyjściowych i wejściowych:

Grid?
5x5

C3?
NW

C2?
N

B2?
y

Punktacja:

To będzie punktowane nieco inaczej niż normalne wyzwanie.

Zwycięzcą jest program, który przyjmuje najmniejszą liczbę zgadnięć (średnio), potrzebną do odgadnięcia właściwego kwadratu. Przypadki testowe, które należy uśrednić, to wszystkie możliwe kwadraty w 5 x 5, a następnie w 10 x 10.

Musi jednak działać również z każdym wzorem siatki do 26 rzędów (tj. 5x8, 6x2, 20x5 itp.).

Podaj sposób jego przetestowania, na przykład JSFiddle.

I na koniec, w przypadku remisu, wygrywa najkrótszy program.

Python 3.6 , 466 398 392 bajtów, 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)

Dane wejściowe i wyjściowe powinny mieć formę pokazaną w przykładzie. Znajduje kwadrat z minimalnym „współczynnikiem podziału” - który jest największym pozostałym obszarem, który może wynikać z odpowiedzi gracza (tj. NW, E, y itd.) - i zgaduje. Tak, to zawsze jest środek pozostałego obszaru w tej grze, ale ta technika minimalizacji najgorszego przypadku będzie działać bardziej ogólnie w podobnych grach z różnymi zasadami.

Nieczytelna wersja:

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]

Matematyka, optymalne zachowanie przypadków testowych, 260 bajtów

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"]]

Ten program można przetestować, wycinając i wklejając powyższy kod do chmury Wolfram . (Testuj jednak szybko: Myślę, że istnieje limit czasowy dla każdego uruchomienia programu.) Zgadnięcia programu wyglądają 2 czamiast C2, ale w przeciwnym razie działają zgodnie z powyższą specyfikacją. Siatka musi być wprowadzana jako uporządkowana para liczb całkowitych itp. {26,100}, A odpowiedzi na domysły programu muszą być wprowadzane jako ciągi znaków, takie jak "NE"lub "y".

Program śledzi najmniejszy i największy numer wiersza i numeru kolumny, który jest zgodny z dotychczasowymi danymi wejściowymi i zawsze zgaduje punkt środkowy podsiatki możliwości (zaokrąglanie NW). Program jest deterministyczny, więc łatwo jest obliczyć liczbę domysłów, których wymaga średnio na stałej siatce. Na siatce 10x10 program wymaga 1 zgadywania dla pojedynczego kwadratu, 2 zgadywania dla ośmiu kwadratów, 3 zgadywania dla 64 kwadratów i 4 zgadywania dla pozostałych 27 kwadratów, średnio 3,17; i jest to teoretyczne minimum, biorąc pod uwagę, ile sekwencji 1 zgadnij, 2 zgadnij itd. może prowadzić do poprawnych domysłów. Rzeczywiście, program powinien osiągnąć teoretyczne minimum na dowolnej siatce rozmiarów z podobnych powodów. (Na siatce 5x5 średnia liczba domysłów wynosi 2,6.)

Małe wyjaśnienie kodu, chociaż jest całkiem proste, inne niż gra w golfa. (Wymieniłem kolejność niektórych instrukcji inicjujących do celów ekspozycyjnych - bez wpływu na liczbę bajtów).

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"]
   ]

Linie 1-3 inicjują Forpętlę, która w rzeczywistości jest tylko Whileukrytą pętlą, więc hej, dwa mniej bajtów. Możliwe zakresy numerów wierszy i numerów kolumn w dowolnym momencie są przechowywane {{a, c}, {f, h}}, a wyśrodkowane zgadywanie w tej podsiatce jest obliczane przez funkcje {b, g}zdefiniowane w wierszu 2. Wiersz 3 inicjuje maksimum wiersza ci maksimum kolumny na hpodstawie danych wprowadzonych przez użytkownika, oraz inicjuje również rzmienną testowaną w pętli, a także kolejne dane wejściowe użytkownika.

Podczas gdy test na linii 4 jest spełniony, linia 5 otrzymuje dane wejściowe od użytkownika, gdzie monit pochodzi z bieżącej domysły {b, g}( Alphabet[][[b]]]konwertuje numer wiersza na literę). Następnie linie 6-8 aktualizują podsiatkę możliwości (i domyślnie następną przypuszczenie). Na przykład t["NSu", {{a, b - 1}, {b + 1, c}, {b, b}}](biorąc pod uwagę definicję tw wierszu 1) rozwija się do

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

gdzie można zobaczyć, że numery wierszy min i wierszy są aktualizowane zgodnie z ostatnim wejściem użytkownika. Wiersz 8 konwertuje wszelkie możliwe dane wejściowe na uporządkowaną parę znaków formularza { "N" | "S" | "u", "u" | "W" | "X"}; tutaj "u"oznacza prawidłowy wiersz lub kolumnę i "X"oznacza wschód (tylko po to, Sortaby ładnie pracować). Kiedy użytkownik w końcu wprowadza dane "y", wiersze te generują błąd, ale test pętli kończy się niepowodzeniem, a błąd nigdy nie jest propagowany (program i tak po prostu zatrzymuje się).

Partia, dziel i rządź

@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

Działa, tworząc obwiednię obszaru, który ma być nadal przeszukiwany. Następne przypuszczenie jest zawsze środkiem pudełka. W przypadku punktów kompasu, które nie zostały uwzględnione w odpowiedzi, pole jest zmniejszane w tym kierunku. Na przykład dla odpowiedzi Nlewy, prawy i dolny bok pola są ustawione na odgadnięty kwadrat.

Przy 369 bajtach nie spodziewam się nikogo pokonać, więc zostawiłem wolne miejsca dla czytelności.