Quantos movimentos?

16

Dadas duas posições diferentes em um tabuleiro de xadrez e o tipo de peça, faça o número mínimo de movimentos necessários para que essa peça vá de uma posição para outra.

Regras

A peça dada pode ser rei, rainha, torre, cavaleiro e bispo. (Esta entrada pode ser aceita como 5 caracteres únicos)

As 2 posições podem ser tomadas em qualquer formato conveniente,

Example:
a8 b8 c8 d8 ... h8
a7 b7 c7 d7 ... h7
...
...
a1 b1 c1 d1 ... h1

Caso a peça não possa chegar lá, produza algo que não seja um número inteiro positivo.

Exemplos

i/p ---- o/p
King
a1,a4    3
a1,h6    7
b3,h5    6

Queen
a1,a4    1
a1,h6    2
b3,f7    1

Rook
a1,a4    1
a1,h6    2
h2,c7    2

Knight
a1,a4    3
a1,h6    4
b2,d3    1
b2,c3    2
b3,c3    3
a1,b2    4

Bishop
a1,a4    -1
a1,h6    2
b2,d3    -1
e1,h4    1
Vedant Kandoi
fonte
1
Por que o rei precisa de 12 a a1-h6? King não pode ir diag?
L4m2 26/11/18
@ l4m2, corrigido
Vedant Kandoi 26/11/18
1
@ngn, você pode usar 0 para indicar inacessibilidade, as 2 posições sempre serão diferentes.
Vedant Kandoi 26/11/19
1
Algumas definições (como ISO-80000-2) de números naturais incluem 0. Recomenda a substituição por "número inteiro positivo".

Respostas:

9

JavaScript (Node.js) , 183 180 179 bytes

with(Math)(a,b,c,d,t,x=abs(a-c),y=abs(b-d),v=x<y?y:x,q=0|.9+max(/[18][18]/.test(a+b+9+c+d)-v?x/2:3,y/2,x*y?x*y-4?(x+y)/3:3:2))=>t?t==2&x+y?0:t&1>x*y|t/2&x==y?1:t<4?2:v:q+(q+x+y&1)

Experimente online!

Há muito tempo para casos extremos, agradeço a Arnauld pela verificação. Teste do cavaleiro

l4m2
fonte
@Arnauld Bem canto realmente custar
l4m2
Eu acho que você pode salvar um byte, substituindo o último maxpor um ternário.
Shaggy #
170 bytes (acho que estou no meu telefone..)
Shaggy
@Shaggy foi o que Arnauld apontou errado
l4m2 26/11/18
6

APL (Dyalog Classic) , 117 107 105 103 98 97 95 92 89 87 bytes

{(⍎⍺⊃'⌈/' '≢∘∪~∘0' '+/×' '{⍺∊⍵:0⋄1+⍺∇i/⍨∨⌿2=|×/↑⍵∘.-i←,⍳8 8}/,¨⊂¨↓⍵' '≢∘∪×2=.|⊢')⊣|-⌿⍵}

Experimente online!

arg esquerdo é tipo de peça: 0 = rei, 1 = rainha, 2 = torre, 3 = cavaleiro, 4 = bispo; arg direito é uma matriz 2x2 de cordas, cada linha representando uma posição; retorna 0 para inacessível

|-⌿⍵ calcula o par [abs (∆x), abs (∆y)]

(⍎⍺⊃... )⊣escolhe uma expressão da lista "..."; se é uma função, é aplicada a |-⌿⍵; se for um valor (isso acontece apenas para um cavaleiro), certifique-se de devolvê-lo em vez de|-⌿⍵

  • rei: max ( ⌈/) dos abs ∆-s

  • queen: remova os zeros ( ~∘0) e conte ( ) os únicos ( )

  • torre: soma ( +/) de signa (monádico ×; 0 para 0, 1 para positivo)

  • cavaleiro: {⍺∊⍵:0⋄1+⍺∇i/⍨∨⌿2=|×/↑⍵∘.-i←,⍳8 8}/,¨⊂¨↓⍵- comece com a posição inicial e calcule recursivamente gerações de movimentos do cavaleiro até que a posição final esteja no conjunto; retornar profundidade de recursão

  • bispo: as paridades dos dois ∆-s são iguais? ( 2=.|⊢, equivalente a =/2|⊢) multiplique o resultado booleano (0 ou 1) pelo número único de contagem ( ≢∘∪)

