Kedekatan heksagonal

28

Contoh Hexagon Spiral

Gambar di atas menampilkan kisi heksagon segi enam. Setiap sel di grid diberi indeks, mulai dari pusat dan berputar berlawanan seperti yang ditunjukkan. Perhatikan bahwa kisi akan berlanjut tanpa batas - gambar di atas hanyalah bagian pertama. Segi enam berikutnya akan berdekatan dengan 60 dan 37.

Tugas Anda adalah menentukan apakah dua sel yang diberikan pada kisi ini berdekatan.

Tulis sebuah program atau fungsi yang, diberi dua indeks sel, mencetak / mengembalikan nilai kebenaran jika dua sel berdekatan, dan nilai palsu jika tidak.

Jika tidak dibatasi oleh alasan praktis, kode Anda secara teoritis harus berfungsi untuk input ukuran apa pun.

Kasus uji kebenaran:

0, 1
7, 18
8, 22
24, 45
40, 64
64, 65

Kasus uji Falsey:

6, 57
29, 90
21, 38
38, 60
40, 63
41, 39
40, 40

Ini adalah sehingga jawaban tersingkat dalam byte menang. Penjelasan, bahkan untuk bahasa non-esoterik, dianjurkan.

John Michael Law
sumber

Jawaban:

7

Elixir , 263 257 264 223 214 218 214 byte

a=fn x,y->i=&(&1*(&1-1)*3+1)
[x,y]=Enum.sort [x,y]
if x<1,do: y in 1..6,else: (y-x==1||fn->a=y-trunc i.((r=(:math.sqrt(12*x-3)+3)/6)+1)
t=trunc r
a in [0,1,rem(b=x-i.(t)+1, t)<1&&b-t*6!=0&&2]||b<2&&a==-1 end.())end

Cobalah online!

versi tanpa ungolfed

def get_ring(x) do
    1/6*(:math.sqrt(12*x-3)+3)
end

def inv_get_ring(x), do: x*(x-1)*3+1

def ring_base(x), do: inv_get_ring(trunc(x))

def is_corner(x) do
    ring = trunc(get_ring(x))
    inv_ring = ring_base(ring)
    stuff = (x-inv_ring+1)
    rem(stuff, ring) == 0
end

def is_last(x),do: ring_base(get_ring(x)+1)-1 == x
def is_first(x),do: ring_base(get_ring(x)) == x

def hex_adj(x, y) do
    {x, y} = {min(x,y), max(x,y)}
    cond do 
        x == 0 ->y in 1..6      
        y-x==1 -> true
        true ->
            adj = trunc(inv_get_ring(get_ring(x)+1))
            number = if is_corner(x)&&!is_last(x), do: 2, else: 1
            if y-adj in 0..number do
                true
            else
                is_first(x) && y == adj-1
            end
    end
end
  • trunc(number) Mengembalikan bagian bilangan bulat dari angka
  • rem(a,b) Mengembalikan sisa a / b
  • cond do end Ini sama dengan yang lain jika atau mengganti klausa kasus dalam banyak bahasa imperatif

Penjelasan

get_ring (indeks)

Menghitung "cincin" indeks.

Contoh: 1 untuk 1-6, 2 untuk 7-18, dll.

Ini hanya berlaku jika hasilnya floored. Angka trailing menunjukkan seberapa jauh ubin itu berada di sekitar cincin.

inv_get_ring (dering)

Menghitung kebalikan dari get_ring(index).

ring_base (dering)

Hitung indeks ubin pertama di atas ring.

is_corner (indeks)

Sudut adalah ubin yang memiliki tiga ubin adajcent di cincin luar. Cincin terdalam seluruhnya terdiri dari sudut.

Contoh: 21,24,27,30,33,36

is_last (indeks)

Benarkah indeks ini adalah yang tertinggi di cincinnya.

is_first (index)

Apakah benar jika ini adalah ubin dasar cincin.

