Jarak Manhattan Triangular

26

The Manhattan jarak pada grid biasa adalah jumlah langkah orthogonal orang perlu mengambil untuk mencapai satu sel dari yang lain. Langkah-langkah ortogonal adalah langkah-langkah yang melewati tepi sel-sel kisi (yang bertentangan dengan sudut-sudut, yang akan memberi kita jarak Chebyshev ).

Kita dapat menentukan jarak yang sama pada grid lain, misalnya grid segitiga. Kami dapat mengatasi masing-masing sel dalam kisi dengan skema pengindeksan berikut, di mana setiap sel berisi x,ypasangan:

    ____________________________________...
   /\      /\      /\      /\      /\
  /  \ 1,0/  \ 3,0/  \ 5,0/  \ 7,0/  \
 / 0,0\  / 2,0\  / 4,0\  / 6,0\  / 8,0\
/______\/______\/______\/______\/______\...
\      /\      /\      /\      /\      /
 \ 0,1/  \ 2,1/  \ 4,1/  \ 6,1/  \ 8,1/
  \  / 1,1\  / 3,1\  / 5,1\  / 7,1\  /
   \/______\/______\/______\/______\/___...
   /\      /\      /\      /\      /\
  /  \ 1,2/  \ 3,2/  \ 5,2/  \ 7,2/  \
 / 0,2\  / 2,2\  / 4,2\  / 6,2\  / 8,2\  
/______\/______\/______\/______\/______\...
\      /\      /\      /\      /\      /
 \ 0,3/  \ 2,3/  \ 4,3/  \ 6,3/  \ 8,3/
  \  / 1,3\  / 3,3\  / 5,3\  / 7,3\  /
   \/______\/______\/______\/______\/___...
   /\      /\      /\      /\      /\
  .  .    .  .    .  .    .  .    .  .
 .    .  .    .  .    .  .    .  .    .

Sekarang jarak Manhattan pada grid ini lagi-lagi adalah jumlah minimal langkah melintasi tepi untuk bergerak dari satu sel ke sel lainnya. Jadi Anda dapat beralih dari 3,1ke 2,1, 4,1atau 3,2, tetapi tidak ke segitiga lain, karena itu akan menjadi titik persimpangan daripada tepi.

Misalnya, jarak dari 2,1ke 5,2adalah 4. Jalur terpendek umumnya tidak unik, tetapi salah satu cara untuk membuat jarak dalam 4 langkah adalah:

2,1 --> 3,1 --> 3,2 --> 4,2 --> 5,2

Tantangan

Diberikan dua pasangan koordinat dan dari skema pengalamatan di atas, kembalikan jarak Manhattan di antara mereka.x1,y1x2,y2

Anda dapat berasumsi bahwa keempat input adalah bilangan bulat non-negatif, masing-masing kurang dari 128. Anda dapat mengambilnya dalam urutan apa pun dan dikelompokkan secara sewenang-wenang (empat argumen terpisah, daftar empat bilangan bulat, dua pasang bilangan bulat, matriks 2x2, .. .).

Anda dapat menulis sebuah program atau fungsi dan menggunakan salah satu metode standar untuk menerima input dan memberikan output.

Anda dapat menggunakan bahasa pemrograman apa pun , tetapi perhatikan bahwa celah ini dilarang secara default.

Ini adalah , sehingga jawaban terpendek yang valid - diukur dalam byte - menang.

Uji Kasus

Setiap test case diberikan sebagai .x1,y1 x2,y2 => result