ngn
fonte
Eu amo o ⍎⍺⊃. Muito esperto.
J. Sallé
@ J.Sallé thanks
ngn
2

Java (JDK) , 229 bytes

(p,a,b,c,d)->{c^=a/4*7;a^=a/4*7;d^=b/4*7;b^=b/4*7;int x=c<a?a-c:c-a,y=d<b?b-d:d-b,z=(x^=y^(y=y<x?y:x))-y;return p<1?x:p<2?z*y<1?1:2:p<3?2-z%2:p<4?x+y<2?3:(a<c?a+b:c+d)+x<2|x==2&z<1?4:z+2*Math.ceil((y-z)/(y>z?3:4.)):z<1?1:~z*2&2;}

Experimente online!

Explicações

  • O conselho é um conselho baseado em 0.
  • O valor retornado é um número inteiro, representado como um duplo. Nunca haverá nenhuma parte decimal.

Código:

(p,a,b,c,d)->{                          // double-returning lambda.
                                        // p is the piece-type (0: king, 1: queen, 2: rook, 3: knight, 4: bishop)
                                        // a is the origin-X
                                        // b is the origin-Y
                                        // c is the destination-X
                                        // d is the destination-Y
 c^=a/4*7;a^=a/4*7;                     // Mirror board if origin is in the top part of the board
 d^=b/4*7;b^=b/4*7;                     // Mirror board if origin is in the left part of the board
 int x=c<a?a-c:c-a,                     // x is the X-distance between a and c
     y=d<b?b-d:d-b,                     // y is the Y-distance between b and d
     z=(x^=y^(y=y<x?y:x))-y;            // z is the delta between x and y
                                        // also, swap x and y if necessary so that x is the greater value.
               //    At this point,
               //     x      cannot be 0 (because the two positions are different)
               //     z<1    means the origin and destination are on the same diagonal
               //     y<1    means the origin and destination are on the same horizontal/vertical line
 return
  p<1?x:                                //  For a king, just take the max distance.
  p<2?z*y<1?1:2:                        //  For a queen, just move once if in direct line, or twice.
  p<3?2-z%2:                            //  For a rook, just move once if on the same horizontal or vertical line, or twice
  p<4?                                  //  For a knight, 
   x+y<2?3:                             //   Hardcode 3 if moving to the next horizontal/vertical square
   (a<c?a+b:c+d)+x<2|x==2&z<1?4:        //   Hardcode 4 if moving 2 cases in diagonal or one case in diagonal in a corner.
   z+2*Math.ceil((y-z)/(y>z?3:4.)):     //   Compute the number of moves necessary for the usual cases
  z<1?1:                                //  For a bishop, hardcode 1 if they are on the same diagonal
   ~z*2&2;                              //   Return 2 if they have the same parity else 0.
}

Créditos

  • -2 bytes graças a Arnauld , bem como por me fazer perceber que eu tinha um problema com todos os meus casos de canto.
Olivier Grégoire
fonte
1

Carvão , 108 bytes

F…β⁸F⁸⊞υ⁺ι⊕κ≔⟦⟦η⟧⟧δW¬№§δ±¹ζ⊞δΦυΦ§δ±¹⁼⁵ΣEμX⁻℅ξ℅§κπ²≔Eη↔⁻℅ι℅§ζκε≡θKI⌈εQI∨∨¬⌊ε⁼⊟ε⊟ε²RI∨¬⌊ε²BI∧¬﹪Σε²∨⁼⊟ε⊟ε²NI⊖Lδ

Experimente online! Link é a versão detalhada do código. Explicação:

F…β⁸F⁸⊞υ⁺ι⊕κ

Liste todos os 64 quadrados do tabuleiro na variável de lista vazia predefinida.

≔⟦⟦η⟧⟧δ

Faça uma lista de listas cuja primeira entrada é uma lista que contém a posição inicial.

W¬№§δ±¹ζ

