L'utilisateur se cachera et l'ordinateur essaiera de les trouver.

Tout d'abord, le programme prendra une entrée, pour la taille de la grille. Comme 5x5, 10x10, 15x15, etc. La grille ne sera pas toujours un carré parfait.

La grille est un peu comme un échiquier:

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

Maintenant, l'utilisateur choisira un carré, comme B2(sans le dire à l'ordinateur)

L'ordinateur commencera à deviner les carrés. S'il choisit le bon carré, l'utilisateur répondra par y. Sinon, ils entreront la direction de leur tuile à partir de celle choisie (N, NE, E, SE, S, SW, W).

Donc, si l'utilisateur choisissait B2, et l'ordinateur devinait C3, l'utilisateur entrerait NW.

Voici un exemple des sorties et entrées:

Grid?
5x5

C3?
NW

C2?
N

B2?
y

Notation:

Cela sera marqué un peu différemment d'un défi normal.

Le gagnant est le programme qui prend le plus petit nombre de suppositions (en moyenne) qu'il faut pour deviner le bon carré. Les cas de test à faire la moyenne seront tous les carrés possibles dans un 5x5 puis dans un 10x10.

Cependant, il doit également fonctionner avec chaque modèle de grille jusqu'à 26 lignes (c'est-à-dire 5x8, 6x2, 20x5, etc.).

Veuillez inclure un moyen de le tester, tel qu'un JSFiddle.

Et enfin, en cas d'égalité, le programme le plus court l'emporte.

Python 3.6 , 466 398 392 octets, 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)

L'entrée et la sortie doivent être sous la forme indiquée dans l'exemple. Ceci trouve le carré avec le "facteur de partage" minimal - qui est la plus grande zone restante qui peut résulter de la réponse du joueur (c'est-à-dire NW, E, y, etc.) - et le devine. Oui, c'est toujours le centre de la zone restante de ce jeu, mais cette technique de minimisation du pire des cas fonctionnera plus généralement dans des jeux similaires avec des règles différentes.

Version illisible:

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]

Mathematica, comportement optimal sur les cas de test, 260 octets

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

Ce programme peut être testé en coupant et collant le code ci-dessus dans Wolfram Cloud . (Testez rapidement, cependant: je pense qu'il y a une limite de temps pour chaque exécution de programme.) Les suppositions du programme ressemblent à la 2 cplace de C2, mais sinon il s'exécute selon les spécifications ci-dessus. La grille doit être entrée sous la forme d'une paire ordonnée d'entiers, comme {26,100}, et les réponses aux suppositions du programme doivent être entrées sous forme de chaînes, comme "NE"ou "y".

Le programme garde une trace du plus petit et du plus grand numéro de ligne et de colonne qui est cohérent avec les entrées jusqu'à présent, et devine toujours le point central de la sous-grille de possibilités (arrondi NW). Le programme est déterministe, il est donc facile de calculer le nombre de suppositions dont il a besoin en moyenne sur une grille fixe. Sur une grille de 10x10, le programme nécessite 1 supposition pour un seul carré, 2 suppositions pour huit carrés, 3 suppositions pour 64 carrés et 4 suppositions pour les 27 carrés restants, pour une moyenne de 3,17; et c'est le minimum théorique, étant donné le nombre de séquences 1-deviner, 2-deviner, etc. peuvent conduire à des suppositions correctes. En effet, le programme devrait atteindre le minimum théorique sur n'importe quelle grille de taille pour des raisons similaires. (Sur une grille 5x5, le nombre moyen de suppositions est de 2,6.)

Une petite explication de code, bien que ce soit assez simple à part le golf. (J'ai échangé l'ordre de certaines instructions d'initialisation à des fins d'exposition - aucun effet sur le nombre d'octets.)

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

Les lignes 1 à 3 initialisent la Forboucle, qui n'est en fait qu'une Whileboucle déguisée, donc bon, deux octets de moins. Les plages de numéros de ligne et de colonne possibles à tout moment sont stockées dans {{a, c}, {f, h}}, et la supposition centrée dans cette sous-grille est calculée par les fonctions {b, g}définies à la ligne 2. La ligne 3 initialise la ligne cmax et la colonne max à hpartir de l'entrée utilisateur, et initialise également rla variable testée en boucle ainsi que les entrées utilisateur suivantes.

Alors que le test de la ligne 4 est satisfait, la ligne 5 reçoit une entrée de l'utilisateur, où l'invite provient de la supposition actuelle {b, g}( Alphabet[][[b]]]convertit le numéro de ligne en lettre). Ensuite, les lignes 6-8 mettent à jour la sous-grille de possibilités (et donc implicitement la prochaine supposition). Par exemple, t["NSu", {{a, b - 1}, {b + 1, c}, {b, b}}](compte tenu de la définition de la tligne 1) se développe en

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

où vous pouvez voir les numéros de ligne mini et max ligne mis à jour en fonction de la dernière entrée de l'utilisateur. La ligne 8 convertit toute entrée possible en une paire ordonnée de caractères du formulaire { "N" | "S" | "u", "u" | "W" | "X"}; ici "u"représente une ligne ou une colonne correcte et "X"représente l'Est (juste pour permettre Sortde bien fonctionner). Lorsque l'utilisateur entre enfin "y", ces lignes génèrent une erreur, mais le test de boucle échoue et l'erreur n'est jamais propagée (le programme s'arrête tout de même de toute façon).

Lot, diviser pour mieux régner

@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

Fonctionne en créant le cadre de délimitation de la zone à rechercher. La prochaine supposition est toujours le centre de la boîte. Pour les points cardinaux qui ne sont pas inclus dans la réponse, la boîte est réduite dans cette direction. Par exemple, pour une réponse de N, la gauche, la droite et le bas de la boîte sont définis sur le carré deviné.

À 369 octets, je ne m'attends à battre personne, j'ai donc laissé les espaces pour plus de lisibilité.