Distância Knight

24

No xadrez, um cavaleiro na grade (x, y) pode se mover para (x-2, y-1), (x-2, y + 1), (x-1, y-2), (x-1, y + 2), (x + 1, y-2), (x + 1, y + 2), (x + 2, y-1), (x + 2, y + 1) em uma etapa. Imagine um tabuleiro de xadrez infinito com apenas um cavaleiro ligado (0, 0):

Quantos passos são necessários para mover um Knight de (0, 0) para (t x , t y )?

Entradas

Dois inteiros: t x , t y ;

-100 <t x <100, -100 <t y <100

Saída

Etapas mínimas necessárias para mover um Cavaleiro de (0, 0) para (t x , t y ).

Regras

  • código de golfe

Casos de teste

  x    y -> out
  0,   0 ->  0
  0,   1 ->  3
  0,   2 ->  2
  1,   1 ->  2
  1,   2 ->  1
  3,   3 ->  2
  4,   0 ->  2
 42,  22 -> 22
 84,  73 -> 53
 45,  66 -> 37
 99,  99 -> 66
-45, -91 -> 46
-81,   1 -> 42
 11,  -2 ->  7

document.write('<div>');[..."EFEDEDCDCBCBCBCBCBCBCBCBCBCBCBCBCBCDCDEDEFE;FEDEDCDCBCBABABABABABABABABABABABCBCDCDEDEF;EDEDCDCBCBABABABABABABABABABABABABCBCDCDEDE;DEDCDCBCBABA9A9A9A9A9A9A9A9A9A9ABABCBCDCDED;EDCDCBCBABA9A9A9A9A9A9A9A9A9A9A9ABABCBCDCDE;DCDCBCBABA9A9898989898989898989A9ABABCBCDCD;CDCBCBABA9A989898989898989898989A9ABABCBCDC;DCBCBABA9A98987878787878787878989A9ABABCBCD;CBCBABA9A9898787878787878787878989A9ABABCBC;BCBABA9A989878767676767676767878989A9ABABCB;CBABA9A98987876767676767676767878989A9ABABC;BABA9A9898787676565656565656767878989A9ABAB;CBA9A989878767656565656565656767878989A9ABC;BABA98987876765654545454545656767878989ABAB;CBA9A987876765654545454545456567678789A9ABC;BABA98987676565454343434345456567678989ABAB;CBA9A987876565454343434343454565678789A9ABC;BABA98987676545434323232343454567678989ABAB;CBA9A987876565434323232323434565678789A9ABC;BABA98987676545432341214323454567678989ABAB;CBA9A987876565434321232123434565678789A9ABC;BABA98987676545432323032323454567678989ABAB;CBA9A987876565434321232123434565678789A9ABC;BABA98987676545432341214323454567678989ABAB;CBA9A987876565434323232323434565678789A9ABC;BABA98987676545434323232343454567678989ABAB;CBA9A987876565454343434343454565678789A9ABC;BABA98987676565454343434345456567678989ABAB;CBA9A987876765654545454545456567678789A9ABC;BABA98987876765654545454545656767878989ABAB;CBA9A989878767656565656565656767878989A9ABC;BABA9A9898787676565656565656767878989A9ABAB;CBABA9A98987876767676767676767878989A9ABABC;BCBABA9A989878767676767676767878989A9ABABCB;CBCBABA9A9898787878787878787878989A9ABABCBC;DCBCBABA9A98987878787878787878989A9ABABCBCD;CDCBCBABA9A989898989898989898989A9ABABCBCDC;DCDCBCBABA9A9898989898989898989A9ABABCBCDCD;EDCDCBCBABA9A9A9A9A9A9A9A9A9A9A9ABABCBCDCDE;DEDCDCBCBABA9A9A9A9A9A9A9A9A9A9ABABCBCDCDED;EDEDCDCBCBABABABABABABABABABABABABCBCDCDEDE;FEDEDCDCBCBABABABABABABABABABABABCBCDCDEDEF;EFEDEDCDCBCBCBCBCBCBCBCBCBCBCBCBCBCDCDEDEFE"].forEach(c=>document.write(c==';'?'<br>':`<span class="d-${c}">${c}</span>`));
document.write('<style>body{line-height:16px;color:rgba(255,255,255,0.2);}span{display:inline-block;width:16px;font-size:16px;text-align:center;}div{white-space:pre;}');[...'0123456789ABCDEF'].map((c,i)=>document.write(`.d-${c}{background:hsl(${60-4*i},80%,${65-2*i}%)}`));

