Gauß nach Eisenstein

17

Bei einer Gaußschen Ganzzahl ein+bich wobei ein , b ganze Zahlen sind und i=exp(πi/2) die imaginäre Einheit ist, kehre die Eisenstein-Ganzzahl k+lω wobei k , l sind ganze Zahlen und ω=exp(2πi/3)=(1+i3)/2 .

Hintergrund

Es ist wahrscheinlich ziemlich offensichtlich, dass jede Gaußsche Ganzzahl eindeutig als a+bi mit a , b Ganzzahlen geschrieben werden kann. Es ist nicht so offensichtlich, aber dennoch wahr: Jede Eisenstein-Ganzzahl kann eindeutig als k+lω mit k , l ganzen Zahlen geschrieben werden. Sie bilden beide ein Z Modul innerhalb der komplexen Zahlen und sind beide p-te cyclotomische ganze Zahlen für p=2 bzw. 3 . Man beachte, dass 3+2i3+2ω

Quelle: commons.wikimedia.org

Einzelheiten

  • Falls die gegebene komplexe Zahl zwei oder drei nächstliegende Punkte hat, kann jeder von diesen zurückgegeben werden.

  • Die komplexe Zahl wird in Rechteckkoordinaten (Basis) angegeben (1,i) ) angegeben, jedoch nicht in einem geeigneten Format wie(A,B)oderA+BioderA+B*1jusw.

  • Die Eisenstein-Ganzzahl muss als Koordinaten der Basis zurückgegeben werden (1,ω) jedoch nicht in einem geeigneten Format wie(K,L)oderK+LωoderK+L*1ωusw.

Beispiele

Alle reellen Ganzzahlen sollten natürlich wieder auf die reellen Ganzzahlen abgebildet werden.

  6,14 -> 14,16
  7,16 -> 16,18
-18,-2 ->-19,-2
 -2, 2 -> -1, 2
 -1, 3 -> 1, 4
Fehler
quelle
Schön, ich kann mich nicht erinnern, seit codegolf.stackexchange.com/q/70017/17602
Neil
Related
Lynn
@Neil Seitdem gab es drei andere. ;)
Martin Ender
Sie sollten auch Testfälle einbeziehen, wenn a und b entgegengesetzte Vorzeichen haben.
SmileAndNod
@SmileAndNod hat einen hinzugefügt. Man könnte aber auch einfach die Symmetrie in Bezug auf die reale Achse und ersetzen Sie einfach (1,w)mit (-1,1+w). Außerdem habe ich diesen Abschnitt in " Beispiele" umbenannt , um zu verdeutlichen, dass es nicht ausreicht, nur die richtigen Ergebnisse für diese Fälle bereitzustellen.
Fehler

Antworten:

7

APL (Dyalog Extended) , 16 Byte SBCS

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

Probieren Sie es online!

Ein volles Programm, das dauert y dann xaus der Standardeingabe einen 2-Element-Vektor von ganzen Zahlen ausgibt.

Wie es funktioniert: die Mathematik

Zuallererst ist zu beachten, dass jede Gaußsche Ganzzahl auf der vertikalen Diagonale eines Diamanten platziert wird, wobei der Punkt Z bei (x,3y)für eine ganze Zahlx,y.

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

In der Figur ist WZ¯=3 undWX¯=XY.¯=Y.Z¯=XV¯=Y.V¯=13

Einen Punkt gegeben PWZ¯,{PWX¯der nächste Punkt ist WPXY.¯der nächste Punkt ist VPY.Z¯der nächste Punkt ist Z

PPhZx

h=P.y÷3

Z

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

Nun bestimmen wir, welches der Segmente WX¯,XY.¯,Y.Z¯ Pgehört. Dafür können wir den Indikator berechnenw wie folgt:

w=P.y×3%3

Dann die Fälle w=0,1,2 entsprechen Y.Z¯,XY.¯,WX¯beziehungsweise. Schließlich der nächste Eisensteiner Punkt vonP (das ist einer von Z, V, oder X) kann berechnet werden als:

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

Verwendung der Identitäten für h und wkönnen wir weiter vereinfachen:

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

Wie es funktioniert: der 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
quelle
2

JavaScript (ES6), 112 Byte

(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 kann offensichtlich 9 Bytes trimmen. Erklärung: kund stellen lzunächst die Gleitkomma-Lösung dar k+ωl=a+ib. Die Koordinaten mussten jedoch durch euklidischen Abstand auf die nächste ganze Zahl gerundet werden. Ich nehme daher das Wort kund lführe dann einige Tests an den Bruchteilen durch, um festzustellen, ob deren Inkrementierung zu einem näheren Punkt führen würde a+ib.

Neil
quelle
Ich nehme an, Ihre Tests an den Bruchteilen machen sich die Fakten zunutze, dass x immer .2887 oder 0.577 ist und y immer .1547 oder .577 ist
SmileAndNod
@SmileAndNod vor 3 Jahren? Ich kann mich wirklich nicht erinnern, aber ich denke nicht, dass es so kompliziert ist. Ich arbeite gerade daran, welche Ecke des Diamanten am nächsten ist.
Neil
2

MATL , 39 38 35 Bytes

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

Das Eingabeformat ist 6 + 14*1j(Leerzeichen ist optional). Ausgabeformat ist 14 16.

Probieren Sie es online!

Erläuterung

Der Code nimmt die Eingabe zunächst als komplexe Zahl entgegen. Dann erzeugt es ein ausreichend großes hexagonales Gitter in der komplexen Ebene, findet den Punkt, der der Eingabe am nächsten liegt, und gibt seine Eisenstein- "Koordinaten" zurück.

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
quelle
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]

Probieren Sie es online!

Für die Eingabe der Gaußschen Ganzzahl (a, b) konvertieren Sie diese in Eisenstein-Koordinaten, Floor und Ceil, um vier Kandidaten für die nächstgelegene Eisenstein-Ganzzahl zu erhalten. Suchen Sie diejenige mit minimalem Abstand und geben Sie sie zurück.

Sacchan
quelle
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}}

Probieren Sie es online!

Dies ist ein wenig inspiriert von dem dreijährigen Beitrag von @Neil

Die Floor-Funktion gibt die Ecke der Raute zurück, deren Kanten die Vektoren 1 und sind ω. In Bezug auf diese Raute liegt die Gaußsche Ganzzahl auf dem senkrechten Bissektor von oben (wenn l gerade ist) oder unten (wenn l ungerade ist). Dies ist wichtig, da dies bedeutet, dass entweder die untere linke Ecke oder die obere rechte Ecke eine akzeptable Lösung darstellt. Ich berechne k für die untere linke Ecke und mache einen Test, um festzustellen, ob die Gaußsche Ganzzahl über oder unter der Diagonale liegt, die die beiden Ecken trennt. Ich addiere 1 zu k, wenn über der Diagonale, und ich tue ebenso für l.

Es wurden 10 Bytes gespeichert, indem das "Vorzeichen des Kreuzprodukts vxd der Diagonale d mit dem Vektor v, der die untere rechte Ecke und (a, b) verbindet" als Test verwendet wurde, für welche Seite der Diagonale der Punkt liegt.

SmileAndNod
quelle
1

Burlesque , 24 Bytes

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

Probieren Sie es online!

Ziemlich sicher, dass dies kürzer sein kann. Eingabe gelesen alsa 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
Tod inkarnieren
quelle