Odległość rycerza

24

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.
tsh
źródło
Możesz odwołać się do wzoru podanego w oeis.org/A065775
tsh
2
Czy mogę brać dane wejściowe jako liczbę zespoloną x+yi?
Lynn
1
@lynn myślę, że jest to do przyjęcia.
tsh
@ user202729 zaktualizował fragment kodu, aby pokazać wynik.
tsh
Bardzo dobra mapa.
Willtech,

Odpowiedzi:

11

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!

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

alephalpha
źródło
14
Wbudowane matematyki uderzają ponownie
qwr
1
Nieco krótszy:GraphDistance[KnightTourGraph@@({x,y}=Abs@{##}+5),2y+3,(x-2)y-2]&
Lukas Lang
O co chodzi z tym językiem? Dlaczego wszystkie te wbudowane elementy są wstępnie załadowane? Czy próba uzupełnienia frazy tabulatorem trwa wieki?
OganM
@OganM Mathematica nie obsługuje automatycznego uzupełniania w interfejsie wiersza poleceń. Automatyczne uzupełnianie w interfejsie notebooka wygląda następująco .
alephalpha
1
@OganM Być może programiści używają Trie (struktura danych) lub po prostu wyszukiwania binarnego na liście posortowanych wbudowanych. Tak, dlaczego wyszukiwanie liniowe? | Zauważ, że Mathematica jest niewolnym językiem zamkniętym, więc nikt nie wie, jak faktycznie działa predyktor. | Prawdziwi programiści nie potrzebują automatycznego uzupełniania. : P
user202729,
7

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

    2 ruchy

  • 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) :

    3 ruchy

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

Grafika zapożyczona z chess.com

Arnauld
źródło
5

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.

użytkownik202729
źródło
1
@tsh Ale to też dotyczy prawdy x==y==0.
user202729,
Dlaczego max(x+y,x-y,y-x)?
tsh
@tsh: Nie, patrz: x = -5, y = 5. x + y = 0, abs (xy) = 10, a zatem x + y <abs (xy)
Nova
@Nova „Zakładaj x ≥ 0i y ≥ 0”.
user202729,
4

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

Lynn
źródło
4

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
Timtech
źródło
2

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!

Luis Mendo
źródło
2

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.

nimi
źródło
72 bajty
Lynn
1

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.

Neil
źródło
Potrzebujesz x<0testu? Biorąc pod uwagę np. -3,6, x<ytest zmieniłby to w 6, -3, które y<0test zmieniłby w 6,3, a x<ytest zmieniłby w 3,6.
supercat
@ supercat Rzeczywiście, jak powiedziałby Python, x>=y>=0...
Neil
1

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!

JohnWells
źródło
Jestem pewien, że nie musisz :Intokreślać typu zwrotu.
tamalfarfetchd
Funkcje rekurencyjne wymagają typu zwracanego, ponieważ kompilator nie jest wystarczająco inteligentny, aby ustalić typ.
JohnWells
1
Och, przegapiłem rekurencyjne połączenia. Ups
ściągnął
1

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.
PurkkaKoodari
źródło