1,2 1,2 => 0
0,1 1,1 => 1
1,0 1,1 => 3
2,1 5,2 => 4
0,0 0,127 => 253
0,0 127,0 => 127
0,0 127,127 => 254
0,127 127,0 => 254
0,127 127,127 => 127
127,0 127,127 => 255
75,7 69,2 => 11
47,58 36,79 => 42
77,9 111,23 => 48
123,100 111,60 => 80
120,23 55,41 => 83
28,20 91,68 => 111
85,107 69,46 => 123
16,25 100,100 => 159
62,85 22,5 => 160
92,26 59,113 => 174
62,22 35,125 => 206
Martin Ender
sumber
Apakah celah yang menerima peringkat negatif bersih akan dimasukkan di antara celah resmi?
DavidC
@DavidC No. Dari pertanyaan celah: "[...] celah yang dijelaskan dalam jawaban apa pun di +5 atau di atas dan memiliki setidaknya dua kali lebih banyak jumlah upvotes karena downvotes dianggap dianggap tidak dapat diterima oleh komunitas "
Martin Ender
Apakah kami diizinkan mengambil input kelima, yang dimulai dari 0 secara default (hasilnya)? Maka saya tidak perlu menambahkan (a,b,x,y)->c(a,b,x,y,0)(memanggil metode terpisah cdengan empat argumen dan 0sebagai argumen kelima) untuk jawaban saya.
Kevin Cruijssen
3
@KevinCruijssen Tidak maaf. Tambahan, argumen tetap agak terlalu mudah disalahgunakan (dan hanya membiarkan 0 sebagai kasus khusus tampaknya aneh).
Martin Ender
@ MartinEnder Ok, pikir begitu, tapi tidak ada salahnya bertanya. Dalam hal itu, jawaban 190 byte saya tetap ada. Meskipun saya menjawab separuh setahun yang lalu, satu test case gagal. Datang di pertanyaan lagi sekarang, dan mampu memperbaiki bug dalam jawaban saya.
Kevin Cruijssen

Jawaban:

7

JavaScript (ES6), 84 78 byte

Disimpan 6 byte berkat Neil

(a,b,c,d,x=a>c?a-c:c-a,y=b>d?b-d:d-b,z=x>y?x:y)=>y+z+(x+z&1?a+b+(b>d)&1||-1:0)

Uji kasus

Solusi rekursif awal, 100 88 81

Disimpan 12 byte berkat ETHproduk,
Disimpan 7 byte berkat Neil

f=(a,b,c,d,e=b==d|a+b+(b>d)&1)=>a-c|b-d&&f(e?a+1-2*(a>c):a,e?b:b+1-2*(b>d),c,d)+1

Bagaimana itu bekerja

Meskipun pada dasarnya masih berlaku untuk versi saat ini, penjelasan berikut lebih spesifik mengacu pada versi awal:

f=(a,b,c,d)=>b-d?a+b+(b>d)&1?f(a+1-2*(a>c),b,c,d)+1:f(a,b+1-2*(b>d),c,d)+1:Math.abs(a-c)

Beralih dari (x0, y) ke (x1, y) adalah sepele karena kita dapat melintasi tepi lateral sepanjang jalan dari segitiga sumber ke target. Jarak Manhattan dalam hal ini adalah | x0 - x1 | .

Bagian yang sulit adalah langkah-langkah vertikal. Untuk beralih dari baris y0 ke baris y1 , kita harus memperhitungkan dua parameter ini:

  • Orientasi segitiga saat ini
  • Apakah y0 kurang atau lebih besar dari y1

Orientasi segitiga diberikan oleh paritas x + y :

  • jika itu genap, segitiga mengarah ke atas
  • jika aneh, segitiga mengarah ke bawah

Kita dapat turun dari segitiga naik-ke-titik (berguna ketika y0 <y1 ) dan ke atas dari segitiga ke bawah-ke-arah (berguna ketika y0> y1 ).

Dengan menggabungkan orientasi segitiga dengan perbandingan antara y0 dan y1 , kita mendapatkan rumus x + y0 + (y0> y1? 1: 0) yang hasilnya bahkan jika kita dapat pergi ke arah yang diinginkan dan aneh jika tidak.

Jika kita tidak dapat mencapai baris berikutnya secara langsung, pertama-tama kita perlu mendapatkan perataan yang benar dengan memperbarui x :

  • jika x belum sama dengan x1 , kami pasti ingin bergerak ke arah yang benar, jadi kami menambahkannya jika x kurang dari x1 dan kami mengurangi jika x lebih besar dari x1
  • jika x sudah sama dengan x1 , kita bisa menambah atau menguranginya

Uji kasus

Arnauld
sumber
Itu ... banyak operasi matematika yang sangat kecil ... Tapi tidak bisakah Anda melewatkan nvariabel sama sekali dan hanya menambahkan 1 ke hasil setiap iterasi? ( Saya kira 90 karakter )
ETHproduk
@ ETHproductions Sejujurnya, saya mempostingnya tanpa bermain golf yang serius. Tapi itu pasti hal pertama yang harus dilakukan. Terima kasih!
Arnauld
1
Juga, saya pikir operator diutamakan &cara yang dapat Anda lakukan a+b+(b>d)&1untuk menghemat 2 byte
ETHproduk
Turun ke 81, saya pikir:f=(a,b,c,d,e=b==d|a+b+(b>d)&1)=>a-c|b-d&&f(e?a+1-2*(a>c):a,e?b:b+1-2*(b>d),c,d)+1
Neil
Saya pikir itu mungkin untuk menyimpan byte lain menggunakan beberapa kari pintar.
Neil
5

