18
\$\begingroup\$

Given a Gaussian integer \$a+bi\$ where \$a\$,\$b\$ are integers and \$i = \exp\left(\pi i/2\right)\$ is the imaginary unit, return the closest (w.r.t to the Euclidean distance) Eisenstein integer \$k+l\omega\$ where \$k\$,\$l\$ are integers and \$\omega = \exp(2\pi i/3) = (-1+i\sqrt{3})/2\$.

Background

It is probably quite obvious that every Gaussian integer can uniquely be written as \$a+bi\$ with \$a\$,\$b\$ integers. It is not so obvious but nonetheless true: Any Eisenstein integer can uniquely be written as \$k+l\omega\$ with \$k\$,\$l\$ integers. They both form a \$\mathbb{Z}\$-module within the complex numbers, and are both p-th cyclotomic integers for \$p=2\$ or \$3\$ respectively. Note that \$3+2i \neq 3+2\omega\$

Source: commons.wikimedia.org

Details

  • In case the given complex number has two or three closest points, any of those can be returned.

  • The complex number is given in rectangular coordinates (basis \$(1,i)\$), but other than that in any convenient format like (A,B) or A+Bi or A+B*1j etc.

  • The Eisenstein integer has to be returned as coordinates of the basis \$(1,\omega)\$ but other than that in any convenient format like (K,L) or K+Lω or K+L*1ω etc.

Examples

All real integers should obviously be mapped to the real integers again.

  6,14 -> 14,16
  7,16 -> 16,18
-18,-2 ->-19,-2
 -2, 2 -> -1, 2
 -1, 3 -> 1, 4
\$\endgroup\$
  • \$\begingroup\$ Nice, I don't remember seeing a hexagonal grid since codegolf.stackexchange.com/q/70017/17602 \$\endgroup\$ – Neil Aug 7 '16 at 20:22
  • \$\begingroup\$ Related \$\endgroup\$ – Lynn Aug 7 '16 at 20:37
  • \$\begingroup\$ @Neil There have been three others since then. ;) \$\endgroup\$ – Martin Ender Aug 7 '16 at 20:48
  • \$\begingroup\$ You should also include test cases when a and b have opposite signs. \$\endgroup\$ – vo1stv Aug 5 '19 at 10:10
  • \$\begingroup\$ @SmileAndNod Added one. But one could also just use the symmetry with respect to the real axis and just replace (1,w) with (-1,1+w). And I also renamed this section to Examples to make it clear that it is not sufficient to just provide the right results for these cases. \$\endgroup\$ – flawr Aug 5 '19 at 12:13
7
+200
\$\begingroup\$

APL (Dyalog Extended), 16 bytesSBCS

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

Try it online!

A full program that takes y then x from standard input and prints a 2-element vector of integers.

How it works: the math

First of all, note that any Gaussian integer will be placed on the vertical diagonal of a diamond, with the point \$Z\$ placed at \$(x,\sqrt3y)\$ for some integer \$x,y\$.

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

In the figure, \$\overline{WZ}=\sqrt3\$ and \$\overline{WX}=\overline{XY}=\overline{YZ}=\overline{XV}=\overline{YV}=\frac{1}{\sqrt3}\$. So, given the vertical position of a point, we can identify the nearest Eisenstein point as follows:

$$ \text{Given a point }P \in \overline{WZ}, \\ \left\{ \begin{array}{c} P \in \overline{WX} \implies \text{the nearest point is } W \\ P \in \overline{XY} \implies \text{the nearest point is } V \\ P \in \overline{YZ} \implies \text{the nearest point is } Z \end{array} \right. $$

Given a Gaussian point \$P\$, we first determine which diamond \$P\$ belongs to, measured by how many diamonds (denoted \$h\$) \$Z\$ is away from the \$x\$-axis.

$$ h = \lfloor P.y \div \sqrt3 \rfloor $$

Then the Eisenstein coordinates of \$Z\$ are

$$ Z.x_E = P.x+h, \quad Z.y_E = 2h $$

Now, we determine which of the segments \$\overline{WX},\overline{XY},\overline{YZ}\$ \$P\$ belongs to. For this, we can calculate the indicator \$w\$ as follows:

$$ w = \lfloor P.y \times \sqrt3 \rfloor \% 3 $$

Then the cases \$ w = 0, 1, 2 \$ correspond to \$\overline{YZ},\overline{XY},\overline{WX}\$ respectively. Finally, the nearest Eisenstein point of \$P\$ (which is one of \$Z\$, \$V\$, or \$X\$) can be calculated as:

$$ P_E.x_E = P.x+h+\lceil \frac{w}2 \rceil, \quad P_E.y_E = 2h+w $$

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

$$ y' = \lfloor P.y \times \sqrt3 \rfloor, \quad P_E.x_E = P.x+\lceil y' \div 3 \rceil, \quad P_E.y_E = \lceil 2y' \div 3 \rceil $$

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)]
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – vo1stv Aug 9 '19 at 0:08
  • \$\begingroup\$ @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. \$\endgroup\$ – Neil Aug 9 '19 at 9:05
2
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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 \$\omega\$. 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.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 13 bytes

Port of Bubbler's APL answer

3t*ïx‚3/îR΂+

Try it online!

Input and output are both y first, x second.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.