Garuno
sumber
2
Saya telah mengedit jawaban untuk menyertakan perbaikan pada case tepi :)
Garuno
Saya mengikuti versi golf Anda melalui iterasi pertama tetapi kemudian sepertinya Anda mengubah pendekatan Anda. Apakah versi golf Anda saat ini masih setara dengan versi yang tidak disunat?
John Michael Law
Ya itu! Saya baru saja belajar bahwa Anda dapat mendeklarasikan variabel inline di Elixir. Ini memberi saya kemampuan untuk menyingkirkan fungsi lambda di awal kode. Saya hanya menyeret variabel sekitar sedikit, agar lebih efisien.
Garuno
5

MATL , 47 45 44 43 41 byte

s:"JH3/^6:^t5)w5:&)@qY"w@Y"]vYs0hG)d|Yo1=

Cobalah online! Atau verifikasi semua kasus uji .

Sebagai bonus, kode ini menghasilkan spiral heksagonal yang melacak posisi pusat sel, yang dapat dilihat secara grafis di MATL Online dengan memodifikasi bagian terakhir dari kode.

Penjelasan

Gagasan umum    Kode pertama kali membangun spiral heksagonal yang cukup besar dengan unit step. Spiral didefinisikan sebagai vektor bilangan kompleks yang mewakili posisi pusat sel. Pengindeksan ke vektor itu dengan angka-angka input dan menghitung perbedaan absolut memberi jarak antara dua sel yang ditunjukkan. Sel berdekatan jika dan hanya jika hasilnya 1. Namun, karena ketidaktepatan titik apung, pembulatan diperlukan sebelum membandingkan dengan 1.

Membangun spiral    Spiral akan memiliki jumlah "lapisan" yang sama dengan jumlah dari dua input. Ini (jauh) lebih besar dari yang diperlukan, dan memastikan bahwa sel-sel input akan hadir dalam spiral.

Untuk membangun spiral, bilangan kompleks j 2/3 (di mana j adalah unit imajiner) pertama kali dihitung. Menaikkan ini ke eksponen 1 hingga 6 memberikan satu set dasar perpindahan, sehingga mengikuti perpindahan itu agar dapat melacak hexagon. Heksagon ini akan membentuk lapisan spiral paling dalam, kecuali bahwa itu akan "tertutup". Sebenarnya, kami ingin hexagon itu "tumbuh" pada langkah terakhir dan kemudian kami melacak hexagon yang lebih besar, dengan dua kali lebih banyak poin (disejajarkan dalam kelompok dua), untuk membentuk lapisan spiral berikutnya; lihat ilustrasi di sini . Lapisan berikutnya akan memiliki tiga poin sebanyak poin pertama (dalam kelompok tiga); lihat di sini .

Untuk melakukan ini, perpindahan kelima dari perangkat dasar (yang menunjuk ke arah tenggara) dipilih sebagai langkah "tumbuh". Lapisan k dimulai dengan langkah itu, diikuti oleh lima langkah dasar pertama yang diulang k kali, diikuti oleh langkah keenam (arah timur) diulang k −1 kali. Mudah-mudahan ini menjadi lebih jelas dengan melihat dua angka yang terhubung di atas.

Vektor yang dihasilkan, termasuk semua lapisan, mewakili perpindahan kompleks yang akan melacak spiral. Jumlah kumulatif memberikan koordinat aktual dari pusat sel.

Terakhir, sel awal, yang terletak di 0, melekat pada ujung vektor ini. Ini karena MATL menggunakan pengindeksan berbasis 1 modular, dan indeks 0 merujuk pada entri terakhir array.

Menguji kedekatan    Dua sel yang diberikan oleh nomor input dipilih, koordinatnya dikurangi, dan nilai absolutnya dibulatkan dan dibandingkan dengan 1.

Kode yang dikomentari

s         % Implicitly input array of two numbers. Push their sum, say S
:         % Range [1 2 ... S]
"         % For each k in [1 2 ... S]
  J       %   Push 1j
  H3/     %   Push 2, then 3, then divide: gives 2/3
  ^       %   Power
  6:      %   Push [1 2 ... 6]
  ^       %   Element-wise power. This is the array of 6 basic displacements
  t5)     %   Duplicate. Get 5th entry
  w5:&)   %   Swap. Push subarray with entries 1st to 5th, then push 6th
  @qY"    %   Repeat the 6th displacement k-1 times
  w@Y"    %   Swap. Repeat 1st to 5th displacements k times
]         % End
v         % Concatenate everything into a column vector
Ys        % Cumulative sum. This gives the cell center coordinates
0h        % Append a 0
G)        % Index by the input vector
d|        % Absolute difference
Yo        % Round to nearest integer
1=        % Does it equal 1? Implicitly display
Luis Mendo
sumber
Bisakah Anda menambahkan penjelasan?
Shaggy
@ Shaggy saya menambahkan penjelasan umum. Beri tahu saya jika jelas (sulit dijelaskan). Saya akan menambahkan kode yang dikomentari nanti
Luis Mendo
2

