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,y
pasangan:
____________________________________...
/\ /\ /\ /\ /\
/ \ 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,1
ke 2,1
, 4,1
atau 3,2
, tetapi tidak ke segitiga lain, karena itu akan menjadi titik persimpangan daripada tepi.
Misalnya, jarak dari 2,1
ke 5,2
adalah 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,y1
x2,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 kode-golf , 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
sumber
(a,b,x,y)->c(a,b,x,y,0)
(memanggil metode terpisahc
dengan empat argumen dan0
sebagai argumen kelima) untuk jawaban saya.Jawaban:
JavaScript (ES6),
8478 byteDisimpan 6 byte berkat Neil
Uji kasus
Tampilkan cuplikan kode
Solusi rekursif awal,
1008881Disimpan 12 byte berkat ETHproduk,
Disimpan 7 byte berkat Neil
Bagaimana itu bekerja
Meskipun pada dasarnya masih berlaku untuk versi saat ini, penjelasan berikut lebih spesifik mengacu pada versi awal:
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 diberikan oleh paritas x + y :
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 :
Uji kasus
Tampilkan cuplikan kode
sumber
n
variabel sama sekali dan hanya menambahkan 1 ke hasil setiap iterasi? ( Saya kira 90 karakter )&
cara yang dapat Anda lakukana+b+(b>d)&1
untuk menghemat 2 bytef=(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
Python 2, 74 byte
sumber
**(x^y^(Y>=y))
?Batch, 99 byte
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 terakhirx=%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
Menghitungsumber
Jelly , 24 byte
Cobalah online!
Mari kita panggil input . Saya bekerja dari formula feersum:(x,y),(X,Y)
Baris pertama menghitung , eksponen dalam rumus.¢=(Y≮y)+x+y
Baris terakhir pertama menghitung dan kemudian menghitung maksimum dari dan , di mana adalah fungsi di garis tengah.L=[|x−X|,|y−Y|] sum(L) f(L) f
Garis tengah, mengingat , menghitung , membawanya ke daya , lalu menambahkan .L=[a,b] −((a+b)mod2) ¢ 2b
sumber
raket / skema, 214 byte
sumber
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)
Cobalah online!
Kerusakan
sumber
©
keD
dan 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.M
perilaku akan terpengaruh oleh ini. Gagal untuk[[0, 127], [0, 0]]
.Python 2 ,
747271 byteCobalah 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 :
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:120∘ 90∘
Ini kemudian dapat di-golf dengan mencatat bahwa .−⌊aj+12⌋=⌊−aj2⌋
sumber
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.Pyth ,
3128 byteMenggunakan 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)
Coba di sini! atau Coba test suite!
Kerusakan
sumber
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)
Cobalah online! atau Coba test suite! (Menggunakan versi kode yang sedikit dimodifikasi (
®
bukan²
), milik Kevin Cruijssen )sumber
©+®
untukDŠ+
lebih mudah untuk mendirikan sebuah test suite. ;) Ini adalah suite tes itu, dan semua kasus uji memang berhasil (abaikan tajuk yang berantakan; p).Jelly ,
22 .. 1615 byteCobalah 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, y2
danx1, x2
.sumber
Java 8,
157190188144142141127 byte+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.
sumber
z*z<c*c
alih-alih(z<0?-z:z)<(c<0?-c:c)