Repita até que a última entrada da lista contenha a posição final.

⊞δΦυΦ§δ±¹⁼⁵ΣEμX⁻℅ξ℅§κπ²

Filtre todas as posições do tabuleiro afastadas de qualquer entrada na última entrada da lista de listas e empurre-a para a lista de listas. Isso inclui as posições visitadas anteriormente, mas, de qualquer maneira, não estávamos interessadas nelas, então terminamos com uma primeira pesquisa abrangente do fórum sobre a posição final.

≔Eη↔⁻℅ι℅§ζκε

Calcule as diferenças absolutas de coordenadas entre as posições inicial e final.

≡θ

Selecione com base na peça de entrada.

KI⌈ε

Se for um rei, imprima a diferença máxima absoluta de coordenadas.

QI∨∨¬⌊ε⁼⊟ε⊟ε²

Se for uma dama, imprima 2, a menos que as duas diferenças sejam iguais ou uma seja zero.

RI∨¬⌊ε²

Se for uma torre, imprima 2, a menos que uma das diferenças seja zero.

BI∧¬﹪Σε²∨⁼⊟ε⊟ε²

Se for um bispo, imprima 0 se os quadrados tiverem paridade oposta, caso contrário, imprima 2, a menos que as duas diferenças sejam iguais.

NI⊖Lδ

Se for um cavaleiro, imprima o número de voltas realizadas para encontrar a posição final.

Neil
fonte
1

Japonês , 67 bytes

®ra
g[_rw}_â è}@=ã ü;@pUÌïVõ á ÈíaY})Ìde[TT]}a Ä}_è}_ra v *Zâ l}]gV

Experimente online!

Que foi uma experiência. Tomei muita inspiração na excelente resposta da APL . Suspeito que ainda haja muito golfe, especialmente no código Knight.

As posições são a primeira entrada, no formulário [[x1,x2],[y1,y2]]. Deve funcionar bem [[y1,y2],[x1,x2]]também. A seleção das peças é a segunda entrada, com 0 = rei, 1 = rainha, 2 = cavaleiro, 3 = torre, 4 = bispo. Observe que Knight e Rook são trocados em comparação com a resposta da APL.

Explicação:

®ra         :Turn absolute positions into relative movement and store in U
®           : For each of X and Y
 ra         : Get the absolute difference between the start position and the end position

g[...]gV    :Apply the appropriate function
 [...]      : A list of functions
      gV    : Get the one indicated by the second input
g           : Apply it to U

_rw}        :King function
 rw         : Get the maximum of X and Y

_â è}       :Queen function
 â          : Get unique elements
   è        : Count non-zero elements

@=ã ü;@pUÌï2õ á ÈíaY})Ìde[TT]}a Ä}  :Knight function
 =ã ü;                              : Wrap U twice (U -> [[U]])
      @                      }a Ä   : Repeat until True; return number of tries:
        UÌ                          :  Get the previous positions
          ï                         :  Cartesian product with:
           2õ                       :   The range [1,2]
              á                     :   All permutations, i.e. [[1,2],[2,1]]
                ÈíaY})              :  Apply each move to each position
       p                            :  Store the new positions
                      Ìde[TT]       :  True if any are at the destination

_è}         :Rook function
 è          : Count non-zero elements

_ra v *Zâ l}    :Bishop function
 ra             : Absolute difference between X and Y
    v           : Is divisible by 2? (returns 1 or 0)
      *         : Times:
       Zâ       :  Get the unique elements
          l     :  Count them
Kamil Drakari
fonte
@ETHproductions Boas sugestões. Enquanto eu os colocava, descobri que áfuncionava para diminuir [[1,2][2,1]]consideravelmente.
Kamil Drakari 28/11
Uau, nunca teria pensado em usar á, um bom!
ETHproductions
Mais algumas sugestões: Uestá implícito depois @, para que você possa salvar dois bytes na função knight. Você também pode iniciá-lo @=ã ü;para salvar outro. (O ãtruque é inteligente também :-))
ETHproductions
@ETHproductions Bom achado, os momentos em que U está implícito são uma das coisas que ainda não compreendi completamente.
Kamil Drakari 29/11