Cavaleiro na borda é sombrio

48

Introdução

Aron Nimzowitsch foi um dos principais mestres do xadrez e um influente escritor de xadrez.

Em seu livro 'My System', o primeiro capítulo trata da importância do centro e por que você deve dominá-lo. A simples razão é que suas peças têm mais movimentos diretos possíveis quando estão no centro, o que novamente dá ao jogador mais poder.

Isso fica muito claro quando se olha para diferentes posições de um cavaleiro e seus possíveis próximos movimentos (mostrados em rosa) em um tabuleiro vazio:

insira a descrição da imagem aqui

Objetivo

Avalie o número de possíveis próximos movimentos diretos de um cavaleiro em um tabuleiro vazio com base em sua posição.

Especificações de entrada

A posição do cavaleiro.

Primeiro o x (coluna) e depois o y (linha). 0 0é o canto inferior esquerdo.

Para simplificar, mudei os rótulos de um tabuleiro de xadrez para apenas números. Para nossos exemplos e casos de teste, usamos um índice baseado em 0, mas você pode usar um índice baseado em 1.

Você pode usar qualquer tipo de possível formato de entrada, matriz, argumentos de função etc.

Especificações de saída

O número de próximos movimentos diretos em potencial para um cavaleiro em um tabuleiro vazio.

Casos de teste

3 4 => 8
4 6 => 6
7 7 => 2
1 0 => 3

Os casos de teste estão empregando um índice baseado em 0. A grade completa de valores é:

2 3 4 4 4 4 3 2
3 4 6 6 6 6 4 3
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
3 4 6 6 6 6 4 3
2 3 4 4 4 4 3 2
starcorder
fonte
9
Bom primeiro desafio! :-)
Luis Mendo
14
"Cavaleiro na borda é sombrio"
2
@stacey O seu comentário teria sido um grande título para este quebra-cabeça :)
starcorder
6
Agora, a pergunta realmente difícil: os cavaleiros vermelhos nas imagens acima têm a mesma cor?
mbomb007

Respostas:

25

Python 2 , 35 bytes

lambda x,y:50/(8+x*x/7-x+y*y/7-y)-4

Experimente online!


Python 2 , 39 bytes

lambda x,y:50/(8-x*(7-x)/5-y*(7-y)/5)-4

Experimente online!

Leva as entradas indexadas em 0.

A expressão x*(7-x)/5leva os valores das coordenadas 0..7para

[0, 1, 2, 2, 2, 2, 1, 0]

( min(x,7-x,2)faz o mesmo, mas é mais longo.) Soma isso xe yfornece o padrão certo, mas com os números errados

0 1 2 2 2 2 1 0
1 2 3 3 3 3 2 1
2 3 4 4 4 4 3 2
2 3 4 4 4 4 3 2
2 3 4 4 4 4 3 2
2 3 4 4 4 4 3 2
1 2 3 3 3 3 2 1
0 1 2 2 2 2 1 0

(Veja a solução de Neil para um melhor raciocínio sobre por que isso dá o padrão certo.)

Finalmente, o mapeamento a -> 50/(8-a)-4com divisão de piso fornece os valores certos

2 3 4 4 4 4 3 2
3 4 6 6 6 6 4 3
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
3 4 6 6 6 6 4 3
2 3 4 4 4 4 3 2

Uma solução alternativa igualmente longa com entradas indexadas 1:

lambda x,y:(x*(9-x)/6+y*(9-y)/6)**2/6+2
xnor
fonte
(7-a)*a/5é 3 bytes menor que min(a,7-a,2).
Neil
11
*lna verdade, o custo total de um byte lambda a,b:"23468"[(7-a)*a/5+(7-b)*b/5]é de apenas 41 bytes.
Neil
@ Neil Acabei de encontrar a mesma coisa com x*(9-x)/6, um indexado.
xnor
11
Por que você não usa <strike>como todo mundo para mostrar o progresso no golfe?
Insano
4
@ Insano Eu acho que parece feio e na verdade não ajuda. O código é o importante, e quem quiser ver sua evolução ainda precisa procurar no histórico de edições. Quando meu código antigo é diferente o suficiente para valer a pena mostrar, mostro as versões como aqui . Mas nesta questão, são todas pequenas melhorias na mesma estratégia, então achei mais limpo apenas mencionar as diferentes possibilidades.
xnor
17

