Este é o Buraco-3 do Torneio de Outono da APL CodeGolf . Eu sou o autor original do problema lá e, portanto, posso republicá-lo aqui.
Dado:
um número de turnos (indique se nenhum movimento é 0, caso contrário, assumiremos que é chamado 1) e
uma lista de uma ou mais posições iniciais (de qualquer forma, por exemplo, 0 ou 1 coordenada indexada ou 64 números / caracteres consecutivos ou A1 – H8 - indicar qual), em um tabuleiro de xadrez 8 por 8,
retornar (em qualquer ordem) a lista de posições únicas (no mesmo formato da entrada) em que os cavaleiros podem estar após o número determinado de turnos.
Cada cavaleiro deve se mover a cada turno, mas você não precisa se preocupar com vários cavaleiros que ocupam o mesmo quadrado.
Um cavaleiro só pode se mover para as posições marcadas com X em relação à sua posição atual, marcadas com ♞:
Exemplos (coordenadas 1-indexadas)
1
mover de [[1,1]]
: [[2,3],[3,2]]
2
move de [[1,1]]
: [[1,1],[1,3],[1,5],[2,4],[3,1],[3,5],[4,2],[4,4],[5,1],[5,3]]
1
mover de [[1,1],[5,7]]
: [[2,3],[3,2],[3,6],[3,8],[4,5],[6,5],[7,6],[7,8]]
2
move de [[1,1],[5,7]]
: [[1,1],[1,3],[1,5],[1,7],[2,4],[2,6],[2,8],[3,1],[3,3],[3,5],[3,7],[4,2],[4,4],[4,6],[4,8],[5,1],[5,3],[5,5],[5,7],[6,4],[6,6],[6,8],[7,3],[7,7],[8,4],[8,6],[8,8]]
0
move de [[3,4]]
: [[3,4]]
fonte
[[1,1]], 2 -> [[2,3],[3,2]]
Respostas:
Wolfram Language (Mathematica) , 45 bytes
Como a outra solução está incorreta (veja o comentário de Martin abaixo), eu decido postar minha solução:
Experimente online!
Notação infix final ...
Toma 2 entradas, a primeira é uma lista de números no intervalo
[1,64]
descreve as posições iniciais do cavaleiro, a segunda é o número de etapas.Esta solução depende da extrema conveniência das funções integradas do Mathematica:
AdjacencyList
O may pode pegar uma lista de vértices no lado direito e retornar uma lista de vértices adjacentes a qualquer um deles, duplicatas já removidas e classificadas .KnightTourGraph
é um builtin. Não é surpresa.Nest
recebe argumentos em ordemNest[f, expr, n]
, os quais podemos dividir no##
lado direito comoNest[f, ##]
.a~b~c~d~e
como(a~b~c)~d~e
, portanto, nenhum colchete é necessário. Sem notação infix e achatada##
, seriaNest[AdjacencyList[KnightTourGraph[8, 8], #] &, #, #2]&
.fonte
JavaScript (ES7), 99 bytes
Formato de entrada / saída: índices dos quadrados em [0 ... 63] .
Casos de teste
Esse snippet inclui duas funções auxiliares para converter de e para o formato fornecido pelo OP.
Mostrar snippet de código
Quão?
Um movimento de (x, y) para (X, Y) é um movimento válido de cavaleiro se tivermos:
Esquadrando em vez de usar valores absolutos, isso pode ser expresso como:
Porque 1 e 4 são os únicos quadrados perfeitos que dão 5 quando XOR estavam juntos, temos um movimento válido de cavaleiro se:
(xX) ² XOR (aa) ² XOR 5 = 0
Aplicamos esta fórmula a cada quadrado p = 8y + x no tabuleiro e a cada quadrado de cavaleiro P = 8Y + X para deduzir os novos possíveis quadrados alvo de cavaleiro e repetimos recursivamente esse processo n vezes.
fonte
Oitava, 69 bytes
Demo Online!
A entrada / saída é a configuração da placa no início / fim como uma matriz binária 8 * 8.
Explicação:
Para as
n
etapas, repita a dilatação morfológica do quadro com a seguinte máscara:fonte
Retina ,
147102 bytesExperimente online! Aceita entrada como um tabuleiro de 8x8 de
:
s com os cavaleiros marcados comN
s, com um dígito para o número de turnos na próxima linha (não faz sentido ter mais de 9 turnos, mas se você insistir, posso apoiá-lo por mais um byte). Observe que a saída contém espaço em branco adicional. Editar: salvou 45 bytes graças a @MartinEnder. Explicação: O primeiro estágio converte o número de turnos em unário, mas usando caracteres de tabulação, para que não sejam correspondidos posteriormente por acidente, enquanto o segundo estágio adiciona alguns espaços à direita do quadro para impedir que as expressões regulares se agrupem. A beira. A terceira etapa substitui todas asN
s e:
s que são movimento de um cavaleiro longe de umN
com umn
enquanto que a quarta fase elimina quaisquer restantesN
s, muda on
s paraN
s e subtrai 1 da contagem de movimentos. Isso se repete até que a contagem de movimentos seja zero.fonte
Gelatina , 29 bytes
Experimente online!
Coordenadas indexadas em 0. Quase certo que isso é subótimo.
-1 byte graças a user202729
Explicação
fonte
Ç
.05AB1E ,
2725 bytesObrigado a Emigna por economizar 2 bytes!
Usa coordenadas indexadas em 1.
Código:
Usa a codificação 05AB1E .Experimente online!
Explicação:
Isso nos dá a seguinte matriz:
Quais são os deltas dos movimentos do cavaleiro.
fonte
•eĆ•SÍü‚
vez deƵ‡4в2ô<D(«
salvar 2 bytes.Python 3, 105 bytes
Tem que usar um lambda nomeado para a recursão. Não tenho certeza se isso é desqualificante. Passe nas posições iniciais como lista de números quadrados indexados em 0. 0 conta como nenhum movimento.
fonte
Java (OpenJDK 8) , 124 bytes
Experimente online!
Formato de entrada / saída
A entrada / saída é representada como bits em um
long
(64 bits): bits definidos significam que um cavalo está presente, bits não definidos significam nenhum cavalo. Exemplo:Explicações
Créditos
(X-x)²+(Y-y)²==5
truque da resposta JavaScript de Arnauldint[]
para 64 bitslong
.fonte
(m,p)->{for(;m-->0;){int i=64,a[]=p,x,y,u[]={1,3,5,9,15,19,21,23};for(p=new int[i];i-->0;)for(int z:u)if((((x=i/8+z/5-2)|(y=i%8+z%5-2))&-8)==0)p[x*8+y]|=a[i];}return p;}
(m,p)->{for(int i,j,a[],x;m-->0;)for(a=p,p=new int[i=64];i-->0;)for(j=64;j-->0;)p[j]|=(x=i%8-j%8)*x+(x=i/8-j/8)*x==5?a[i]:0;return p;}
int[]
porlong
:(m,p)->{for(long i,j,a;m-->0;)for(a=p,p=i=0;i<64;i++)for(j=64;j-->0;)p|=(p=i%8-j%8)*p+(p=i/8-j/8)*p==5?(a>>i&1)<<j:0;return p;}
Geléia ,
2928 bytesExperimente online!
O número de turnos ocorre no STDIN e o quadrado é um argumento.
Isso vincula a solução Jelly da @ HyperNeutrino, mas com uma abordagem diferente.Agora, batendo @HyperNeutrino por 1 byte inteiro!
São necessárias sugestões para eliminar alguns bytes!
Link 1 (O tabuleiro de xadrez)
Link 2 (geração de movimento)
Link 3 (verificação quadrada)
fonte
Casca , 18 bytes
Usa indexação baseada em 1 de quadrados e etapas. Experimente online!
Explicação
fonte
R ,
145183134 bytesEste é o resultado do excelente jogo de golfe de Giuseppe do meu algo inicial não muito golfe (veja o comentário abaixo)
Experimente online!
A entrada e a saída são baseadas em 1 ... 64. Toma um vetor de posição usando a notação 1 ... 64. Mapeia para uma notação 1: 576, que é uma super placa composta por nove placas. Nesta notação, a cada iteração, cada cavaleiro deve ser capaz de se mover em +/- 22,26,47,49 Retorne as posições futuras na notação 1 ... 64, excluindo as que caem do quadro central. O exemplo TIO exibe o resultado usando uma matriz 8x8.
fonte
[0...63]
.[1..64]
para entrada e saída. +1, porém, é uma excelente resposta.