Jarak Ksatria

24

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.
tsh
sumber
Anda dapat mengambil referensi dari formula yang diberikan di oeis.org/A065775
tsh
2
Bisakah saya mengambil input sebagai bilangan kompleks x+yi?
Lynn
1
@lynn saya pikir itu dapat diterima.
tsh
@ user202729 memperbarui potongan kode untuk menunjukkan hasilnya.
tsh
Peta yang sangat bagus.
Willtech

Jawaban:

11

Bahasa Wolfram (Mathematica) , 64 byte

Menggunakan built-in KnightTourGraph.

Disimpan 2 byte berkat Mathe172 .

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

Cobalah online!

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

alephalpha
sumber
14
Mathematica builtins strike lagi
qwr
1
Sedikit lebih pendek:GraphDistance[KnightTourGraph@@({x,y}=Abs@{##}+5),2y+3,(x-2)y-2]&
Lukas Lang
Ada apa dengan bahasa ini? Kenapa semua built-in ini dimuat sebelumnya? Apakah mencoba menyelesaikan frasa dengan tab butuh waktu lama?
OganM
@OganM Mathematica tidak mendukung penyelesaian otomatis di antarmuka baris perintahnya. Penyelesaian otomatis di antarmuka notebook terlihat seperti ini .
alephalpha
1
@ OganM Mungkin pengembang menggunakan Trie (struktur data), atau hanya mencari biner pada daftar built-in yang diurutkan. Ya, mengapa pencarian linear? | Perhatikan bahwa Mathematica adalah bahasa sumber tertutup yang tidak bebas, jadi tidak ada yang tahu bagaimana sebenarnya alat prediksi. | Pemrogram sungguhan tidak membutuhkan pelengkapan otomatis. : P
user202729
7

JavaScript (ES6), 90 75 72 byte

Terinspirasi oleh formula yang diberikan untuk A065775 . Lambat sekali untuk jarak yang jauh (tidak begitu).

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

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

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

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 menggunakan z*3-x*y):

  • x & y == 1 menyiratkan x | y == 1 dan artinya x = y = 1 . Kami membutuhkan dua gerakan lagi untuk mencapai (0, 0) :

    2 bergerak

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

    3 bergerak

  • x & y == 0 dan x | y == 0 berarti kita sudah memiliki x = y = 0 .

Grafik dipinjam dari chess.com

Arnauld
sumber
5

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+yganjil dan x+ygenap diwarnai dengan warna yang berbeda).

Perhatikan bahwa setiap langkah harus melompat di antara dua sel berwarna berbeda. Karena itu:

  • Paritas dari jumlah langkah harus sama dengan paritas x+y.

2. Perkiraan

Diasumsikan ksatria mulai dari koordinat (0,0), dan telah pindah nlangkah, dan saat ini di (x,y).
Untuk mempermudah, mengasumsikan x ≥ 0, y ≥ 0.
Kita dapat menyimpulkan:

  • Karena setiap langkah xmeningkatkan oleh paling 2, x ≤ 2×n. Demikian pula y ≤ 2×n,.
  • Karena setiap langkah x+ymeningkatkan oleh paling 3, x+y ≤ 3×n.

Karena itu n ≥ l(x,y)dimana l(x,y) = max(max(x,y)/2, (x+y)/3. (perhatikan bahwa kita tidak perlu memasukkan -xatau x-ydalam rumus karena dengan asumsi x ≥ 0 and y ≥ 0,, begitu x+y ≥ max(x-y,y-x,-x-y)dan x ≥ -x, y ≥ -y)

Ternyata itu a(x,y) = round(0.4 + l(x,y))adalah pendekatan yang bagus untuk n.

  • Asumsikan a(x,y)adalah perkiraan dengan kesalahan kurang dari 1, nilai yang benar diberikan oleh

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

    (bulat di bawah mengurangi x+ydan membaginya dengan 2)

3. Kasus khusus yang gagal rumus

Asumsikan x ≥ 0dan y ≥ 0. Ada 2 kasus khusus di mana algoritme gagal:

  • x == 1 and y == 0atau x == 0 and y == 1: Algoritme secara salah mengembalikan 1jawaban yang benar 3.
  • x == y == 2: Algoritma salah mengembalikan 2sementara jawaban yang benar adalah 4.

Jadi, hanya kasus khusus itu. Tambahkan hasilnya dengan 2jika nilai xdan yadalah salah satunya.

pengguna202729
sumber
1
@ tsh Tapi itu juga benar x==y==0.
user202729
Mengapa max(x+y,x-y,y-x)?
tsh
@ tsh: Tidak, lihat: x = -5, y = 5. x + y = 0, abs (xy) = 10 dan karena itu x + y <abs (xy)
Nova
@Nova "Asumsikan x ≥ 0 dan y ≥ 0".
user202729
4

Python 2 , 87 byte

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

Cobalah online!

Mengambil input sebagai bilangan kompleks z = complex(tx, ty).

Lynn
sumber
4

TI-Basic, 86 54 byte

Berdasarkan solusi lama @ 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
sumber
2

MATL , 29 byte

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

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!

Luis Mendo
sumber
2

Haskell, 79 72 byte

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]

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

nimi
sumber
72 byte
Lynn
1

JavaScript (ES6), 90 78 byte

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

Sunting: Disimpan 12 byte berkat @supercat yang x<0menunjukkan apakah itu y<0atau x<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):

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

Semua kotak yang ditandai +dapat ditentukan dengan bergerak langsung ke arah asal dan kemudian berulang.

Neil
sumber
Apakah Anda perlu x<0tes? Diberikan misalnya -3,6, x<ytes akan mengubahnya menjadi 6, -3, yang y<0tesnya akan berubah menjadi 6,3, yang x<ytesnya akan berubah menjadi 3,6.
supercat
@ supercat Memang, seperti kata Python, x>=y>=0...
Neil
1

Kotlin , 148 146 140 byte

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

Cobalah online!

JohnWells
sumber
Cukup yakin Anda tidak perlu :Intmenentukan jenis pengembalian.
therealfarfetchd
Fungsi rekursif memang membutuhkan tipe pengembalian karena kompiler tidak cukup pintar untuk mengetahui jenisnya.
JohnWells
1
Oh, saya melewatkan panggilan rekursif. Whoops
therealfarfetchd
1

Jelly , 27 26 25 23 byte

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

Cobalah 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 Æidan mengganti 0dengan 0,0pada baris kedua.

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
sumber