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.
x+yi
?Respostas:
Wolfram Language (Mathematica) , 64 bytes
Usando o built-in
KnightTourGraph
.Economizou 2 bytes graças ao Mathe172 .
Experimente online!
fonte
GraphDistance[KnightTourGraph@@({x,y}=Abs@{##}+5),2y+3,(x-2)y-2]&
JavaScript (ES6),
907572 bytesInspirado na fórmula dada para A065775 . Lento como o inferno por (não tão) longas distâncias.
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) :
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 usarz*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) :
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) :
x e y == 0 e x | y == 0 significa que já temos x = y = 0 .
Gráficos emprestados de chess.com
fonte
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 ex+y
pares são coloridas com cores diferentes).Observe que cada etapa deve pular entre duas células de cores diferentes. Assim sendo:
x+y
.2. Aproximação
Assume que o cavaleiro começa a partir de coordenadas
(0,0)
e moveun
etapas, e está atualmente em(x,y)
.Para simplicidade, assume
x ≥ 0
,y ≥ 0
.Podemos concluir:
x
aumenta em, no máximo2
,x ≤ 2×n
. Da mesma formay ≤ 2×n
,.x+y
aumenta em, no máximo3
,x+y ≤ 3×n
.Portanto,
n ≥ l(x,y)
ondel(x,y) = max(max(x,y)/2, (x+y)/3
. (observe que não precisamos incluir-x
oux-y
na fórmula porque, por suposição,,x ≥ 0 and y ≥ 0
entãox+y ≥ max(x-y,y-x,-x-y)
ex ≥ -x
,y ≥ -y
)Acontece que
a(x,y) = round(0.4 + l(x,y))
é uma boa aproximação paran
.Suponha que
a(x,y)
é uma aproximação com erro menor que1
, o valor correto é dado por(arredondar para subtrair
x+y
e dividir por 2)3. Casos especiais que falham na fórmula
Suponha
x ≥ 0
ey ≥ 0
. Existem 2 casos especiais em que o algoritmo falha:x == 1 and y == 0
oux == 0 and y == 1
: O algoritmo retorna incorretamente1
enquanto a resposta correta é3
.x == y == 2
: O algoritmo retorna incorretamente2
enquanto a resposta correta é4
.Então, apenas casos especiais. Adicione o resultado por
2
se o valor dex
ey
for um desses.fonte
x==y==0
.max(x+y,x-y,y-x)
?x ≥ 0
ey ≥ 0
".Python 2 , 87 bytes
Experimente online!
Recebe a entrada como um número complexo
z = complex(tx, ty)
.fonte
TI-Basic,
8654 bytesCom base na solução mais antiga do @ user202729
fonte
MATL , 29 bytes
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!
fonte
Haskell,
7972 bytesExperimente 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.
fonte
JavaScript (ES6),
9078 bytesEditar: salvou 12 bytes graças a @supercat apontando que
x<0
implica emy<0
oux<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):Todos os quadrados marcados
+
podem ser determinados movendo-se diretamente em direção à origem e depois recorrendo.fonte
x<0
teste? Dado, por exemplo, -3,6, ox<y
teste transformaria isso em 6, -3, que oy<0
teste se tornaria em 6,3, e ox<y
teste se tornaria em 3,6.x>=y>=0
...Kotlin ,
148146140 bytesExperimente online!
fonte
:Int
especificar o tipo de retorno.Geléia ,
27262523 bytesExperimente 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
Æi
e substituindo0
por0,0
na segunda linha.fonte