Existe um jogo chamado Get Home que é jogado no tabuleiro de xadrez. Neste jogo, há uma única peça que é movida pelos dois jogadores em turnos. Existem algumas regras sobre como a peça pode ser movida. Em um turno, um jogador deve fazer um dos seguintes movimentos para n positivo .
n espaços acima
n espaços à esquerda
n espaços acima e à esquerda (uma diagonal)
O jogador que move a peça para o canto superior esquerdo do tabuleiro vence o jogo.
Agora vamos definir o conceito de um quadrado perdedor. Em este vídeo (de onde eu tive a idéia) um quadrado perder é definido como um quadrado sobre o qual, qualquer jogador que começa sua vez será forçado a fazer um movimento permitindo o seu adversário para forçar uma vitória. O exemplo mais simples de um quadrado perdedor seria o quadrado em (1,2). Uma peça em (1,2) pode ser movida para qualquer um dos seguintes lugares.
Todos os quais têm um caminho direto para a vitória para o próximo jogador.
Da mesma forma, qualquer quadrado que possua um caminho de um movimento para um quadrado perdedor permite que o jogador que começa nesse quadrado force uma vitória. Isso significa que qualquer quadrado que não esteja a um passo de um quadrado perdedor também é um quadrado perdedor.
Isso nos leva a essa definição bastante clara de um quadrado perdedor:
Um quadrado perdedor é um quadrado do qual nenhum movimento pode chegar a outro quadrado perdedor e (0,0) é um quadrado perdedor.
Tarefa
Dadas as coordenadas de um quadrado em um tabuleiro de xadrez de tamanho arbitrário, determine se é um quadrado perdedor. Saída dois valores um para perder quadrados e um para outros.
Isso é código-golfe, então as respostas serão pontuadas em bytes, com menos bytes sendo melhores.
Casos de teste
Aqui estão todos os quadrados perdidos em um tabuleiro de xadrez regular de 8 por 8 (marcado com 0).
0 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1
1 0 1 1 1 1 1 1
1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 0
1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1
Aqui está uma imagem de uma placa de 100 por 100 com quadrados perdidos marcados em preto (cada quadrado tem 2 pixels por 2 pixels).
fonte
10, 7
um quadrado perdedor? É10, 8
? Que tal15, 11
?Respostas:
Python 3 ,
112504642 bytes-4 bytes graças a Jonathan Allan !
-2 bytes graças ao xnor !
Experimente online!
Baseado na fórmula para posições frias no jogo de Wythoff e fazendo algumas modificações para produzir uma fórmula explícita. Explicação de entrada uma vez que eu realmente terminei uma metodologia adequada para a derivação da fórmula.
fonte
0<=x
parax>0
e salvar um byte ou dois?<=
ou>=
para incluir a posição0, 0
.lambda r,c:int(abs(r-c)*(5**.5+1)**2/4)==max(r,c)
/2//1
parece o mesmo que//2
.Gelatina , 8 bytes
Experimente online! ou veja os 60 por 60 no canto superior esquerdo como uma grade .
Quão?
Uma posição fria no jogo de Wythoff é uma posição perdida. As coordenadas
[n,m]
dão uma posição fria quandon = floor(kφ) = floor(mφ) - m
oum = floor(kφφ) = ceil(nφ) = n + k
para algum número naturalk
, e a proporção áureaφ
,. O primeiro mantém quandon
é menor quem
; o último quandom
é menor quen
(ambos segurando em0,0
).k
é, portanto, a diferença absoluta entren
em
e sefloor(abs(n-m)φ)=min(n,m)
a condição for atendida.fonte
JavaScript (ES6), 64 bytes
Percebo agora que essa não é a melhor técnica, mas tive que elaborá-la porque perdi a Internet logo após carregar esta página. (Teria postado um tempo atrás, se não fosse por esses problemas da Internet ...)
Em um mundo perfeito, a precisão da flutuação não seria um problema e eu poderia salvar 9 bytes:
Mais 6 bytes poderiam ser salvos se JS suportasse o encadeamento de comparação do Python:
fonte
Pyth, 39 Bytes
Eu escrevi isso com uma função nomeada (ew) e era extremamente preguiçoso com o golfe. Planejando jogar fora vários bytes mais tarde hoje à noite
Experimente online, com meus próprios testes gerados, destinados a alternar Verdadeiro / Falso
Explicação:
As diagonais da matriz da solução têm um quadrado perdedor de acordo com a sequência de números repetidos no OEIS A005206 . De
L
através;
é uma notação polonesa bastante direta para definiry(b)=b-y(y(b-1))
.O restante da explicação segue
fonte
Lote, 204 bytes
Retorna via código de saída. Explicação: Como o Lote possui apenas aritmética inteira, tive que criar uma solução puramente aritmética. Excluindo a
0,0
entrada, os pares de coordenadas quadradas perdedoras seguem a seguinte regra: se o próximo11
número binário livre for igual, adicione add3,2
caso contrário2,1
. Um teste para um11
número binário livre é se não houver carregamentos quando multiplicado por três, em outras palavras(i*2)+i==(i*2)^i
. Aqui estão os primeiros11
números binários livres e suas coordenadas:Misteriosamente, essa regra é suficiente para tornar as seqüências complementares. Resta então calcular a sequência até que ela atinja a coordenada maior, momento em que podemos determinar se o quadrado está perdendo.
fonte