MATL , 17 14 13 12 bytes

Graças a @ Neil por 1 byte de desconto!

8:HZ^ZP5X^=s

A entrada é baseada em 1.

Experimente online!

Explicação

Isso calcula a distância euclidiana da entrada para cada uma das 64 posições no tabuleiro de xadrez e descobre quantos desses valores são iguais à raiz quadrada de 5.

Como as coordenadas são valores inteiros, podemos ter certeza de que os dois valores de ponto flutuante que representam a raiz quadrada de 5 (calculados a partir das coordenadas e calculados diretamente) são realmente os mesmos.

8:      % Push array [1 2 ... 8]
H       % Push 2
Z^      % Cartesian power. Gives 2D array [1 1; 1 2; ... 1 8; 2 1; ... 8 8]     
ZP      % Implicit input. Compute Euclidean distances, considering each row as a point
5X^     % Square root of 5
=s      % Compute how many squared distances equal sqrt(5). Implicit display
Luis Mendo
fonte
11
Impressionantes e obrigado pela explicação
starcorder
11
Se a comparação do quadrado da raiz quadrada de 5 a 5 falhar devido a erros de arredondamento, você não pode pelo menos comparar a raiz quadrada de 5 com a raiz quadrada de 5?
Neil
@ Neil Obrigado pela idéia! Sim, como os cálculos são com números inteiros, posso ter certeza de que as duas "raízes de 5" são o mesmo doublenúmero. Ant salva um byte
Luis Mendo
15

Mathematica 63 43 bytes

Com 20 bytes salvos, graças às sugestões de Martin Ender!

