Vamos brincar de esconde-esconde!

12

O usuário irá ocultar e o computador tentará encontrá-los.

Primeiro, o programa terá uma entrada, para o tamanho da grade. Como 5x5, 10x10, 15x15, etc. A grade nem sempre será um quadrado perfeito.

A grade é como um tabuleiro de xadrez:

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

Agora, o usuário escolherá um quadrado, como B2(sem informar o computador)

O computador começará a adivinhar os quadrados. Se escolher o quadrado correto, o usuário responderá com y. Caso contrário, eles informarão a direção em que seu bloco é o escolhido (N, NE, E, SE, S, SW, W).

Portanto, se o usuário selecionasse B2, e o computador adivinhasse C3, o usuário digitaria NW.

Aqui está um exemplo das saídas e entradas:

Grid?
5x5

C3?
NW

C2?
N

B2?
y

Pontuação:

Isso será pontuado um pouco diferente de um desafio normal.

O vencedor é o programa que leva o menor número de palpites (em média) necessários para adivinhar o quadrado correto. Os casos de teste a serem calculados serão todos os quadrados possíveis em um 5x5 e depois em um 10x10.

No entanto, ele também deve funcionar com todos os padrões de grade de até 26 linhas (5x8, 6x2, 20x5 etc.).

Inclua uma maneira de testá-lo, como um JSFiddle.

E, finalmente, em caso de empate, o programa mais curto vence.

JKonowitz
fonte
1
Se estou me escondendo A1e o computador adivinha B9, a resposta é adequada NWou W?
Greg Martin
@GregMartin Seria NW .... N, W, S, E devem todos ser de cadeia linear, enquanto nada sobre uma linha / coluna diferente deve ser NW, NE, SW, SE
JKonowitz
Existe flexibilidade no formato específico de entrada e saída? Se houver mais de 26 linhas, como elas são chamadas?
Greg Martin
@ GregMartin Você pode ser flexível com a saída, mas tente mantê-la simples. Não precisa ser exatamente o mesmo, mas deve ter um estilo semelhante. Você não precisa responder por nada acima de 26, vou editar isso.
JKonowitz
Não sei o que significa "estilo semelhante". Podemos considerar a entrada como um par ordenado de números inteiros (linha #, col #)? (PS: Estes tipos de perguntas são razões pelas quais desafios pré-lançamento no Sandbox é uma ótima idéia.)
Greg Martin

Respostas:

3

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)

A entrada e a saída devem estar no formato mostrado no exemplo. Ele encontra o quadrado com o "fator de divisão" mínimo - que é a maior área restante que pode resultar da resposta do jogador (ou seja, NW, E, y, etc.) - e adivinha isso. Sim, esse é sempre o centro da área restante deste jogo, mas essa técnica de minimizar o pior caso funcionará de maneira mais geral em jogos semelhantes com regras diferentes.

Versão ilegível:

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
fonte
2

Mathematica, comportamento ideal em casos de teste, 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"]]

Este programa pode ser testado cortando e colando o código acima na Wolfram Cloud . (Teste rapidamente, no entanto: acho que há um limite de tempo para cada execução do programa.) As suposições do programa parecem em 2 cvez de C2, mas, caso contrário, são executadas de acordo com as especificações acima. A grade deve ser inserida como um par ordenado de números inteiros, como {26,100}, e as respostas às suposições do programa devem ser inseridas como cadeias, como "NE"ou "y".

O programa controla o menor e o maior número de linhas e colunas que são consistentes com as entradas até o momento e sempre adivinha o ponto central da sub-grade de possibilidades (arredondamento NW). O programa é determinístico, por isso é fácil calcular o número de suposições necessárias em média em uma grade fixa. Em uma grade de 10x10, o programa requer 1 palpite para um único quadrado, 2 palpites para oito quadrados, 3 palpites para 64 quadrados e 4 palpites para os 27 quadrados restantes, para uma média de 3,17; e esse é o mínimo teórico, considerando quantas seqüências de 1 palpite, 2 palpites etc. podem levar a suposições corretas. De fato, o programa deve atingir o mínimo teórico em qualquer grade de tamanho por razões semelhantes. (Em uma grade de 5x5, o número médio de suposições é 2,6.)

Uma pequena explicação sobre o código, embora seja bastante simples, além do golfe. (Troquei a ordem de algumas instruções de inicialização para fins expositivos - sem efeito na contagem de bytes).

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

As linhas 1-3 inicializam o Forloop, que na verdade é apenas um Whileloop disfarçado, portanto, ei, menos dois bytes. Os possíveis intervalos de número de linha e número de coluna a qualquer momento são armazenados {{a, c}, {f, h}}e a suposição centralizada nessa subgrelha é calculada pelas funções {b, g}definidas na linha 2. A linha 3 inicializa a linha ce a coluna máx. hDa entrada do usuário e também inicializa rqual é a variável testada em loop e também as entradas subseqüentes do usuário.

Enquanto o teste na linha 4 é satisfeito, a linha 5 recebe informações do usuário, de onde o prompt vem da suposição atual {b, g}( Alphabet[][[b]]]converte o número da linha em uma letra). As linhas 6-8 atualizam a sub-grade de possibilidades (e, portanto, implicitamente a próxima estimativa). Por exemplo, t["NSu", {{a, b - 1}, {b + 1, c}, {b, b}}](dada a definição de tna linha 1) se expande para

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

onde você pode ver os números da linha mínima e da linha máxima sendo atualizados de acordo com a última entrada do usuário. A linha 8 converte qualquer entrada possível em um par ordenado de caracteres do formulário { "N" | "S" | "u", "u" | "W" | "X"}; aqui "u"significa uma linha ou coluna correta e "X"significa Leste (apenas para permitir um Sortbom funcionamento). Quando o usuário finalmente insere "y", essas linhas geram um erro, mas o teste de loop falha e o erro nunca é propagado (o programa simplesmente pára de qualquer maneira).

Greg Martin
fonte
0

Lote, dividir e conquistar

@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

Funciona criando a caixa delimitadora da área ainda a ser pesquisada. O próximo palpite é sempre o centro da caixa. Para os pontos de bússola que não estão incluídos na resposta, a caixa é reduzida nessa direção. Por exemplo, para uma resposta de N, a esquerda, a direita e a parte inferior da caixa estão definidas no quadrado adivinhado.

Com 369 bytes, não espero vencer ninguém, então deixei os espaços para facilitar a leitura.

Neil
fonte
Bem, dividir e conquistar é geralmente útil para grandes casos de teste, mas não para casos pequenos, algum algoritmo melhor?
Matthew Roh
@SIGSEGV Não sei o que você quer dizer; As respostas de Greg e Ben também usam o método do centro da caixa.
314 Neil
Ainda precisamos de um algoritmo melhor.
Matthew Roh 31/03
@SIGSEGV O método do centro da caixa é ideal. Não existe melhor algoritmo.
TheNumberOne 31/03