Dalam Catur, Ksatria di grid (x, y) dapat pindah ke (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) dalam satu langkah. Bayangkan papan catur tanpa batas dengan hanya Knight di (0, 0):
Berapa banyak langkah yang diperlukan untuk memindahkan seorang Knight dari (0, 0) ke (t x , t y )?
Input
Dua bilangan bulat: t x , t y ;
-100 <t x <100, -100 <t y <100
Keluaran
Langkah-langkah minimal yang diperlukan untuk memindahkan seorang Knight dari (0, 0) ke (t x , t y ).
Aturan
- golf kode
Testcases
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 terkait
Berikut adalah beberapa OEIS untuk dibaca lebih lanjut
- A018837 : Jumlah langkah untuk mencapai knight (n, 0) di papan catur tak terbatas.
- A018838 : Jumlah langkah untuk mencapai knight (n, n) di papan catur tak terbatas.
- A065775 : Array T dibaca oleh diagonal: T (i, j) = jumlah gerakan ksatria di papan catur (tak terbatas ke segala arah) yang diperlukan untuk berpindah dari (0,0) ke (i, j).
- A183041 : Jumlah paling sedikit gerakan knight dari (0,0) ke (n, 1) di papan catur tak terbatas.
x+yi
?Jawaban:
Bahasa Wolfram (Mathematica) , 64 byte
Menggunakan built-in
KnightTourGraph
.Disimpan 2 byte berkat Mathe172 .
Cobalah online!
sumber
GraphDistance[KnightTourGraph@@({x,y}=Abs@{##}+5),2y+3,(x-2)y-2]&
JavaScript (ES6),
907572 byteTerinspirasi oleh formula yang diberikan untuk A065775 . Lambat sekali untuk jarak yang jauh (tidak begitu).
Cobalah online!
Bagaimana?
Kami mendefinisikan z sebagai bitwise OR antara x dan y .
Langkah 1
Kami pertama-tama memastikan bahwa kami berada di kuadran tertentu dengan memaksa x dan y menjadi non-negatif. Selama z <0 (yang berarti x atau y negatif), kami memproses panggilan rekursif f (-y, x) :
Langkah 2
Meskipun kita memiliki z> 1 (yang berarti bahwa x atau y lebih besar dari 1 ), kita secara rekursif mencoba dua gerakan yang membawa kita lebih dekat ke (0, 0) : f (x-1, y-2) dan f ( x-2, y-1) . Kami akhirnya menjaga jalan terpendek.
Langkah # 3
Ketika z kurang dari atau sama dengan 1 , kita memiliki 3 kemungkinan yang diproses dengan
z*3^x&y
(kita bisa menggunakanz*3-x*y
):x & y == 1 menyiratkan x | y == 1 dan artinya x = y = 1 . Kami membutuhkan dua gerakan lagi untuk mencapai (0, 0) :
x & y == 0 dan x | y == 1 berarti kita memiliki x = 1 / y = 0 atau x = 0 / y = 1 . Kami membutuhkan tiga gerakan lagi untuk mencapai (0, 0) :
x & y == 0 dan x | y == 0 berarti kita sudah memiliki x = y = 0 .
Grafik dipinjam dari chess.com
sumber
Python 3 , 90 byte
Terima kasih tsh untuk -11 byte!
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
Cobalah online!
(pemformatan kode sebaris untuk menghindari pembaca harus menggulir. Maaf, tetapi saya harus memutar program saya)
Sangat sangat efisien.
Bagaimana saya bisa menemukan ini !?
1. Paritas
Asumsikan bahwa seluruh papan diwarnai dalam pola kotak-kotak (yaitu, sel dengan
x+y
ganjil danx+y
genap diwarnai dengan warna yang berbeda).Perhatikan bahwa setiap langkah harus melompat di antara dua sel berwarna berbeda. Karena itu:
x+y
.2. Perkiraan
Diasumsikan ksatria mulai dari koordinat
(0,0)
, dan telah pindahn
langkah, dan saat ini di(x,y)
.Untuk mempermudah, mengasumsikan
x ≥ 0
,y ≥ 0
.Kita dapat menyimpulkan:
x
meningkatkan oleh paling2
,x ≤ 2×n
. Demikian pulay ≤ 2×n
,.x+y
meningkatkan oleh paling3
,x+y ≤ 3×n
.Karena itu
n ≥ l(x,y)
dimanal(x,y) = max(max(x,y)/2, (x+y)/3
. (perhatikan bahwa kita tidak perlu memasukkan-x
ataux-y
dalam rumus karena dengan asumsix ≥ 0 and y ≥ 0
,, begitux+y ≥ max(x-y,y-x,-x-y)
danx ≥ -x
,y ≥ -y
)Ternyata itu
a(x,y) = round(0.4 + l(x,y))
adalah pendekatan yang bagus untukn
.Asumsikan
a(x,y)
adalah perkiraan dengan kesalahan kurang dari1
, nilai yang benar diberikan oleh(bulat di bawah mengurangi
x+y
dan membaginya dengan 2)3. Kasus khusus yang gagal rumus
Asumsikan
x ≥ 0
dany ≥ 0
. Ada 2 kasus khusus di mana algoritme gagal:x == 1 and y == 0
ataux == 0 and y == 1
: Algoritme secara salah mengembalikan1
jawaban yang benar3
.x == y == 2
: Algoritma salah mengembalikan2
sementara jawaban yang benar adalah4
.Jadi, hanya kasus khusus itu. Tambahkan hasilnya dengan
2
jika nilaix
dany
adalah salah satunya.sumber
x==y==0
.max(x+y,x-y,y-x)
?x ≥ 0
dany ≥ 0
".Python 2 , 87 byte
Cobalah online!
Mengambil input sebagai bilangan kompleks
z = complex(tx, ty)
.sumber
TI-Basic,
8654 byteBerdasarkan solusi lama @ user202729
sumber
MATL , 29 byte
Input adalah bilangan kompleks dengan bilangan bulat nyata dan imajiner.
Kode ini sangat tidak efisien. Persyaratan memorinya meningkat secara eksponensial dengan output. Ini habis dalam TIO untuk kasus uji dengan output melebihi 7.
Cobalah online!
sumber
Haskell,
7972 byteCobalah online!
Mengambil input sebagai daftar pasangan nomor tunggal .
Kekuatan kasar yang sederhana. Membutuhkan banyak waktu dan memori untuk hasil> 8. Dimulai dengan satu daftar elemen koordinat (input), berulang kali tambahkan semua posisi yang dapat dijangkau untuk setiap elemen hingga
(0,0)
ada dalam daftar ini. Catat tingkat rekursi dan kembalikan sebagai hasilnya.Edit: -7 byte terima kasih kepada @Lynn.
sumber
JavaScript (ES6),
9078 byteSunting: Disimpan 12 byte berkat @supercat yang
x<0
menunjukkan apakah ituy<0
ataux<y
. Penjelasan: Ini adalah solusi rekursif. Dua kondisi pertama hanya memastikan kuadran yang tepat untuk kondisi lainnya. Kondisi ketiga menghasilkan jawaban untuk koordinat dekat asal, sedangkan dua kondisi terakhir berurusan dengan dua kasus khusus lainnya (1 byte lebih pendek dari pengujian kedua gerakan):Semua kotak yang ditandai
+
dapat ditentukan dengan bergerak langsung ke arah asal dan kemudian berulang.sumber
x<0
tes? Diberikan misalnya -3,6,x<y
tes akan mengubahnya menjadi 6, -3, yangy<0
tesnya akan berubah menjadi 6,3, yangx<y
tesnya akan berubah menjadi 3,6.x>=y>=0
...Kotlin ,
148146140 byteCobalah online!
sumber
:Int
menentukan jenis pengembalian.Jelly ,
27262523 byteCobalah online!
Sangat lambat; time out pada TIO untuk output lebih dari 6. Mengambil bilangan kompleks sebagai input.
Penjelasan
Kode menggunakan bilangan kompleks karena lebih pendek pada langkah perantara dan juga tampaknya jauh lebih cepat; Anda juga bisa menggunakan pasangan dengan menghapus
Æi
dan mengganti0
dengan0,0
pada baris kedua.sumber