Python 2, 74 byte

lambda x,y,X,Y:abs(y-Y)+max(x-X,X-x,abs(y-Y)+((x+y+X+Y)%-2)**(x^y^(Y>=y)))
feersum
sumber
1
Dapatkah Anda, silakan, menjelaskan bagian ini: **(x^y^(Y>=y))?
Dead Possum
1
@DeadPossum Bergerak dengan jarak 1 secara vertikal dapat mengambil 1 atau 3 gerakan; tidak ada cara untuk mengetahui dengan hanya melihat paritas sehingga Anda harus membandingkan nilai y.
feersum
2

Batch, 99 byte

@cmd/cset/a"x=%3-%1,x*=x>>31|1,y=%4-%2,w=y>>31,y*=w|1,z=x+(y+x&1)*(-(%1+%2+w&1)|1)-y,z*=z>>31,x+y+z

Penjelasan: Gerak hanya horizonal hanya mengambil perbedaan mutlak koordinat x Untuk x yang cukup besar, gerakan vertikal hanya membutuhkan satu langkah ekstra per perbedaan koordinat y mutlak, tetapi untuk x kecil, dibutuhkan empat langkah ekstra per dua perbedaan koordinat y, ditambah satu atau tiga langkah untuk perbedaan aneh. Ini dihitung sebagai dua langkah per perbedaan ditambah faktor koreksi. Semakin besar dari dua langkah yang dikoreksi dan jumlah perbedaan absolut maka hasilnya, meskipun ini sendiri dihitung sebagai semakin besar dari perbedaan koordinat y mutlak yang dikoreksi dan jarak koordinat x absolut yang ditambahkan ke perbedaan koordinat y mutlak tidak dikoreksi .

  • @cmd/cset/a" - Mengevaluasi ekspresi yang dipisahkan koma dan mencetak yang terakhir
  • x=%3-%1,x*=x>>31|1x=|x2x1|
  • y=%4-%2,w=y>>31,y*=w|1w=y1>y2y=|y2y1|
  • z=x+(y+x&1)*(-(%1+%2+w&1)|1)-yc=(y+(xmod2))(12((x1+y1+w)mod2)),z=x+cy
  • z*=z>>31,x+y+zMenghitungmax(x,yc)+y=x+ymin(0,x+cy)
Neil
sumber
2

Jelly , 24 byte

⁴<³¬Ḋ;³S
SḂN*¢+ḊḤ$
ạµS»Ç

Cobalah online!

Mari kita panggil input . Saya bekerja dari formula feersum:(x,y),(X,Y)

d=|yY|+max(|xX|,|yY|+((x+y+X+Y)mod2)xy(Yy))=|yY|+max(|xX|,|yY|+[(|xX|+|yY|mod2)]x+y+(Yy))=max(|xX|+|yY|,2|yY|+[(|xX|+|yY|mod2)](Yy)+x+y).

Baris pertama menghitung , eksponen dalam rumus.¢=(Yy)+x+y

Baris terakhir pertama menghitung dan kemudian menghitung maksimum dari dan , di mana adalah fungsi di garis tengah.L=[|xX|,|yY|]sum(L)f(L)f

Garis tengah, mengingat , menghitung , membawanya ke daya , lalu menambahkan .L=[a,b]((a+b)mod2)¢2b

Lynn
sumber
2

raket / skema, 214 byte

(define(f x y X Y)(let m((p x)(q y)(c 0))
(let((k(+ c 1))(d(- Y q)))
(cond((= 0(- X p)d)c)
((and(> d 0)(even?(+ p q)))(m p(+ q 1)k))
((and(< d 0)(odd?(+ p q)))(m p(- q 1)k))
((< p X)(m(+ p 1)q k))
(else(m(- p 1)q k))))))
Kevin
sumber
2

05AB1E , 24 byte

Port jawaban Pyth saya , yang pada gilirannya menggunakan pendekatan yang kira-kira sama dengan jawaban Python feersum . Mengambil input sebagai daftar pasangan koordinat, . Memperbaiki bug untuk +1 byte, lalu memperbaiki kesalahan lain untuk +1, tetapi yang menghasilkan hasil yang benar untuk semua kasus uji ...(x1,x2),(y1,y2)

