Let's Play Hide and Seek!

Question

The user will hide, and the computer will try to find them.

First, the program will take an input, for the size of the grid. Like 5x5, 10x10, 15x15, etc. The grid won't always be a perfect square.

The grid is sort of like a chessboard:

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

Now, the user will pick a square, such as B2 (without telling the computer)

The computer will start guessing squares. If it picks the correct square, the user will respond with y. If not, they will input the direction their tile is from the one picked (N, NE, E, SE, S, SW, W).

So if the user picked B2, and the computer guessed C3, the user would input NW.

Here is an example of the outputs and inputs:

Grid?
5x5

C3?
NW

C2?
N

B2?
y

Scoring:

This will be scored a little differently than a normal challenge.

The winner is the program that takes lowest number of guesses (on average) it takes to guess the correct square. The test cases to be averaged will be all of the possible squares in a 5x5 and then in a 10x10.

However, it must also work with every pattern of grid up to 26 rows (i.e. 5x8, 6x2, 20x5, etc.).

Please include a way for it to be tested, such as a JSFiddle.

And lastly, in case of a tie, the shortest program wins.

Answer 1

Python 3.6, 466 398 392 bytes, 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 and output should be in the form shown in the example. This finds the square with the minimal "split factor"--which is the largest remaining area that can result from the player's answer (i.e. NW, E, y, etc.)--and guesses that. Yes, that's always the center of the remaining area in this game, but this technique of minimizing the worst-case will work more generally in similar games with different rules.

Unreadable version:

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]

Answer 2

Mathematica, optimal behavior on test cases, 260 bytes

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

This program can be tested by cutting and pasting the above code into the Wolfram Cloud. (Test quickly, though: I think there's a time limit for each program run.) The program's guesses look like 2 c instead of C2, but otherwise it runs according to the spec above. The grid must be input as an ordered pair of integers, like {26,100}, and responses to the program's guesses must be input as strings, like "NE" or "y".

The program keeps track of the smallest and largest row number and column number that is consistent with the inputs so far, and always guesses the center point of the subgrid of possibilities (rounding NW). The program is deterministic, so it's easy to compute the number of guesses it requires on average over a fixed grid. On a 10x10 grid, the program requires 1 guess for a single square, 2 guesses for eight squares, 3 guesses for 64 squares, and 4 guesses for the remaining 27 squares, for an average of 3.17; and this is the theoretical minimum, given how many 1-guess, 2-guess, etc. sequences can lead to correct guesses. Indeed, the program should achieve the theoretical minimum on any size grid for similar reasons. (On a 5x5 grid, the average number of guesses is 2.6.)

A little code explanation, although it's fairly straightforward other than the golfingness. (I exchanged the order of some initializing statements for expository purposes—no effect on byte count.)

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

Lines 1-3 initialize the For loop, which actually is just a While loop in disguise, so hey, two fewer bytes. The possible row-number and column-number ranges at any moment is stored in {{a, c}, {f, h}}, and the centered guess in that subgrid is computed by the functions {b, g} defined in line 2. Line 3 initializes the max-row c and max-column h from user input, and also initializes r which is the loop-tested variable and also the subsequent user inputs.

While the test on line 4 is satisfied, line 5 gets input from the user, where the prompt comes from the current guess {b, g} (Alphabet[][[b]]] converts the row number to a letter). Then lines 6-8 update the subgrid-of-possibilities (and hence implicitly the next guess). For example, t["NSu", {{a, b - 1}, {b + 1, c}, {b, b}}] (given the definition of t on line 1) expands to

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

where you can see the min-row and max-row numbers being updated according to the user's last input. Line 8 converts any possible input to an ordered pair of characters of the form { "N" | "S" | "u", "u" | "W" | "X"}; here "u" stands for a correct row or column, and "X" stands for East (just to allow Sort to work nicely). When the user finally inputs "y", these lines throw an error, but then the loop-test fails and the error is never propogated (the program simply halts anyway).

Answer 3

Batch, divide-and-conquer

@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

Works by creating the bounding box of the the area still to be searched. The next guess is always the centre of the box. For those compass points that are not included in the response, the box is reduced in that direction. For example for a response of N, the left, right and bottom of the box are set to the guessed square.

At 369 bytes I'm not expecting to beat anybody so I've left the spaces in for readibility.