05AB1E (warisan) , 30 29 27 byte

α2‹i1q}1ݹ+v12y*3-tîÌy+}Ÿ²å

Cobalah online!

Penjelasan kode:

α2‹i1q}                     : if the absolute diff of the two number is 1 or 0 return 1
                          ²å: return that the second number is in
                         Ÿ  : range of {
       1Ý                   :  create [0, 1]
         ¹+                 :  add the first number to the elements
           v            }   :  map that list
            12y*3-tîÌy+     :  calculate the corresponding value where it's an adjacency
                                }

Penjelasan matematika:

Saya "terbuang" sekitar 5 jam membuat golf ini. Singkatnya saya mulai membuat grafik input 2d, dan menggambar di Xmana mereka berdekatan satu sama lain. Kemudian saya menemukan sebuah pola. Saya mencarinya di OEIS dan bingo! Saya menemukan urutan itu dan saya menggunakan formula yang diberikan di situs web.

Kerrin
sumber
1

C (gcc) , 175 173 byte

Terimakasih untuk Peter Taylor untuk menangkap bug.

Berkat ceilingcat untuk -2 byte. Itu ~ operator terus menjadi blindspot utama saya.

c,r,C,L;y(a){a=a<L*2?L-a:a<L*3?-L:a<5*L?a-L*4:L;}z(a){L=ceil(sqrt(a/3.+.25)-.5);C=y(a-=3*L*~-L);L?L=y((L+a)%(L*6)):0;}f(a,b){z(a);c=C,r=L;z(b);a=a-b&&(abs(c-C)|abs(r-L))<2;}

Cobalah online!

Pendekatan ini difokuskan pada menemukan baris dan kolom dari dua sel dan membandingkannya; tetangga tidak dapat memiliki koordinat yang sesuai berbeda lebih dari 1. Bergerak dari pusat ke luar, kami mengamati bahwa setiap lapisan memiliki 6 sel lebih banyak dari sebelumnya. Ini berarti bahwa "indeks" tertinggi di setiap lapisan L adalah pada bentuk 6 * (L * (L - 1) * (L - 2) ...), atau C = 6 * (L 2 + L) / 2 , di mana C adalah nomor sel "global". Mengacak-acak, kami mendapatkan L 2 + L - C / 3 = 0, yang memberikan kilas balik matematika sekolah menengah. Dari itu, kita mendapatkan formula ceil (sqrt (1/4 + C / 3) + 0,5). Memasukkan indeks sel global ke dalamnya, kami menerima lapisan mana sel masuk

Karena sel pertama di setiap lapisan secara alami lebih tinggi dari yang tertinggi dari lapisan sebelumnya, kami menemukan L start = (6 * (L - 1) 2 + (L - 1)) / 2, yang disederhanakan menjadi 3 * (L 2 - L). Dari yang kita dapatkan indeks lapisan L index = C - L start .

Selanjutnya, kita melihat bahwa setiap lapisan terdiri dari enam bagian, masing-masing panjang L. Mulai dari timur laut dan berlawanan arah jarum jam, kita melihat bahwa untuk dua bagian pertama (1 <= L indeks <= 2 * L) , kita mendapatkan kolom dari L - L indeks . Bagian selanjutnya L * 2 <L index <= L * 3 memiliki semua sel yang berbagi satu kolom -L. Dua bagian berikutnya adalah L * 3 <L indeks <= L * 5 dengan kolomnya sesuai dengan indeks L - L * 4. Dan terakhir, bagian keenam semuanya memiliki sel pada kolom L. Kita dapat menggeser batas atas satu langkah untuk menyimpan beberapa byte dalam kode.