EdgeCount[8~KnightTourGraph~8,#+1+8#2/<->_]&

A tabela acima mostra o número de quadrados que estão a 1 salto da célula especificada no gráfico completo do tour dos cavaleiros.


g=KnightTourGraph[8,8,VertexLabels->"Name",Axes->True]

exibe o gráfico completo do tour do cavaleiro, com nomes e coordenadas de vértices. Observe que o Mathematica assume como padrão a indexação baseada em uma única para as coordenadas.

gráfico


#+1+8#2&[r,f]converts retorna o vértice correspondente ao quadrado na classificação (linha) re arquivo (coluna) f, usando valores baseados em zero como entrada.

Por exemplo, #+1+8#2&[2,1]retorna 11.


EdgeCount fornece o número de arestas no gráfico da vizinhança.


As arestas da classificação 2, arquivo 1 (quadrado 11):

IncidenceList[8~KnightTourGraph~8, 8 #2 + # + 1] &[2, 1]

(*{1 <-> 11, 5 <-> 11, 11 <-> 17, 11 <-> 21, 11 <-> 26, 11 <-> 28}*)

As arestas destacadas:

HighlightGraph[g, {1, 5, 11, 17, 21, 26, 28, Style[1 <-> 11, Thick, Blue], Style[5 <-> 11, Thick, Blue], Style[11 <-> 17, Thick, Blue], Style[11 <-> 21, Thick, Blue], Style[11 <-> 26, Thick, Blue], Style[11 <-> 28, Thick, Blue]},GraphHighlightStyle -> "DehighlightFade", PlotRangePadding -> .5]

realçar


Método 2: Distância euclidiana

70 bytes

Este método é mais longo, mas possivelmente de algum interesse. A abordagem é verificar a distância euclidiana entre o centro do tabuleiro de xadrez e a célula de interesse.

Which[(x=Sqrt@Tr[({3.5, 3.5}-#)^2])<2.2,8,x<3,6,x<4,4,x<4.6,3,x>4.6,2]&

Exemplificando

Which[(x=Sqrt@Tr[({3.5, 3.5}-#)^2])<2.2,8,x<3,6,x<4,4,x<4.6,3,x>4.6,2]&@{0, 0}
Which[(x=Sqrt@Tr[({3.5, 3.5}-#)^2])<2.2,8,x<3,6,x<4,4,x<4.6,3,x>4.6,2]&@{3, 3}

2

8


Para ajudar a visualizar como a distância do centro do tabuleiro de xadrez é suficiente para atribuir um valor.

values={{2,3,4,4,4,4,3,2},{3,4,6,6,6,6,4,3},{4,6,8,8,8,8,6,4},{4,6,8,8,8,8,6,4},{4,6,8,8,8,8,6,4},{4,6,8,8,8,8,6,4},{3,4,6,6,6,6,4,3},{2,3,4,4,4,4,3,2}};
f[x_]:=Text[x,#]&/@Position[values,x]r_~w~p_:=RegionMember[{3.5`,3.5`}~Disk~r,p]
h@y_:=Which[2.2~w~y,8,3~w~y,6,4~w~y,4,4.6~w~y,3,2<3,2]

Graphics[{Circle[{4.5, 4.5}, 2.3], Circle[{4.5, 4.5}, 3], 

Círculo [{4,5, 4,5}, 4],

Círculo [{4.5, 4.5}, 4.6], Achatar [f / @ {2, 3, 4, 6, 8}, 1]}, Eixos -> Verdadeiro, AxesOrigin -> {-1, -1}]


Os números 2.2, 3, 4 e 4.6 são os raios dos círculos.

imagem

DavidC
fonte
11
Great tour graph
starcorder 28/06/2016
20
KnightTourGraphMathematica e seus builtins ... :-)
Luis Mendo
Eu acho que há um desvio #no final do seu código-fonte (pouco antes do ]). Você deve poder usar em IncidenceListvez de fazê-lo EdgeList@NeighborhoodGraph. (Como alternativa, há também EdgeCount, mas eu acho que acaba por ser mais longo.)
Martin Ender
11
Ah, espere, é realmente mais curto:EdgeCount[8~KnightTourGraph~8,#+1+8#2<->_]&
Martin Ender
EdgeCounté muito legal!
DavidC
12

JavaScript (ES6), 38 bytes

(x,y)=>+"23468"[((7-x)*x+(7-y)*y)/5|0]

Recebe entradas indexadas em 0. Explicação: Observe os quadrados das distâncias para o centro:

24.5 18.5 14.5 12.5 12.5 14.5 18.5 24.5
18.5 12.5  8.5  6.5  6.5  8.5 12.5 18.5
14.5  8.5  4.5  2.5  2.5  4.5  8.5 14.5
12.5  6.5  2.5  0.5  0.5  2.5  6.5 12.5
12.5  6.5  2.5  0.5  0.5  2.5  6.5 12.5
14.5  8.5  4.5  2.5  2.5  4.5  8.5 14.5
18.5 12.5  8.5  6.5  6.5  8.5 12.5 18.5
24.5 18.5 14.5 12.5 12.5 14.5 18.5 24.5

O número de quadrados alcançáveis ​​cai em cinco faixas:

8    0-5
6    5-10
4   10-15
3   15-20
2   20-25

Na verdade, eu calculo 24,5 - (3,5 - x) ** 2 - (3,5 - y) ** 2 = (7 - x) * x + (7 - y) * y como é um cálculo mais curto, mas tudo o que faz é inverso a ordem das bandas.

Neil
fonte
Super concisa e abordagem muito bom, então eu não tenho que começar minha própria solução JS mais :)
starcorder
Bom argumento sobre a fórmula ser equivalente ao raio ao quadrado. Eu tinha pensado x*(7-x)apenas como uma operação que se parece com um arco descendente 0..7e acontece com o ajuste de curva, mas isso explica por que ele produz um padrão tão bom quando somado a xe y.
Xnor 28/06
11

Gelatina, 10 bytes

8ṗ2_³²S€ċ5

1 indexado. Aceita um único argumento do formulário [x,y]. Experimente aqui.

8ṗ2          Cartesian square [[1,1],[1,2]…[8,8]]
   _³        Subtract the input
     ²S€     Compute the norm of each vector
        ċ5   Count fives

Dennis salvou um byte!

Lynn
fonte
Apenas onze bytes, uau!
Starcorder 28/06
Vi essa pergunta de manhã e esse é o algoritmo exato que pensei em implementar no Jelly quando tivesse tempo. : P
PurkkaKoodari
8

Mathematica, 44 40 bytes

Atualmente, tenho três soluções na mesma contagem de bytes:

2[3,4,6,8][[Tr@⌊3.2-.8Abs[#-4.5]⌋]]&
Tr@⌈.85(4-Abs[#-4.5])⌉/.{5->6,6->8}&
⌊Tr@⌈.85(4-Abs[#-4.5])⌉^1.1608⌋&

Todas essas são funções sem nome que usam par de coordenadas {3, 4}, que são baseadas em 1.

Tentei encontrar uma fórmula um pouco explícita. O padrão geral em todo o quadro é assim:

insira a descrição da imagem aqui

Os valores reais dessas cores (do mais claro ao mais escuro) são 2, 3, 4, 6, 8. Isso é:

2 3 4 4 4 4 3 2
3 4 6 6 6 6 4 3
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
3 4 6 6 6 6 4 3
2 3 4 4 4 4 3 2

Primeiro exploramos a simetria deslocando a origem para o centro, pegando o valor absoluto e subtraindo o resultado 4. Isso nos dá coordenadas 0.5para 3.5aumentar a partir de cada canto. A fim de tornar as coordenadas do centro a mesma necessidade que para mapear 0.5e 1.5para diferentes valores e 2.5e 3.5para o mesmo valor. Isso é feito facilmente multiplicando por 0.8(distribuindo {0.4, 1.2, 2., 2.8}) e colocando o resultado no piso. Então agora temos {0, 1, 2, 2}as distâncias do centro. Se somarmos as coordenadas em cada célula, obteremos esta tabela:

0 1 2 2 2 2 1 0
1 2 3 3 3 3 2 1
2 3 4 4 4 4 3 2
2 3 4 4 4 4 3 2
2 3 4 4 4 4 3 2
2 3 4 4 4 4 3 2
1 2 3 3 3 3 2 1
0 1 2 2 2 2 1 0

Isso tem valores exclusivos para todos os diferentes resultados possíveis, então simplesmente o usamos como um índice para 2[3,4,6,8].

Na segunda versão, usamos teto em vez de piso. Desta forma, 2, 3e 4já estão corretos, mas nós temos 5e 6, em vez de 6e 8, por isso, corrigir os manualmente com uma regra de substituição.

Por fim, na terceira versão, estendemos 5e subimos 6para 6e 8por meio de exponenciação, seguidos por outra operação de andar.

Martin Ender
fonte
Eu gosto muito da abordagem usando o padrão geral do fórum, ótimo!
starcorder
6

APL, 21 caracteres

{+/,5=+/¨×⍨(⍳8 8)-⊂⍵}

Em inglês:

  • (⍳8 8): Matriz 8x8 rank-2 contendo as coordenadas de todas as células;
  • +/¨×⍨(⍳8 8)-⊂⍵: quadrado das distâncias euclidianas da célula especificada em relação a cada célula do quadro;
  • 5=: matriz de 0/1, onde os 1s aparecem a distâncias quadradas iguais a 5;
  • +/,: soma a matriz achatada

Teste (na origem 1):

    f←{+/,5=+/¨×⍨(⍳8 8)-⊂⍵}
    f¨1+(3 4)(4 6)(7 7)(1 0)
8 6 2 3

Nesta forma:

f←{+/,5=+/¨×⍨(⍳⍺)-⊂⍵}

o argumento da esquerda pode especificar as dimensões do quadro. Portanto 8 8 f, funcionará para o tabuleiro de xadrez quadrado padrão. Mas em uma placa maior e retangular, os casos de teste dariam resultados diferentes. Por exemplo, em uma placa 12x10:

    g←(10 12)∘f
    g¨1+(3 4)(4 6)(7 7)(1 0)
8 8 8 3
lstefano
fonte
No jargão da APL, uma matriz é uma matriz de classificação 2, nada dito sobre o conteúdo das células. Anos de (ab) uso dos termos me deixaram insensível. Atualizarei a descrição para os leitores mais tradicionais. Obrigado.
21816 lstefano # 11:
@Istefano Esse uso de "rank" como "número de dimensões" parece sofrer do mesmo :-P aflição
Luis Mendo
Eu estarei ... Você está certo! Você pode ver que já faz um tempo desde que tirei Álgebra Linear. Eu desisto :-)
lstefano 28/06
11
Programa completo, 27: ≢⍸5=+/¨×⍨-∘⎕¨⍳8 8 Experimente online!
Adám
@ Adám você quer dizer 17
ngn
6

Java - 160 150 bytes

int m(int r,int c){int m=0,i,j;for(i=0;i<3;i+=2)for(j=0;j<3;j+=2){m+=r+i>0&r+i<9&c+2*j>1&c+2*j<11?1:0;m+=r+2*i>1&r+2*i<11&c+j>0&c+j<9?1:0;}return m;}

Ungolfed:

public static int m(int r, int c) {
    int m=0;
    for(int i=-1;i<2;i+=2)
        for(int j=-1;j<2;j+=2){
            m += r+i>-1 && r+i<8 && c+2*j>0 && c+2*j<8 ? 1:0;
            m += r+2*i>0 && r+2*i<8 && c+j>1 && c+j<8 ? 1:0;
        }
    return m;
}

O código ungolfed é idêntico, exceto para alterar os limites do loop for para economizar 4 bytes. Trabalha iterando cada movimento possível e executando uma verificação de limites (> 0 e <8). Usa o fato de que as compensações são (1, 2), (2, 1), (-1, 2), (-2, 1) etc., e é capaz de verificar 2 movimentos para cada valor de iej.

Editar: 10 bytes salvos graças às sugestões de Leaky Nun e u902383.

ejaszewski
fonte
Isso também foi rápido, legal!
starcorder
Ocorreu um erro lá, foi corrigido.
ejaszewski
11
int m=0,i=-1,j;para salvar alguns bytes
Leaky Nun
11
alterar E lógico para bit a bit AND e que irá permitir que você remover adicional de 6 caracteres
user902383
6

C, 44 bytes

f(x,y){return "23468"[((7-x)*x+(7-y)*y)/5];}

Mas isso é melhor:

f(x,y){return "2344443234666643468888644688886446888864468888643466664323444432"[x*8+y];}
Giacomo Garabello
fonte
11
Desaparecido ;. Não será compilado.
ugoren
@GiacomoGarabello Veja: meta.codegolf.stackexchange.com/a/1146/55729
Jacajack
11
Não é um trecho, é uma função e não é proibido postar funções. Desculpe pelo ponto e vírgula ausente. Fixo.
Giacomo Garabello
5

Haskell, 49 48 bytes

w=[0..7]
x%y=sum[1|a<-w,b<-w,(a-x)^2+(b-y)^2==5]
Damien
fonte
11
Você pode salvar [0..7]em uma variável para 1 byte.
xnor
5

Java, 81 caracteres (113 bytes)

int r(int a,int b){return "⍄䐲㑦晃䚈衤䚈衤䚈衤䚈衤㑦晃⍄䐲".codePointAt(a*2+b/4)>>(3-b%4)*4&15;}

Codifique a tabela de resultados inteira como tabela unicode e obtenha os bytes apropriados executando operações bit a bit.

Você pode vê-lo online aqui: https://ideone.com/K9BojC

cliffroot
fonte
3

Python, 94 bytes

lambda x,y,a=[2,1,-1,-2,-2,-1,1,2]:list((9>x+a[i]>0)&(9>y+a[5-i]>0)for i in range(8)).count(1)

Usa 1 indexação baseada.

Demonstração em https://repl.it/C6gV .

Chuck Morris
fonte
2

Pitão - 33 15 bytes

Obrigado a @LeakyNun por reduzir meu tamanho pela metade.

Reorganizar os mapas e Vprovavelmente deixará o golfe um pouco fora.

/sM*Fm^R2-Rd8Q5

Conjunto de Teste .

Maltysen
fonte
11
Isso foi rápido, legal!
starcorder
2
15 bytes
Freira vazada
1

Na verdade, 18 bytes

`;7-2km`MΣ8-:50\¬¬

Experimente online!

Este implementa a mesma fórmula que muitas outras respostas têm vindo a utilizar: 50/(8-x*(7-x)//5+y*(7-y))//5)-4. A entrada é tomada como uma lista: [x,y](ou qualquer literal iterável em Python, como (x,y)ou x,y).

Explicação:

`;7-2km`MΣ8-:50\¬¬
`;7-2km`M           for each value in input:
 ;7-                  make a copy, subtract from 7
    2                 push 2
     km               minimum of the three values (x, 7-x, 2)
         Σ          sum
          8-        subtract from 8
            :50\    integer divide 50 by the value
                ¬¬  subtract 2 twice
Mego
fonte