ÆÄ`©I˜OÉ(IøнOIθD{Q+m+M®+

Cobalah online!

Kerusakan

ÆÄ` © I˜OÉ (IøнOIθD {Q + m + M® + Program lengkap. Saya mewakili input yang dievaluasi.
ÆÄ Kurangi pasangan dengan mengurangi, ambil nilai absolut.
  `© Buang mereka secara terpisah ke tumpukan dan simpan yang kedua
                            satu, | y1-y2 | dalam register C.
    I˜O Dorong jumlah input yang rata ke stack.
       É (Ambil paritasnya dan negasikan.
         Iøн Push [x1, y1].
            O Ambil x1 + y1 (jumlahkan).
             IθD {Q Lalu periksa apakah pasangan kedua disortir (y1 ≤ y2).
                  + Dan jumlahkan itu dengan x1 + y1.
                   m Eksponensial. Dorong paritas di atas ** hasilnya.
                    + Dan tambahkan perbedaan absolut kedua untuk itu.
                     M® + Hasilnya, dorong nomor terbesar di tumpukan
                            ditambah nilai yang disimpan dalam register C.
Tuan Xcoder
sumber
Saya tidak 100% yakin, tapi tidak bisa Anda mengubah ©ke Ddan menghapus ®? Tampaknya berfungsi untuk case yang saat ini ada di TIO Anda, tetapi saya tidak yakin apakah itu mengikuti jalur yang sama untuk setiap case.
Kevin Cruijssen
1
@KevinCruijssen EDIT : Tidak, karena Mperilaku akan terpengaruh oleh ini. Gagal untuk [[0, 127], [0, 0]].
Tn. Xcoder
2

Python 2 , 74 72 71 byte

lambda c,a,d,b:abs(a-b)+abs(a+(-c-a)/2-b-(-d-b)/2)+abs((c+a)/2-(d+b)/2)

Cobalah online! Tautan termasuk kasus uji. Sunting: Disimpan 2 byte berkat @ JoKing. Menyimpan byte lebih lanjut berkat @ Mr.Xcoder. Berdasarkan rumus berikut saya temukan dalam pertanyaan ini :

|aibi|+|(aiaj2)(bibj2)|+|aj+12bj+12|

Sistem koordinat berbeda dalam tiga cara; koordinat dipertukarkan (yang menjelaskan urutan nama parameter saya agak aneh), koordinat miring pada daripada (yang menjelaskan dua penambahan) dan koordinat dalam pertanyaan terkait menggunakan pengindeksan 1 rendah. Karena kami mengambil perbedaan, ini membatalkan sebagian besar waktu dan kami dibiarkan dengan:12090

|aibi|+|(aiaj+12)(bibj+12)|+|aj2bj2|

Ini kemudian dapat di-golf dengan mencatat bahwa .aj+12=aj2

Neil
sumber
Anda dapat menjadikannya one-liner dengan menghapus baris baru
Jo King
1
lambda c,a,d,b:abs(a-b)+abs(a+-(c+a)/2-b--(d+b)/2)+abs((c+a)/2-(d+b)/2)harus menghemat 3 byte.
Tn. Xcoder
1

Pyth , 31 28 byte

Menggunakan pendekatan yang kira-kira sama seperti pada jawaban Python feersum . Mengambil input sebagai daftar pasangan koordinat, . Memperbaiki bug untuk -1 byte.(x1,x2),(y1,y2)

+eKaMQg#hK+eK^%ssQ_2+shCQSIe

Coba di sini! atau Coba test suite!

Kerusakan

+ eKaMQg # hK + eK ^% ssQ_2xxFhCQSIe Program lengkap. Q = eval (input ()).
  KaMQ Menyimpan perbedaan [| x1-x2 |, | y1-y2 |] di K.
 e Ambil yang terakhir (| y1-y2 |).
+ g # Dan menambahkannya ke nilai terbesar antara:
        hK - Kepala K (| x1-x2 |)
          + - Dan hasil dari penambahan:
           eK Akhir K (| y1-y2 |).
             ^ - dengan hasil eksponensial:
              % ssQ_2 Jumlah dari Q rata, modulo -2.
                                        Menghasilkan -1 jika x1 + x2 + y1 + y2 ganjil, 0 sebaliknya.
                    xxFhCQSIe - oleh hasil dari ungkapan ini:
                       hCQ Transpose Q dan dapatkan kepala (x1, y1).
                     xF Mengurangi dengan XOR bitwise.
                          SIe Dan periksa apakah daftar [y1, y2] diurutkan.
                    x Setelah itu, xor hasilnya dengan bool (0/1).
Tuan Xcoder
sumber
1

05AB1E , 16 byte

Menggunakan versi modifikasi dari jawaban Neil , dioptimalkan untuk bahasa berbasis stack seperti 05AB1E. Mengambil input sebagai dua pasang koordinat, , dipisahkan oleh baris baru dari STDIN. Awalnya saya menggabungkannya dengan jawaban 05AB1E saya yang lain tetapi kemudian memutuskan untuk mempostingnya secara terpisah karena itu sangat, sangat berbeda.(x1,x2),(y1,y2)

+D(‚2÷Æ`²Æ©+®)ÄO

Cobalah online! atau Coba test suite! (Menggunakan versi kode yang sedikit dimodifikasi ( ®bukan ²), milik Kevin Cruijssen )

Tuan Xcoder
sumber
Jawaban bagus! Bukan sesuatu untuk golf, tetapi ketika Anda mengubah ©+®untuk DŠ+lebih mudah untuk mendirikan sebuah test suite. ;) Ini adalah suite tes itu, dan semua kasus uji memang berhasil (abaikan tajuk yang berantakan; p).
Kevin Cruijssen
@KevinCruijssen Saya memiliki itu sebagai versi alternatif, tetapi tidak terpikir oleh saya bahwa saya bisa menulis test suite ... Terima kasih, saya akan menambahkannya
Tn. Xcoder
1
@KevinCruijssen Saya bermain golf dua byte lebih (sangat jelas ...!), Dan berhasil mematahkan kompatibilitas test suite lebih banyak lagi, jadi saya menyimpannya apa adanya: P Terima kasih atas hasil pengeditannya.
Tn. Xcoder
1