Jadi, bagaimana dengan baris? Untuk menggunakan kembali kode, kita membalikkan kisi sehingga sel 44 lurus ke atas. Kemudian kita menjalankan logika yang sama dengan kolom tetapi memanggil hasil "baris" kali ini. Tentu saja, alih-alih benar-benar memutar grid, kita hanya berjalan 1/6 putaran di sekitarnya.

gastropner
sumber
@ PeterTaylor Tangkapan yang bagus, terima kasih!
gastropner
1

Python 3, 150 byte

def h(a,b):
 L=[];i=1
 while len(L)<a+b:r=sum((i*[1j**(k/3)]for k in range(4,16,2)),[]);r[0]+=1;L+=r;i+=1
 return.9<abs(sum(L[min(a,b):max(a,b)]))<1.1

Solusi saya pada dasarnya mengikuti garis pemikiran yang sama dengan Luis Mendo di atas. Jika ditulis lebih mudah dibaca, kode ini cukup jelas:

def h(a,b):
    L=[]
    i=1
    while len(L)<a+b:
        l=sum((i*[1j**(k/3)]for k in range(4,16,2)),[])
        l[0]+=1
        L+=l
        i+=1
return .9<abs(sum(L[min(a,b):max(a,b)]))<1.1
  1. fungsi hmelakukan hal berikut:
  2. Daftar L akan berisi posisi (kompleks) dari setiap angka.
  3. i adalah nomor dering.
  4. Dalam loop sementara, cincin baru ditambahkan setiap iterasi. Alih-alih mencari tahu berapa banyak cincin yang kita butuhkan, kita terus membuat daftar sampai cukup panjang untuk mengandung + b, maka sudah pasti cukup lama untuk memuat salah satu dari mereka.
  5. 'daftar dering' l adalah gabungan dari 6 daftar len (i) dikalikan step-vector, di mana step-vector adalah 1j ** (2/3) untuk suatu daya. Rentang ini tidak dimulai pada 0 tetapi pada 4, yang menyebabkan rotasi seluruh kisi. Ini memungkinkan saya untuk melakukan:
  6. l[0]+=1 pada baris 6, yang merupakan langkah dari satu cincin ke cincin berikutnya.
  7. L+=l merangkai daftar lengkap dan daftar-dering.
  8. Daftar L hanya berisi vektor langkah, yang masih harus dijumlahkan (terintegrasi) untuk mendapatkan posisi. Fitur yang rapi di sini adalah kita bisa menjumlahkan irisan dari angka terendah ke tertinggi untuk mendapatkan jarak mereka! Karena kesalahan pembulatan, hasilnya tidak akan tepat 1, maka 0,9 <... <1.1. Menariknya, nol case h(0,0)atau h (0,1) dijaga secara implisit, karena jumlah daftar kosong adalah nol. Jika saya bisa yakin bahwa a<b, yaitu argumen akan datang dalam rangka meningkatkan, saya bisa mencukur habis lagi 14 byte dengan mengganti L[min(a,b):max(a,b)]dengan L[a:b], tapi sayangnya!

PS: Saya tidak tahu ini adalah tantangan lama, itu muncul di atas beberapa hari yang lalu, dan terus mengomel saya sejak :)

Hermen
sumber
Ini jawaban yang bagus! Jangan khawatir tentang jawaban yang terlambat, kami tidak benar-benar memiliki masalah dengan itu di sini di PPCG.
Rɪᴋᴇʀ
0

Mathematica, 111 105 104 byte

