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.
x+yi
?Odpowiedzi:
Wolfram Language (Mathematica) , 64 bajty
Korzystanie z wbudowanego
KnightTourGraph
.Zaoszczędzono 2 bajty dzięki Mathe172 .
Wypróbuj online!
źródło
GraphDistance[KnightTourGraph@@({x,y}=Abs@{##}+5),2y+3,(x-2)y-2]&
JavaScript (ES6),
907572 bajtówZainspirowany wzorem podanym dla A065775 . Powoli jak diabli na (nie tak) duże odległości.
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) :
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*y
zamiast 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
źródło
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+y
nieparzystych, ax+y
nawet 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:
x+y
.2. Przybliżenie
Zakłada, że rycerz zaczyna od współrzędnych
(0,0)
, przesunąłn
kroki i jest obecnie na(x,y)
.Dla uproszczenia zakłada
x ≥ 0
,y ≥ 0
.Możemy stwierdzić:
x
zwiększa się co najwyżej2
,x ≤ 2×n
. Podobniey ≤ 2×n
.x+y
zwiększa się co najwyżej3
,x+y ≤ 3×n
.Dlatego
n ≥ l(x,y)
gdziel(x,y) = max(max(x,y)/2, (x+y)/3
. (zauważ, że nie musimy uwzględniać-x
anix-y
w formule, ponieważ z założeniax ≥ 0 and y ≥ 0
, więcx+y ≥ max(x-y,y-x,-x-y)
ix ≥ -x
,y ≥ -y
)Okazuje się, że
a(x,y) = round(0.4 + l(x,y))
jest to dobre przybliżenie don
.Załóżmy, że
a(x,y)
jest to przybliżenie z błędem mniejszym niż1
, poprawna wartość jest podana przez(zaokrąglić, odejmując
x+y
i dzieląc przez 2)3. Specjalne przypadki, które nie spełniają formuły
Załóżmy
x ≥ 0
iy ≥ 0
. Istnieją 2 specjalne przypadki, w których algorytm zawodzi:x == 1 and y == 0
lubx == 0 and y == 1
: Algorytm niepoprawnie zwraca,1
gdy poprawna odpowiedź to3
.x == y == 2
: Algorytm niepoprawnie zwraca,2
gdy jest poprawna odpowiedź4
.Więc tylko te specjalne przypadki. Dodaj wynik,
2
jeśli wartośćx
iy
są jedną z nich.źródło
x==y==0
.max(x+y,x-y,y-x)
?x ≥ 0
iy ≥ 0
”.Python 2 , 87 bajtów
Wypróbuj online!
Pobiera dane wejściowe jako liczbę zespoloną
z = complex(tx, ty)
.źródło
TI-Basic,
8654 bajtówNa podstawie starszego rozwiązania @ user202729
źródło
MATL , 29 bajtów
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!
źródło
Haskell,
7972 bajtówWypró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.
źródło
JavaScript (ES6),
9078 bajtówEdit: Saved 12 bajty dzięki @supercat wskazując, że
x<0
sugeruje alboy<0
albox<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):Wszystkie zaznaczone kwadraty
+
można ustalić, przesuwając się bezpośrednio w stronę początku, a następnie powtarzając.źródło
x<0
testu? Biorąc pod uwagę np. -3,6,x<y
test zmieniłby to w 6, -3, którey<0
test zmieniłby w 6,3, ax<y
test zmieniłby w 3,6.x>=y>=0
...Kotlin ,
148146140 bajtówWypróbuj online!
źródło
:Int
określać typu zwrotu.Galaretka ,
27262523 bajtówWypró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
Æi
i zastąpienie0
z0,0
drugiej linii.źródło