Seu objetivo é escrever um jogador perfeito para o jogo de Nim de Wythoff .
Regras do Nim de Wythoff
O Nim de Wythoff é um jogo determinístico para dois jogadores, jogado com duas pilhas de marcadores idênticos. Os jogadores alternam turnos, nos quais realizam um destes procedimentos:
- Remova um ou mais contadores da primeira pilha
- Remova um ou mais contadores da segunda pilha
- Remova um número igual de contadores (um ou mais), da primeira pilha e da segunda pilha.
Obviamente, as pilhas não podem ser negativas, mas podem chegar a 0. Qualquer jogador que remover o último contador geral vence o jogo.
Para os mais geométricos, aqui está uma formulação equivalente do jogo que você pode jogar neste applet . Uma única rainha começa em algum quadrado de um tabuleiro de xadrez infinito, cujo canto fica no canto inferior esquerdo. Os jogadores alternam a mudança da rainha, que se move como uma rainha do xadrez, mas restrita a três direções:
- Baixa
- Esquerda
- Na diagonal para baixo e para a esquerda
Quem leva a rainha para o canto ganha.
Associando as coordenadas da rainha (com canto (0,0)
) ao tamanho das respectivas pilhas, é fácil ver os dois jogos iguais.
Jogo perfeito
(Você pode pular isso se estiver familiarizado com as noções de jogo perfeito e movimentos vencedores.)
Como o Nim de Wythoff é um jogo finito e determinístico, ele tem uma noção de jogo perfeito . Um jogador perfeito é uma estratégia que sempre vencerá de uma posição conquistada teoricamente, ou seja, uma posição em que exista uma estratégia que garanta uma vitória.
Para ser uma estratégia vencedora, basta mudar para sempre passar para uma posição teórica de vitória para o jogador que acabou de se mudar e, portanto, o jogador não vai para a próxima. A primeira dessas posições vencedoras (também chamadas de posições frias ) é (0,0), (1,2), (2,1), (3,5), (5,3)
. Consulte o artigo da Wikipedia para obter uma explicação de um algoritmo para encontrar uma estratégia vencedora para o Nim da Wythoff, bem como uma fórmula para gerar posições de vitória.
Requisitos do programa
Escrever um programa ou função toma uma posição como entrada e produz um movimento vencedor na forma da posição após esse movimento. Menos bytes ganha.
Se não houver movimento vencedor, ou seja, a posição é uma perda teórica, seu programa deve indicar isso e perder.
Seu programa deve ser executado dentro de um período de tempo razoável. Portanto, uma pesquisa de árvore de jogo recursiva exponencial não será suficiente. Se você quiser pré-calcular e codificar uma estratégia, tudo bem.
Entrada
Um par (i,j)
de números não negativos representando tamanhos de pilha, cada um no máximo 99
. Podem ser dois números, uma tupla, uma lista ou qualquer contêiner que você preferir.
Resultado
Imprima ou produza a posição após a sua mudança, novamente como dois números ou um contêiner. Isso deve ser uma mudança legal para uma posição vencedora. Se houver vários desses movimentos, qualquer um está bem, mas apenas um.
Se não houver movimento vencedor, você deve indicar isso na saída. Qualquer saída como False
, None
0 ou (-1,-1)
funcionará, desde que não seja uma posição legal e seja a mesma para todas as entradas perdidas.
Execuções de exemplo
f(5,0) = (0,0)
f(2,2) = (1,2) # Or (2,1) or (0,0)
f(1,2) = False
f(13,9) = (13,8) # Or (10,6)
f(10,6) = False
f(5,10) = (5,3)
f(25,30) = (8,13)
fonte
Respostas:
Haskell,
167165 caracteresO algoritmo é ineficiente, mas ainda é executado dentro de um segundo (embora não no console interativo) para entradas <100.
Explicação:
A lista de posições frias para um conjunto de posições frias anteriores é uma posição fria seguida pela lista de posições frias para esta posição e as anteriores (Ineficiência: esta posição é gerada duas vezes)
Uma posição fria é o primeiro par, de modo que não há posições frias acessíveis a partir desse par (Ineficiência: devemos procurar pelo par anterior)
As posições alcançáveis a partir de um par são aquelas que correspondem aos seus primeiros elementos, seus segundos elementos, suas diferenças ou o heap menor antes da remoção é o heap maior após a remoção.
(método principal) Se os montões estiverem na ordem errada, troque-os. Caso contrário, se a primeira posição fria alcançável de uma posição for a própria posição, indique falha (idealmente, a pessoa retornaria
Maybe (Int,Int)
contrário vez disso ). Caso contrário, retorne à posição fria (Ineficiência: o referido par é consultado duas vezes. Pior ainda, a lista de posições frias é gerada duas vezes)fonte
x@
dex@(a,b)?p=...
GolfScript (
6357 bytes)Espera a entrada de stdin no formulário
[a b]
e deixa a saída em stdout nesse formulário ou0
se é uma posição perdida. Demonstração onlineVisão geral
calcula uma lista de posições frias (incluindo a versão invertida
[b a]
para cada posição fria[a b]
) usando a propriedade de sequência Beatty .Então
?
procura a primeira posição fria que satisfaz o bloco criado porque basicamente verificações de que a posição é acessível a partir da posição de entrada calculando a diferença de vectores e, em seguida, verificar se é ou
[0 x]
,[x 0]
, ou[x x]
por algumx > 0
. O IMO desse teste é o bit mais inteligente:0|$
força qualquer matriz em um desses formatos para o formulário[0 x]
durante o mapeamento[0 0]
para[0]
,[a b]
onde nema
nemb
é0
para uma matriz de três elementos e[-x 0]
ou[-x -x]
para[-x 0]
. Em seguida,(!*,1=
verifica se temos[0 x]
.Finalmente
0]0=`
faz o caso de fallback e formatação para saída.fonte
Pitão 57
58 61 62Experimente online.
Bem parecido com outras respostas, mas essa página da Wikipedia não deu muito mais para continuar;) O número mágico
39
é o número de posições frias com valores <99
.Define uma função
g
que você pode chamar comog 30 25
. Retorna[]
por falha,[(13,8)]
em caso de sucesso.Explicação
fonte
s
é convertido para int - salva alguns caracteres/____1
.rZ39
pode ser substituído porU39
, usando um intervalo unário. Da mesma forma, você pode substituirr99)
porU99
.U
. Eu realmente deveria atualizar a explicação: P@
uma interseção de conjuntos se seu segundo argumento for uma lista agora. É um pouco sem jeito deixado de fora desde quea
foi mudado: PJavascript ES6 - 280 bytes
Minificado
Expandido
Algoritmo rápido e agradável. É executado em O (n), mas seria executado em tempo constante, se não fosse por um loop de economia de bytes. O loop é implementado como um incrementador recursivo; portanto, o script eventualmente falhará com um erro de recursão para n na casa das centenas ou milhares. Usa a mesma propriedade de sequência Beatty mencionada pelo Sr. Taylor, mas, em vez de computar a sequência, ela simplesmente adota o (s) termo (s) correto (s).
É executado corretamente em todas as entradas de teste e em muitas dezenas além do que eu testei.
A função a chamar é
f
. Ele retorna uma matriz de sucesso e uma0
desistência.fonte
Perl 5 - 109 (com 2 bandeiras)
Uso:
Simplesmente calcula a solução para cada entrada possível e apenas faz uma única pesquisa.
fonte