r=Floor[(1+Sqrt[(4#-1)/3])/2]&;t=Limit[Pi(#/(3x)+1-x),x->r@#]&;p=r@#*Exp[I*t@#]&;Round@Abs[p@#-p@#2]==1&

Penjelasan:

r=Floor[(1+Sqrt[(4#-1)/3])/2]&mendefinisikan fungsi ryang mengambil input #dan menghitung jarak (dalam jumlah sel) ke sel 0. Ia melakukan ini dengan mengeksploitasi pola dalam sel terakhir dari setiap jarak / dering: 0 = 3 (0 ^ 2 + 0), 6 = 3 (1 ^ 2 + 1), 18 = 3 (2 ^ 2 + 2), 36 = 3 (3 ^ 2 + 3), ... dan membalikkan rumus untuk pola itu. Perhatikan bahwa untuk sel 0, sebenarnya dibutuhkan lantai (1/2) + i * (sqrt (3) / 6), yang menghitung komponen-bijaksana untuk mendapatkan 0 + 0 * i = 0.

Dengan rdidefinisikan, r@#adalah cincin untuk sel #(di dalam definisi fungsi lain). #+3r@#-3(r@#)^2&tidak muncul dalam kode persis, tetapi dibutuhkan jumlah sel dan kurangi jumlah sel tertinggi di cincin dalam berikutnya, sehingga memberikan jawaban untuk pertanyaan "sel dari cincin mana saat ini?" Misalnya, sel 9 adalah sel ke-3 dari cincin 2, demikian r[9]juga output 2 dan#+3r@#-3(r@#)^2&[9] akan menghasilkan 3.

Apa yang dapat kita lakukan dengan fungsi di atas adalah menggunakannya untuk menemukan sudut kutub , sudut berlawanan arah jarum jam dari sinar "sel 0, sel 17, sel 58" ke sel yang dimaksud. Sel terakhir dari setiap cincin selalu pada sudut Pi / 6, dan kami mengelilingi sebuah cincin dalam penambahan Pi / (3 * ring_number). Jadi, secara teori, kita perlu menghitung sesuatu seperti Pi / 6 + (which_cell_of_the_current_ring) * Pi / (3 * ring_number). Namun, rotasi gambar tidak memengaruhi apa pun, sehingga kami dapat membuang bagian Pi / 6 (untuk menghemat 6 byte). Menggabungkan ini dengan formula sebelumnya dan menyederhanakan, kami dapatkanPi(#/(3r@#)+1-r@#)&

Sayangnya, ini tidak terdefinisi untuk sel 0 karena nomor cincinnya adalah 0, jadi kita perlu menyiasatinya. Solusi alami akan seperti itu t=If[#==0,0,Pi(#/(3r@#)+1-r@#)]&. Tetapi karena kita tidak peduli dengan sudut untuk sel 0 dan karena r@#diulang, kita sebenarnya dapat menyimpan byte di sinit=Limit[Pi(#/(3x)+1-x),x->r@#]&

Sekarang kita memiliki nomor cincin dan sudut, kita dapat menemukan posisi sel (tengah) sehingga kita dapat menguji kedekatan. Menemukan posisi yang sebenarnya mengganggu karena cincin itu heksagonal, tetapi kita bisa menganggap cincin itu lingkaran sempurna sehingga kita memperlakukan nomor cincin sebagai jarak ke pusat sel 0. Ini tidak akan menjadi masalah karena perkiraannya cukup dekat. Dengan menggunakan bentuk kutub dari bilangan kompleks , kita dapat mewakili posisi perkiraan ini di bidang kompleks dengan fungsi sederhana:p = r@#*Exp[I*t@#] &;

Jarak antara dua bilangan kompleks pada bidang kompleks diberikan oleh nilai absolut dari selisihnya, dan kemudian kita dapat membulatkan hasilnya untuk menangani kesalahan apa pun dari perkiraan, dan memeriksa apakah ini sama dengan 1. Fungsi yang akhirnya apakah karya ini tidak memiliki nama, tetapi ada Round@Abs[p@#-p@#2]==1&.


Anda dapat mencobanya secara online di kotak pasir Wolfram Cloud dengan menempelkan kode seperti berikut ini dan mengeklik Gear -> "Evaluate cell" atau menekan Shift + Enter atau numpad Enter:

r=Floor[(1+Sqrt[(4#-1)/3])/2]&;t=Limit[Pi(#/(3x)+1-x),x->r@#]&;p=r@#*Exp[I*t@#]&;Round@Abs[p@#-p@#2]==1&[24,45]

Atau untuk semua kasus uji:

r=Floor[(1+Sqrt[(4#-1)/3])/2]&;t=Limit[Pi(#/(3x)+1-x),x->r@#]&;p=r@#*Exp[I*t@#]&;Round@Abs[p@#-p@#2]==1&//MapThread[#,Transpose[{{0,1},{7,18},{8,22},{24,45},{40,64},{64,65},{6,57},{29,90},{21,38},{38,60},{40,63},{41,39},{40,40}}]]&
Tanda.
sumber