OEIS relacionado

Aqui estão alguns OEIS para leitura adicional

  • A018837 : Número de etapas para o cavaleiro alcançar (n, 0) no tabuleiro de xadrez infinito.
  • A018838 : Número de etapas para o cavaleiro alcançar (n, n) no tabuleiro de xadrez infinito.
  • A065775 : Matriz T lida pelas diagonais: T (i, j) = menor número de movimentos do cavaleiro em um tabuleiro de xadrez (infinito em todas as direções) necessário para se mover de (0,0) para (i, j).
  • A183041 : Menor número de movimentos do cavaleiro de (0,0) para (n, 1) no tabuleiro de xadrez infinito.
tsh
fonte
Você pode fazer uma referência à fórmula dada em oeis.org/A065775
tsh
2
Posso aceitar a entrada como um número complexo x+yi?
27418 Lynn
11
@lynn eu acho que é aceitável.
TSH
@ user202729 atualizou o snippet de código para mostrar o resultado.
TSH
Um mapa muito bom.
Willtech # 03

Respostas:

11

Wolfram Language (Mathematica) , 64 bytes

Usando o built-in KnightTourGraph.

Economizou 2 bytes graças ao Mathe172 .

GraphDistance[KnightTourGraph@@({x,y}=Abs@{##}+4),y+2,(x-2)y-2]&

Experimente online!

ArrayPlot @ Array [GraphDistance [KnightTourGraph @@ ({x, y} = Abs @ {##} + 5), 2y + 3, (x-2) y-2] &, {65,65}, - 32]

alefalpha
fonte
14
Mathematica builtins strike novamente
qwr
11
Um pouco mais curto:GraphDistance[KnightTourGraph@@({x,y}=Abs@{##}+5),2y+3,(x-2)y-2]&
Lukas Lang
O que há com esse idioma? Como é que todos esses built-ins são pré-carregados? A tentativa de completar uma frase com a guia leva anos?
OganM
O @OganM Mathematica não suporta a conclusão automática em sua interface de linha de comando. A conclusão automática na interface do notebook se parece com isso .
precisa saber é o seguinte
11
@OganM Talvez os desenvolvedores usem um Trie (estrutura de dados) ou apenas uma pesquisa binária na lista de built-ins classificados. Sim, por que pesquisa linear? | Observe que o Mathematica é uma linguagem de código fechado não-livre, portanto, ninguém sabe como o preditor realmente funciona. | Programadores reais não precisam de preenchimento automático. : P
user202729
7

JavaScript (ES6), 90 75 72 bytes

Inspirado na fórmula dada para A065775 . Lento como o inferno por (não tão) longas distâncias.

f=(x,y,z=x|y)=>z<0?f(-y,x):z>1?1+Math.min(f(x-1,y-2),f(x-2,y-1)):z*3^x&y

Experimente online!

Quão?

Definimos z como o OR bit a bit entre x e y .

Passo 1

Primeiro, garantimos que estamos localizados em um quadrante específico, forçando x e y a não serem negativos. Enquanto z <0 (o que significa que x ou y é negativo), processamos a chamada recursiva f (-y, x) :

(+1, -2) --> (+2, +1)
(-1, +2) --> (-2, -1) --> (+1, -2) --> (+2, +1)
(-1, -2) --> (+2, -1) --> (+1, +2)

Passo 2

Enquanto nós temos z> 1 (o que significa que ou x ou y é maior do que 1 ), nós recursivamente tentar os dois movimentos que nos trazem mais perto de (0, 0) : f (x-1, y-2) e f ( x-2, y-1) . Eventualmente, mantemos o caminho mais curto.

Etapa 3

Quando z é menor ou igual a 1 , temos três possibilidades processadas z*3^x&y(poderíamos usar z*3-x*y):

  • x & y == 1 implica x | y == 1 e significa que x = y = 1 . Precisamos de mais dois movimentos para alcançar (0, 0) :

    2 movimentos

  • x e y == 0 e x | y == 1 significa que temos x = 1 / y = 0 ou x = 0 / y = 1 . Precisamos de mais três movimentos para alcançar (0, 0) :

    3 movimentos

  • x e y == 0 e x | y == 0 significa que já temos x = y = 0 .

Gráficos emprestados de chess.com

Arnauld
fonte
5

Python 3 , 90 bytes

Obrigado tsh por -11 bytes!

def f(x,y):x=abs(x);y=abs(y);s=x+y;return(.9+max(x/4,y/4,s/6)-s/2+(s==1or x==y==2))//1*2+s

Experimente online!

(formatação de código em linha para evitar que os leitores tenham que rolar. Desculpe, mas tenho que jogar golfe no meu programa)

Muito, muito eficiente.


Como eu pude pensar nisso !?

1. Paridade

Supõe que o quadro inteiro seja colorido no padrão quadriculado (ou seja, células com x+yímpares e x+ypares são coloridas com cores diferentes).

Observe que cada etapa deve pular entre duas células de cores diferentes. Assim sendo:

  • A paridade do número de etapas deve ser igual à paridade de x+y.

2. Aproximação

Assume que o cavaleiro começa a partir de coordenadas (0,0)e moveu netapas, e está atualmente em (x,y).
Para simplicidade, assume x ≥ 0, y ≥ 0.
Podemos concluir:

  • Uma vez que cada etapa xaumenta em, no máximo 2, x ≤ 2×n. Da mesma forma y ≤ 2×n,.
  • Uma vez que cada etapa x+yaumenta em, no máximo 3, x+y ≤ 3×n.

Portanto, n ≥ l(x,y)onde l(x,y) = max(max(x,y)/2, (x+y)/3. (observe que não precisamos incluir -xou x-yna fórmula porque, por suposição,, x ≥ 0 and y ≥ 0então x+y ≥ max(x-y,y-x,-x-y)e x ≥ -x, y ≥ -y)

Acontece que a(x,y) = round(0.4 + l(x,y))é uma boa aproximação para n.

  • Suponha que a(x,y)é uma aproximação com erro menor que 1, o valor correto é dado por

    f(x,y) = round((a(x,y) - (x+y)) / 2) * 2 + (x+y)

    (arredondar para subtrair x+ye dividir por 2)

3. Casos especiais que falham na fórmula

Suponha x ≥ 0e y ≥ 0. Existem 2 casos especiais em que o algoritmo falha:

  • x == 1 and y == 0ou x == 0 and y == 1: O algoritmo retorna incorretamente 1enquanto a resposta correta é 3.
  • x == y == 2: O algoritmo retorna incorretamente 2enquanto a resposta correta é 4.

Então, apenas casos especiais. Adicione o resultado por 2se o valor de xe yfor um desses.

user202729
fonte
11
@tsh Mas isso também é verdade x==y==0.
usar o seguinte comando
Por que max(x+y,x-y,y-x)?
TSH
@tsh: Não, veja: x = -5, y = 5. x + y = 0, abs (xy) = 10 e, portanto, x + y <abs (xy)
Nova
@Nova "Suponha x ≥ 0e y ≥ 0".
usar o seguinte comando
4

Python 2 , 87 bytes

f=lambda z,a={0}:1-({z}<=a)and-~f(z,{k+1j**i*(2-i/4*4+1j)for k in a for i in range(8)})

Experimente online!

Recebe a entrada como um número complexo z = complex(tx, ty).

Lynn
fonte
4

TI-Basic, 86 54 bytes

Com base na solução mais antiga do @ user202729

Input :abs(X->C:abs(Y->D:C+Ans
Ans+2int(.9+(S=1 or C=2 and D=2)-.5Ans+max({C/4,D/4,Ans/6
Timtech
fonte
2

MATL , 29 bytes

`JEQ2J-htZjht_h@Z^2&sG=~}@Gg*

A entrada é um número complexo com partes reais e imaginárias inteiras.

O código é muito ineficiente. Seus requisitos de memória aumentam exponencialmente com a saída. O tempo limite é excedido no TIO para os casos de teste com saída superior a 7.

Experimente online!

Luis Mendo
fonte
2

Haskell, 79 72 bytes

p l|elem(0,0)l=0|r<-[-2..2]=1+p[(x+i,y+j)|(x,y)<-l,i<-r,j<-r,(i*j)^2==4]

Experimente online!

Toma a entrada como uma lista única de pares de números.

Uma força bruta simples. Precisa de muito tempo e memória para obter resultados> 8. Começando com uma lista de coordenadas de um único elemento (a entrada), adicione repetidamente todas as posições que podem ser alcançadas para cada elemento até que (0,0)esteja nesta lista. Acompanhe o nível de recursão e retorne-o como resultado.

Editar: -7 bytes graças a @Lynn.

nimi
fonte
72 bytes
Lynn
1

JavaScript (ES6), 90 78 bytes

f=(x,y)=>y<0?f(x,-y):x<y?f(y,x):x+y<3?4-x-y&3:x-3|y-1?x-4|y-3?f(x-2,y-1)+1:3:2

Editar: salvou 12 bytes graças a @supercat apontando que x<0implica em y<0ou x<y. Explicação: Esta é uma solução recursiva. As duas primeiras condições apenas garantem o quadrante certo para as outras condições. A terceira condição gera a resposta para coordenadas próximas à origem, enquanto as duas últimas condições lidam com os outros dois casos especiais (1 byte menor que o teste de ambos os movimentos):

0
32
2++
+2++
+++3+
++++++
(etc.)

Todos os quadrados marcados +podem ser determinados movendo-se diretamente em direção à origem e depois recorrendo.

Neil
fonte
Você precisa do x<0teste? Dado, por exemplo, -3,6, o x<yteste transformaria isso em 6, -3, que o y<0teste se tornaria em 6,3, e o x<yteste se tornaria em 3,6.
Supercat
@supercat De fato, como Python diria, x>=y>=0...
Neil
1

Kotlin , 148 146 140 bytes

fun s(x:Int,y:Int):Int=if(y<0)s(x,-y)else
if(x<y)s(y,x)else if(x+y<3)4-x-y and 3
else if(x!=3||y!=1)if(x!=4||y!=3)s(x-2,y-1)+1
else 3 else 2

Experimente online!

JohnWells
fonte
Certamente você não precisa :Intespecificar o tipo de retorno.
Therealfarfetchd
Funções recursivas exigem tipo de retorno, pois o compilador não é inteligente o suficiente para descobrir o tipo.
31518 JohnWells
11
Ah, eu perdi as ligações recursivas. Whoops
therealfarfetchd
1

Geléia , 27 26 25 23 bytes

1,-pḤµ;UÆị
¢ṗS€;0i
0ç1#

Experimente online!

Muito devagar; atinge o tempo limite no TIO para saídas acima de 6. Toma um número complexo como entrada.

Explicação

O código usa números complexos porque foi mais curto em uma etapa intermediária e também parece muito mais rápido; você também pode usar pares removendo Æie substituindo 0por 0,0na segunda linha.

1,-pḤµ;UÆị    Helper link. No arguments.
1,-             Get the pair [1,-1].
    Ḥ           Double each to get [2,-2].
   p            Cartesian product: get [[1,2],[1,-2],[-1,2],[-1,-2]].
     µ          Start a new chain with the list of pairs as argument.
       U        Reverse each pair.
      ;         Append the reversed pairs to the list.
        Æi      Convert each pair [real,imag] to a complex number.

¢ṗS€;0i    Helper link. Arguments: iterations, target
¢            Call the previous link to get knight moves as complex numbers.
 ṗ           Get the iterations-th Cartesian power of the list. This will
             yield 8^n tuples containing move sequences.
  S€         Sum each move sequence to get the resulting square.
    ;0       Add the starting square, since the zeroth iteration results
             in no move sequences.
      i      Find the target squares (1-based) index in the results, or 0.

0ç1#    Main link. Argument: target
0         Starting from 0,
   #      find the
  1       first number of iterations where
 ç        calling the previous link results in a nonzero result.
PurkkaKoodari
fonte