Gauss ke Eisenstein

18

Dengan bilangan bulat Gaussian a+bi mana a , b adalah bilangan bulat dan i=exp(πi/2) adalah unit imajiner, kembalikan yang terdekat (wrt ke jarak Euclidean) Bilangan bulat Eisenstein k+lω mana k , l berada bilangan bulat dan ω=exp(2πi/3)=(1+i3)/2.

Latar Belakang

Hal ini mungkin cukup jelas bahwa setiap bilangan bulat Gaussian dapat unik ditulis sebagai a+bi dengan a , b bilangan bulat. Itu tidak begitu jelas tetapi tetap benar: Setiap integer Eisenstein dapat secara unik ditulis sebagai k+lω dengan k , l integer. Keduanya membentuk Z modul dalam bilangan kompleks, dan keduanya bilangan bulat c-thotomic untuk masing-masing p=2 atau 3 . Perhatikan bahwa 3+2i3+2ω

Sumber: commons.wikimedia.org

Detail

  • Dalam hal bilangan kompleks yang diberikan memiliki dua atau tiga titik terdekat, salah satu dari mereka dapat dikembalikan.

  • Bilangan kompleks diberikan dalam koordinat persegi panjang (basis (1,i) ), tetapi selain itu dalam format yang mudah seperti (A,B)atau A+Biatau A+B*1jdll.

  • Bilangan bulat Eisenstein harus dikembalikan sebagai koordinat basis (1,ω) tetapi selain itu dalam format yang mudah seperti (K,L)atau K+Lωatau K+L*1ωdll.

Contohnya

Semua bilangan bulat nyata jelas harus dipetakan ke bilangan bulat nyata lagi.

  6,14 -> 14,16
  7,16 -> 16,18
-18,-2 ->-19,-2
 -2, 2 -> -1, 2
 -1, 3 -> 1, 4
cacat
sumber
Bagus, saya tidak ingat melihat kisi heksagonal sejak codegolf.stackexchange.com/q/70017/17602
Neil
Terkait
Lynn
Anda juga harus memasukkan test case ketika a dan b memiliki tanda yang berlawanan.
SmileAndNod
@SmileAndNod Menambahkan satu. Tetapi orang juga bisa menggunakan simetri sehubungan dengan sumbu nyata dan hanya mengganti (1,w)dengan (-1,1+w). Dan saya juga mengganti nama bagian ini menjadi Contoh untuk menjelaskan bahwa tidak cukup hanya memberikan hasil yang tepat untuk kasus ini.
flawr

Jawaban:

7

APL (Dyalog Extended) , 16 byte SBCS

0+⌈3÷⍨1 2×⌊⎕×√3

Cobalah online!

Sebuah program penuh yang mengambil ymaka xdari input standar dan mencetak vektor 2-unsur bilangan bulat.

Cara kerjanya: matematika

Pertama-tama, perhatikan bahwa bilangan bulat Gaussian akan ditempatkan pada diagonal vertikal berlian, dengan titik Z ditempatkan pada (x,3y)untuk beberapa bilangan bulatx,y.

      + W
     /|\
    / | \
   /  |  \
  /   + X \
 /    |    \
+-----|-----+V
 \    |    /
  \   + Y /
   \  |  /
    \ | /
     \|/
      + Z

Dalam gambar, WZ¯=3 danWX¯=XY¯=YZ¯=XV¯=YV¯=13 . Jadi, mengingat posisi vertikal suatu titik, kita dapat mengidentifikasi titik Eisenstein terdekat sebagai berikut:

Given a point PWZ¯,{PWX¯the nearest point is WPXY¯the nearest point is VPYZ¯the nearest point is Z

Diberi Gaussian point P , pertama-tama kita menentukan berlian P milik, diukur dengan berapa banyak berlian (dilambangkan h ) Z jauh dari x sumbu.

h=P.y÷3

Kemudian koordinat Eisenstein dari Z adalah

Z.xE=P.x+h,Z.yE=2h

WX¯,XY¯,YZ¯ Pw

w=P.y×3%3

w=0,1,2YZ¯,XY¯,WX¯ respectively. Finally, the nearest Eisenstein point of P (which is one of Z, V, or X) can be calculated as:

PE.xE=P.x+h+w2,PE.yE=2h+w

Using the identities for h and w, we can further simplify to:

y=P.y×3,PE.xE=P.x+y÷3,PE.yE=2y÷3

How it works: the code

0+⌈3÷⍨1 2×⌊⎕×√3
           ⌊⎕×√3   Take the first input (P.y) and calculate y'
   ⌈3÷⍨1 2×       ⍝ Calculate [ceil(y'/3), ceil(2y'/3)]
⎕0+  ⍝ Take the second input(P.x) and calculate [P.x+ceil(y'/3), ceil(2y'/3)]
Bubbler
sumber
2

JavaScript (ES6), 112 bytes

(a,b,l=b/Math.pow(.75,.5),k=a+l/2,f=Math.floor,x=k-(k=f(k)),y=l-(l=f(l)),z=x+y>1)=>[k+(y+y+z>x+1),l+(x+x+z>y+1)]

ES7 can obviously trim 9 bytes. Explanation: k and l initially represent the floating-point solution to k+ωl=a+ib. However, the coordinates needed to be rounded to the nearest integer by Euclidean distance. I therefore take the floor of k and l, then perform some tests on the fractional parts to determine whether incrementing them would result in a nearer point to a+ib.

Neil
sumber
I guess your tests on the fractional parts are taking advantage of the facts that x is always .2887 or 0.577and y is always either .1547 or .577
SmileAndNod
@SmileAndNod 3 years ago? I really can't remember, but I don't think it's that complicated, I'm just working out which is the nearest corner of the diamond.
Neil
2

MATL, 39 38 35 bytes

t|Ekt_w&:2Z^tl2jYP3/*Zeh*!sbw6#YkY)

Input format is 6 + 14*1j (space is optional). Output format is 14 16.

Try it online!

Explanation

The code first takes the input as a complex number. It then generates a big enough hexagonal grid in the complex plane, finds the point that is closest to the input, and returns its Eisenstein "coordinates".

t         % Take input implicitly. This is the Gauss number, say A. Duplicate
|Ek       % Absolute value times two, rounded down
t_        % Duplicate and negate
w&:       % Range. This is one axis of Eisenstein coordinates. This will generate
          % the hexagonal grid big enough
2Z^       % Cartesian power with exponent 2. This gives 2-col 2D array, say B
t         % Duplicate
l         % Push 1
2jYP3/*   % Push 2*j*pi/3
Ze        % Exponential
h         % Concatenate. Gives [1, exp(2*j*pi/3)]
*         % Multiply by B, with broadcast.
!s        % Sum of each row. This is the hexagonal grid as a flattened array, say C
bw        % Bubble up, swap. Stack contains now, bottom to top: B, A, C
6#Yk      % Index of number in C that is closest to A
Y)        % Use as row index into B. Implicitly display
Luis Mendo
sumber
2

Haskell, 128 bytes

i=fromIntegral;r=[floor,ceiling];a!k=(i a-k)**2;c(a,b)|l<-2*i b/sqrt 3,k<-i a+l/2=snd$minimum[(x k!k+y l!l,(x k,y l))|x<-r,y<-r]

Try it online!

For input Gaussian integer (a,b), convert it into Eisenstein coordinates, floor and ceil both components to get four candidates for closest Eisenstein integer, find the one with minimal distance and return it.

Sacchan
sumber
1

Tcl, 124 116 106 bytes

{{a b f\ int(floor(2*$b/3**.5)) {l "[expr $f+(1-$f%2<($b-$f)*3**.5)]"}} {subst [expr $l+$a-($f+1)/2]\ $l}}

Try it online!

This is somewhat inspired by the three-year old post from @Neil

The floor function returns the corner of the rhombus whose edges are the vectors 1 and ω. With respect to this rhombus, the Gaussian integer lies on the perpendicular bi-sector of either the top (if l is even) or bottom (if l is odd). This is important because it means that either the lower left corner or the upper right corner will be an acceptable solution. I compute k for the lower left corner, and do one test to see if the Gaussian integer lies above or below the diagonal separating the two corners; I add 1 to k when above the diagonal, and I do likewise for l.

Saved 10 bytes by using the "sign of the cross-product v x d of the diagonal d with the vector v joining the lower right corner and (a,b)" as the test for which side of the diagonal the point lies.

SmileAndNod
sumber
1

Burlesque, 24 bytes

pe@3r@2././J2./x/.+CL)R_

Try it online!

Pretty sure this can be shorter. Input read as a b

pe      # Parse input to two ints
@3r@2./ # sqrt(3)/2
./      # Divide b by sqrt(3)/2
J2./    # Duplicate and divide by 2
x/.+    # swap stack around and add to a
CL      # Collect the stack to a list
)R_     # Round to ints
DeathIncarnate
sumber