Jelly , 22 .. 16 15 byte

ṭH,‘H_ɗɗ@+¥ḞIAS

Cobalah online!

Coba semua uji kasus.

Menggunakan metode @ Neil dalam jawaban ini yang menggunakan rumus yang dimodifikasi dari pertanyaan math.SE ini .

Mengambil koordinat sebagai argumen y1, y2dan x1, x2.

dylnan
sumber
1

Java 8, 157 190 188 144 142 141 127 byte

(a,b,x,y)->{int r=0,c=1,z=1;for(;(c|z)!=0;r--){c=x-a;z=y-b;if((z<0?-z:z)<(c<0?-c:c)|a%2!=b%2?z<0:z>0)b+=z<0?-1:1;else a+=c<0?-1:1;}return~r;}

+33 byte (157 → 190) karena perbaikan bug.
-44 bytes (188 → 144) mengonversi metode rekursif ke metode pengulangan tunggal.
-14 byte terima kasih kepada @ceilingcat .

Penjelasan:

Coba di sini.

(a,b,x,y)->{          // Method with four integers as parameter and integer return-type
                      // (a=x1; b=y1; x=x2; y=y2)
  int r=0,            //  Result-integer `r`, starting at 0
      c=1,z=1;        //  Temp integers for the differences, starting at 1 for now
  for(;(c|z)!=0;      //  Loop until both differences are 0
      r--){           //    After every iteration: decrease the result `r` by 1
    c=x-a;            //   Set `c` to x2 minus x1
    z=y-b;            //   Set `z` to y2 minus y1
    if(z*Z            //   If the absolute difference between y2 and y1
       <c*c)          //   is smaller than the absolute difference between x2 and x1
       |a%2!=b%2?     //   OR if the triangle at the current location is facing downwards
         z<0          //       and we have to go upwards,
        :z>0)         //      or it's facing upwards and we have to go downwards
      b+=z<0?-1:1;    //    In/decrease y1 by 1 depending on where we have to go
    else              //   Else:
     a+=c<0?-1:1;}    //    In/decrease x1 by 1 depending on where we have to go
  return~r;           //  Return `-r-1` as result
Kevin Cruijssen
sumber
1
Sarankan z*z<c*calih-alih(z<0?-z:z)<(c<0?-c:c)
ceilingcat
@ceilingcat Ah, bagus. Terima kasih!
Kevin Cruijssen