Гаусса Эйзенштейну

18

Если дано гауссово целое число a+bi где a , b - целые числа, а i=exp(πi/2) - мнимая единица, вернуть самое близкое (относительно евклидова расстояния) целое Эйзенштейна k+lω где k , l - целые числа и ω=exp(2πi/3)=(1+i3)/2.

Фон

Вероятно, совершенно очевидно, что каждое гауссово целое число может быть однозначно записано как a+bi с целыми числами a , b . Это не так очевидно , но тем не менее верно: любое целое Эйзенштейна можно однозначно записать в виде k+lω с К , l целых чисел. Оба они образуют Z модуль внутри комплексных чисел и оба являются p-тыми циклотомическими целыми числами для p=2 или 3 соответственно. Обратите внимание, что 3+2i3+2ω

Источник: commons.wikimedia.org

Детали

  • Если у данного комплексного числа есть две или три ближайших точки, любая из них может быть возвращена.

  • Комплексное число дается в прямоугольных координатах (основание (1,i) ), но кроме этого в любом удобном формате, таком как (A,B)или A+Biили A+B*1jи т. Д.

  • Целое число Эйзенштейна должно быть возвращено в качестве координат базиса (1,ω) но в любом удобном формате, например, (K,L)или, K+Lωи K+L*1ωт. Д.

Примеры

Все действительные целые числа, очевидно, должны быть снова сопоставлены с действительными целыми числами.

  6,14 -> 14,16
  7,16 -> 16,18
-18,-2 ->-19,-2
 -2, 2 -> -1, 2
 -1, 3 -> 1, 4
flawr
источник
Хорошо, я не помню, чтобы видел гексагональную сетку, так как codegolf.stackexchange.com/q/70017/17602
Нил
@Neil С тех пор было три других. ;)
Мартин Эндер
Вы должны также включить тестовые случаи, когда a и b имеют противоположные знаки.
SmileAndNod
@SmileAndNod Добавил один. Но можно также использовать симметрию относительно реальной оси и просто заменить (1,w)на (-1,1+w). И я также переименовал этот раздел в Примеры, чтобы прояснить, что недостаточно просто предоставить правильные результаты для этих случаев.
19

Ответы:

7

APL (Dyalog Extended) , 16 байтов SBCS

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

Попробуйте онлайн!

Полная программа , которая принимает yзатем xиз стандартного ввода и выводит 2-элементный вектор целых чисел а.

Как это работает: математика

Прежде всего, обратите внимание, что любое гауссово целое число будет помещено на вертикальную диагональ ромба, а точка Z расположена в (x,3y)для некоторого целого числаx,y.

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

На рисунке, WZ¯=3 иWX¯=XY¯=YZ¯=XV¯=YV¯=13 . Итак, учитывая вертикальное положение точки, мы можем определить ближайшую точку Эйзенштейна следующим образом:

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

Учитывая гауссову точку P , мы сначала определяем, к какому алмазупринадлежитP , и измеряем, сколько алмазов (обозначеноh )Z находится внеосиx .

h=P.y÷3

Тогда координаты Эйзенштейна Z являются

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

Теперь мы определяем из сегментов WX¯,XY¯,YZ¯ Pпринадлежит. Для этого мы можем рассчитать показательwследующим образом:

w=P.y×3%3

w=0,1,2YZ¯,XY¯,WX¯PZVX

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

hw

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
источник
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
источник
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

Сначала код принимает входные данные как комплексное число. Затем он генерирует достаточно большую гексагональную сетку в комплексной плоскости, находит точку, ближайшую к входу, и возвращает его «координаты» Эйзенштейна.

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
Луис Мендо
источник
2

Haskell , 128 байт

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]

Попробуйте онлайн!

Для ввода гауссовского целого числа (a, b), конвертируйте его в координаты Эйзенштейна, задайте для пола и потолка оба компонента, чтобы получить четыре кандидата на ближайшее целое число Эйзенштейна, найдите тот с минимальным расстоянием и верните его.

Sacchan
источник
1

Tcl , 124 116 106 байт

{{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}}

Попробуйте онлайн!

Это несколько вдохновлено трехлетней записью от @Neil

Функция floor возвращает угол ромба, ребрами которого являются векторы 1 и ω, Относительно этого ромба гауссово целое число лежит на перпендикулярном би-секторе либо вершины (если l четное), либо основания (если l нечетное). Это важно, потому что это означает, что либо нижний левый угол, либо верхний правый угол будет приемлемым решением. Я вычисляю k для левого нижнего угла и делаю один тест, чтобы увидеть, находится ли гауссово целое число выше или ниже диагонали, разделяющей два угла; Я добавляю 1 к k, когда выше диагонали, и я делаю то же самое для л.

Сохранение 10 байтов с использованием «знака перекрестного произведения vxd диагонали d с вектором v, соединяющим нижний правый угол и (a, b)», в качестве теста, для которого лежит сторона диагонали.

SmileAndNod
источник
1

Бурлеск , 24 байта

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

Попробуйте онлайн!

Уверен, это может быть короче. Ввод читать как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
источник