W szachach rycerz na siatce (x, y) może przejść do (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) w jednym kroku. Wyobraź sobie nieskończoną szachownicę z tylko rycerzem na (0, 0):

Ile kroków jest wymaganych, aby przenieść rycerza z (0, 0) na (t _x , t _y )?

Wejścia

Dwie liczby całkowite: t _x , t _y ;

-100 <t _x <100, -100 <t _y <100

Wydajność

Minimalne kroki potrzebne do przeniesienia rycerza z (0, 0) na (t _x , t _y ).

Zasady

• kod golfa

Przypadki testowe

  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}%)}`));

Powiązane OEIS

Oto kilka OEIS do dalszego czytania

• A018837 : Liczba kroków, które rycerz może osiągnąć (n, 0) na nieskończonej szachownicy.
• A018838 : Liczba kroków, które rycerz może osiągnąć (n, n) na nieskończonej szachownicy.
• A065775 : Tablica T odczytana przez przekątne: T (i, j) = najmniejsza liczba ruchów rycerza na szachownicy (nieskończona we wszystkich kierunkach) potrzebna do przejścia z (0,0) do (i, j).
• A183041 : Najmniejsza liczba ruchów rycerza od (0,0) do (n, 1) na nieskończonej szachownicy.

Wolfram Language (Mathematica) , 64 bajty

Korzystanie z wbudowanego KnightTourGraph.

Zaoszczędzono 2 bajty dzięki Mathe172 .

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

Wypróbuj online!

JavaScript (ES6), 90 75 72 bajtów

Zainspirowany wzorem podanym dla A065775 . Powoli jak diabli na (nie tak) duże odległości.

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

Wypróbuj online!

W jaki sposób?

Zdefiniować Z jako bitowego lub pomiędzy x i y .

Krok 1

Najpierw upewniamy się, że znajdujemy się w konkretnej ćwiartce, wymuszając, aby zarówno x, jak i y były nieujemne. Dopóki z <0 (co oznacza, że ​​albo x albo y jest ujemne), przetwarzamy wywołanie rekurencyjne f (-y, x) :

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

Krok 2

Chociaż mamy z> 1 (co oznacza, że ​​albo x albo y jest większe niż 1 ), rekurencyjnie próbujemy dwa ruchy, które zbliżają nas do (0, 0) : f (x-1, y-2) i f ( x-2, y-1) . W końcu utrzymujemy najkrótszą ścieżkę.

Krok 3

Gdy z jest mniejsze lub równe 1 , mamy 3 możliwości, które są przetwarzane z*3^x&y(możemy użyć z*3-x*yzamiast tego):

• x & y == 1 oznacza x | y == 1 i oznacza, że x = y = 1 . Potrzebujemy jeszcze dwóch ruchów, aby osiągnąć (0, 0) :

  

• x & y == 0 i x | y == 1 oznacza, że ​​mamy x = 1 / y = 0 lub x = 0 / y = 1 . Potrzebujemy jeszcze trzech ruchów, aby osiągnąć (0, 0) :

  

• x & y == 0 i x | y == 0 oznacza, że ​​mamy już x = y = 0 .

_{Grafika zapożyczona z chess.com}

Python 3 , 90 bajtów

Dzięki tsh za -11 bajtów!

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

Wypróbuj online!

(wbudowane formatowanie kodu, aby uniknąć konieczności przewijania przez czytelników. Przepraszam, ale muszę zagrać w golfa w moim programie)

Bardzo, bardzo wydajny.

Jak mogłem to wymyślić !?

1. Parzystość

Zakłada, że ​​cała plansza jest pokolorowana we wzór szachownicy (to znaczy komórki o x+ynieparzystych, a x+ynawet o różnych kolorach).

Pamiętaj, że każdy krok musi przeskakiwać między dwiema komórkami o różnych kolorach. W związku z tym:

• Parzystość liczby kroków musi być równa parzystości x+y.

2. Przybliżenie

Zakłada, że ​​rycerz zaczyna od współrzędnych (0,0), przesunął nkroki i jest obecnie na (x,y).
Dla uproszczenia zakłada x ≥ 0, y ≥ 0.
Możemy stwierdzić:

• Ponieważ każdy krok xzwiększa się co najwyżej 2, x ≤ 2×n. Podobnie y ≤ 2×n.
• Ponieważ każdy krok x+yzwiększa się co najwyżej 3, x+y ≤ 3×n.

Dlatego n ≥ l(x,y)gdzie l(x,y) = max(max(x,y)/2, (x+y)/3. (zauważ, że nie musimy uwzględniać -xani x-yw formule, ponieważ z założenia x ≥ 0 and y ≥ 0, więc x+y ≥ max(x-y,y-x,-x-y)i x ≥ -x, y ≥ -y)

Okazuje się, że a(x,y) = round(0.4 + l(x,y))jest to dobre przybliżenie do n.

• Załóżmy, że a(x,y)jest to przybliżenie z błędem mniejszym niż 1, poprawna wartość jest podana przez

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

  (zaokrąglić, odejmując x+yi dzieląc przez 2)

3. Specjalne przypadki, które nie spełniają formuły

Załóżmy x ≥ 0i y ≥ 0. Istnieją 2 specjalne przypadki, w których algorytm zawodzi:

• x == 1 and y == 0lub x == 0 and y == 1: Algorytm niepoprawnie zwraca, 1gdy poprawna odpowiedź to 3.
• x == y == 2: Algorytm niepoprawnie zwraca, 2gdy jest poprawna odpowiedź 4.

Więc tylko te specjalne przypadki. Dodaj wynik, 2jeśli wartość xi ysą jedną z nich.

Python 2 , 87 bajtów

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)})

Wypróbuj online!

Pobiera dane wejściowe jako liczbę zespoloną z = complex(tx, ty).

TI-Basic, 86 54 bajtów

Na podstawie starszego rozwiązania @ 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

MATL , 29 bajtów

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

Dane wejściowe to liczba zespolona z liczbami całkowitymi rzeczywistymi i urojonymi.

Kod jest bardzo nieefektywny. Wymagania dotyczące pamięci rosną wykładniczo wraz z wydajnością. Limit czasu w TIO dla przypadków testowych z wyjściem przekraczającym 7.

Wypróbuj online!

Haskell, 79 72 bajtów

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]

Wypróbuj online!

Pobiera dane wejściowe jako listę singletonów par liczb.

Prosta brutalna siła. Potrzebuje dużo czasu i pamięci na wyniki> 8. Zaczynając od pojedynczej listy współrzędnych (danych wejściowych), wielokrotnie dodawaj wszystkie pozycje, które można osiągnąć dla każdego elementu, aż(0,0) się na tej liście. Śledź poziom rekurencji i zwróć go w wyniku.

Edycja: -7 bajtów dzięki @Lynn.

JavaScript (ES6), 90 78 bajtów

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

Edit: Saved 12 bajty dzięki @supercat wskazując, że x<0sugeruje albo y<0albo x<y. Objaśnienie: Jest to rozwiązanie rekurencyjne. Dwa pierwsze warunki zapewniają po prostu właściwą ćwiartkę dla pozostałych warunków. Trzeci warunek generuje odpowiedź dla współrzędnych blisko początku, podczas gdy dwa ostatnie warunki dotyczą pozostałych dwóch specjalnych przypadków (1 bajt krótszy niż testowanie obu ruchów):

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

Wszystkie zaznaczone kwadraty +można ustalić, przesuwając się bezpośrednio w stronę początku, a następnie powtarzając.

Kotlin , 148 146 140 bajtów

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

Wypróbuj online!

Galaretka , 27 26 25 23 bajtów

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

Wypróbuj online!

Bardzo wolno; przekracza limit czasu TIO dla wyjść powyżej 6. Pobiera na wejściu liczbę zespoloną.

Wyjaśnienie

Kod używa liczb zespolonych, ponieważ w kroku pośrednim był krótszy i wydaje się także znacznie szybszy; można też użyć pary poprzez usunięcie Æii zastąpienie 0z 0,0drugiej linii.

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.