Sechseckige Nachbarschaft

28

Beispiel Sechseckspirale

Das obige Bild zeigt ein sechseckiges Gitter von Sechsecken. Jeder Zelle im Raster wird ein Index zugewiesen, der von der Mitte aus beginnt und sich wie gezeigt gegen den Uhrzeigersinn dreht. Beachten Sie, dass das Raster auf unbestimmte Zeit fortgesetzt wird - das obige Bild ist lediglich der erste Abschnitt. Das nächste Sechseck wäre neben 60 und 37.

Ihre Aufgabe ist es festzustellen, ob zwei vorgegebene Zellen in diesem Raster benachbart sind.

Schreiben Sie ein Programm oder eine Funktion, die bei zwei gegebenen Zellenindizes einen Wahrheitswert ausgibt / zurückgibt, wenn die beiden Zellen benachbart sind, und einen Falsey-Wert, wenn nicht.

Sofern dies nicht aus praktischen Gründen möglich ist, sollte Ihr Code theoretisch für Eingaben beliebiger Größe funktionieren.

Wahrheitstestfälle:

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

Falsche Testfälle:

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

Das ist also gewinnt die kürzeste Antwort in Bytes. Erklärungen, auch für nicht esoterische Sprachen, sind erwünscht.

John Michael Law
quelle

Antworten:

7

Elixir , 263 257 264 223 214 218 214 Bytes

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

Probieren Sie es online!

ungolfed version

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) Gibt den ganzzahligen Teil der Zahl zurück
  • rem(a,b) Gibt den Rest von a / b zurück
  • cond do end Dies ist äquivalent zu else if- oder switch-Klauseln in vielen imperativen Sprachen

Erläuterung

get_ring (index)

Berechnet den "Ring" des Index.

Beispiel: 1 für 1-6, 2 für 7-18 usw.

Dies gilt nur, wenn das Ergebnis floorbearbeitet wird. Nachgestellte Ziffern geben an, wie weit sich die Kachel um den Ring befindet.

inv_get_ring (ring)

Berechnet die Inverse von get_ring(index).

ring_base (ring)

Berechnet den Index der ersten Kachel im Ring.

is_corner (index)

Ecken sind Kacheln, die drei benachbarte Kacheln im äußeren Ring haben. Der innerste Ring besteht vollständig aus Ecken.

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

is_last (index)

Ist wahr, wenn dieser Index der höchste in seinem Ring ist.

is_first (index)

Ist wahr, wenn dies das Grundplättchen des Rings ist.

Garuno
quelle
2
Ich habe die Antwort so bearbeitet, dass sie eine Korrektur für den Edge-Case enthält :)
Garuno
Ich habe Ihre Golfversion durch die ersten Iterationen verfolgt, aber dann schien es, als hätten Sie Ihre Herangehensweise geändert. Entspricht Ihre aktuelle Golfversion immer noch der ungolften Version?
John Michael Law
Ja ist es! Ich habe gerade erfahren, dass Sie Variablen in Elixir inline deklarieren können. Dies gab mir die Möglichkeit, die Lambda-Funktionen am Anfang des Codes loszuwerden. Ich habe die Variablen nur ein wenig verschoben, um sie effizienter zu gestalten.
Garuno
5

MATL , 47 45 44 43 41 Bytes

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

Probieren Sie es online! Oder überprüfen Sie alle Testfälle .

Als Bonus generiert der Code eine hexagonale Spirale, die die Positionen der Zellzentren nachzeichnet. Dies kann in MATL Online grafisch dargestellt werden, indem der letzte Teil des Codes geändert wird.

Erläuterung

Allgemeine Idee    Der Code baut zunächst eine ausreichend große hexagonale Spirale mit Einheitsschritt auf. Die Spirale ist als Vektor komplexer Zahlen definiert, die Positionen der Zellzentren darstellen. Indizieren in diesen Vektor mit den eingegebenen Zahlen und Berechnen der absoluten Differenz ergibt den Abstand zwischen den zwei angezeigten Zellen. Zellen grenzen genau dann aneinander, wenn das Ergebnis 1 ist. Aufgrund von Gleitkommaungenauigkeiten ist jedoch vor dem Vergleich mit 1 eine Rundung erforderlich.

Aufbau der Spirale    Die Spirale hat eine Anzahl von "Schichten", die der Summe der beiden Eingaben entspricht. Dies ist (viel) größer als nötig und stellt sicher, dass die Eingabezellen in der Spirale vorhanden sind.

Um die Spirale aufzubauen, wird zuerst die komplexe Zahl j 2/3 (wobei j die imaginäre Einheit ist) berechnet. Wenn Sie dies auf die Exponenten 1 bis 6 erhöhen, erhalten Sie eine Grundmenge von Verschiebungen, so dass das Verfolgen dieser Verschiebungen in der angegebenen Reihenfolge ein Sechseck nachzeichnen würde. Dieses Sechseck würde die innerste Schicht der Spirale bilden, mit der Ausnahme, dass es "geschlossen" wäre. Eigentlich wollen wir, dass dieses Sechseck im letzten Schritt "wächst" und zeichnen dann ein größeres Sechseck mit doppelt so vielen Punkten (in Zweiergruppen ausgerichtet), um die nächste Schicht der Spirale zu bilden. Siehe Abbildung hier . Die nächste Ebene hat dreimal so viele Punkte wie die erste (in Dreiergruppen). siehe hier .

Dazu wird der fünfte Versatz aus der Grundmenge (der in südöstlicher Richtung zeigt) als "Wachstums" -Schritt gewählt. Die Schicht k beginnt mit diesem Schritt, gefolgt von den ersten fünf Grundschritten, die k- mal wiederholt werden , gefolgt von dem sechsten Schritt (Richtung Osten), der k- 1-mal wiederholt wird. Dies wird hoffentlich klarer, wenn man sich die beiden oben verknüpften Zahlen ansieht.

Der resultierende Vektor, einschließlich aller Ebenen, stellt die komplexen Verschiebungen dar, die der Spirale folgen würden. Die kumulative Summe gibt die tatsächlichen Koordinaten der Zellzentren an.

Zuletzt wird die anfängliche Zelle, die sich bei 0 befindet, an das Ende dieses Vektors angehängt . Dies liegt daran, dass MATL eine modulare 1-basierte Indexierung verwendet und Index 0 auf den letzten Eintrag eines Arrays verweist .

Prüfen auf Adjazenz    Die beiden durch die Eingabenummern angegebenen Zellen werden ausgewählt, ihre Koordinaten werden subtrahiert, und der Absolutwert wird gerundet und mit 1 verglichen.

Kommentierter Code

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
quelle
Könnten Sie eine Erklärung hinzufügen?
Shaggy
@ Shaggy Ich habe eine allgemeine Erklärung hinzugefügt. Lassen Sie mich wissen, ob es klar ist (es ist schwer zu erklären). Ich werde den kommentierten Code später hinzufügen
Luis Mendo
2

05AB1E (Legacy) , 30 29 27 Byte

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

Probieren Sie es online!

Erklärung des Codes:

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

Erklärung von Mathe:

Ich habe ungefähr 5 Stunden damit "verschwendet", diesen Golf zu machen. Kurz gesagt, ich begann ein 2D-Diagramm der Eingaben zu erstellen und zu zeichnen, Xwo sie nebeneinander lagen. Dann habe ich ein Muster gefunden. Ich habe auf OEIS und Bingo danach gesucht ! Ich habe diese Sequenz gefunden und die auf der Website angegebene Formel verwendet.

krinistof
quelle
1

C (GCC) , 175 173 Bytes

Vielen Dank an Peter Taylor für den Fehler.

Danke an ceilingcat für -2 Bytes. Dieser Operator ist weiterhin mein Hauptblindpunkt.

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

Probieren Sie es online!

Dieser Ansatz konzentriert sich darauf, die Zeile und die Spalte der beiden Zellen zu finden und sie zu vergleichen. Nachbarn können ihre entsprechenden Koordinaten nicht um mehr als 1 unterscheiden. Wenn wir uns von der Mitte nach außen bewegen, stellen wir fest, dass jede Ebene 6 Zellen mehr enthält als die vorherige. Dies bedeutet, dass der höchste "Index" in jeder Schicht L auf der Form 6 * (L * (L - 1) * (L - 2) ...) oder C = 6 * (L 2 + L) / 2 liegt , wobei C die "globale" Zellennummer ist. Wenn wir die Dinge durcheinander bringen, erhalten wir L 2 + L - C / 3 = 0, was Mathematik-Flashbacks der Highschool ergibt. Daraus erhalten wir die Formel ceil (sqrt (1/4 + C / 3) + 0.5). Wenn Sie einen globalen Zellenindex einfügen, erhalten Sie, in welcher Schicht sich die Zelle befindet.

Da die erste Zelle in jeder Schicht natürlich eine höher ist als die höchste der vorherigen Schicht, ergibt sich L start = (6 * (L - 1) 2 + (L - 1)) / 2, was sich zu 3 * (L vereinfacht 2 - L). Daraus ergibt sich der Layerindex L index = C - L start .

Als nächstes sehen wir, dass jede Schicht aus sechs Abschnitten mit der Länge L besteht. Beginnend im Nordosten und gegen den Uhrzeigersinn sehen wir, dass für die ersten beiden Abschnitte (1 <= L Index <= 2 * L) erhalten wir die Spalte von L - L Index . Im nächsten Abschnitt L * 2 <L Index <= L * 3 teilen sich alle Zellen eine einzelne Spalte -L. Die beiden nächsten Abschnitte sind L * 3 <L Index <= L * 5 mit ihren Spalten gemäß L Index - L * 4. Und schließlich haben alle sechsten Abschnitte ihre Zellen in Spalte L. Wir können die oberen Grenzen einen Schritt weiter verschieben um einige Bytes im Code zu speichern.

Was ist dann mit den Reihen? Um den Code wiederzuverwenden, drehen wir das Gitter so, dass die Zelle 44 gerade steht. Dann führen wir dieselbe Logik wie für Spalten aus, nennen die Ergebnisse diesmal jedoch "Zeilen". Anstatt ein Gitter zu drehen, laufen wir natürlich nur eine Sechstelrunde um das Gitter herum.

Gastropner
quelle
@PeterTaylor Guter Fang, danke!
Gastropner
1

Python 3, 150 Bytes

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

Meine Lösung folgt im Grunde der gleichen Denkrichtung wie Luis Mendos oben. Wenn der Code besser lesbar geschrieben ist, ist er ziemlich selbsterklärend:

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. Funktion hführt Folgendes aus:
  2. Liste L enthält die (komplexen) Positionen jeder Zahl.
  3. i ist die Ringnummer.
  4. In der while-Schleife wird bei jeder Iteration ein neuer Ring hinzugefügt. Anstatt herauszufinden, wie viele Ringe wir benötigen, bauen wir die Liste einfach weiter auf, bis sie lang genug ist, um a + b zu enthalten. Dann ist sie mit Sicherheit lang genug, um einen der beiden zu enthalten.
  5. Die 'Ringliste' list eine Verkettung von 6 Listen von len (i) mal dem Schrittvektor, wobei der Schrittvektor 1j ** (2/3) zu einer gewissen Potenz ist. Der Bereich beginnt nicht bei 0, sondern bei 4, wodurch das gesamte Raster gedreht wird. Dies ermöglicht mir Folgendes:
  6. l[0]+=1 in Zeile 6, die der Schritt von einem Ring zum nächsten ist.
  7. L+=l verkettet die komplette Liste und die Ringliste.
  8. Liste L enthält nur Schrittvektoren, die noch aufsummiert (integriert) werden müssen, um eine Position zu erhalten. Eine nette Eigenschaft hier ist, dass wir einfach die Scheibe von der niedrigsten zur höchsten Zahl addieren können , um ihre Entfernung zu erhalten! Aufgrund von Rundungsfehlern wird das Ergebnis nicht genau 1 sein, daher der Wert 0,9 <... <1,1. Interessanterweise wird h(0,0)implizit der Nullfall oder h (0,1) berücksichtigt, da die Summe einer leeren Liste Null ist. Wenn ich sicher sein kann , dass a<b, dh die Argumente in ansteigender Reihenfolge kommen würden, konnte ich weitere 14 Bytes durch den Ersatz abrasieren L[min(a,b):max(a,b)]mit L[a:b], aber ach!

PS: Ich wusste nicht, dass dies eine so alte Herausforderung ist. Sie ist vor ein paar Tagen ganz oben aufgetaucht und hat mich seitdem immer wieder belästigt :)

Hermen
quelle
Das ist eine großartige Antwort! Mach dir keine Sorgen wegen der späten Antwort, wir haben hier bei PPCG keine wirklichen Probleme damit.
23.
0

Mathematica, 111 105 104 Bytes

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&

Erläuterung:

r=Floor[(1+Sqrt[(4#-1)/3])/2]&definiert eine Funktion, rdie Eingaben entgegennimmt #und die Entfernung (in Anzahl der Zellen) zu Zelle 0 berechnet. Hierzu wird das Muster in den letzten Zellen jeder Entfernung / jedes Rings ausgenutzt: 0 = 3 (0 ^ 2 + 0), 6 = 3 (1 ^ 2 + 1), 18 = 3 (2 ^ 2 + 2), 36 = 3 (3 ^ 2 + 3), ... und Invertieren der Formel für dieses Muster. Beachten Sie, dass für die Zelle 0 tatsächlich das Wort (1/2) + i * (sqrt (3) / 6) verwendet wird, das komponentenweise berechnet wird, um 0 + 0 * i = 0 zu erhalten.

Mit rdefined r@#ist der Ring für cell #(innerhalb der Definition einer anderen Funktion). #+3r@#-3(r@#)^2&erscheint nicht genau im Code, sondern nimmt die Nummer einer Zelle und subtrahiert die höchste Nummer einer Zelle im nächsten inneren Ring, so dass die Antwort auf die Frage "Welche Zelle des aktuellen Rings ist das?" Zum Beispiel ist Zelle 9 die 3. Zelle von Ring 2, r[9]würde also 2 ausgeben und #+3r@#-3(r@#)^2&[9]würde 3 ausgeben.

Mit der obigen Funktion können wir den Polarwinkel und den Winkel gegen den Uhrzeigersinn vom Strahl "Zelle 0, Zelle 17, Zelle 58" zur betreffenden Zelle ermitteln. Die letzte Zelle jedes Rings befindet sich immer in einem Winkel Pi / 6, und wir gehen in Schritten von Pi / (3 * ring_number) um einen Ring herum. Theoretisch müssen wir also etwas wie Pi / 6 + (welche_Zelle_des_Current_Rings) * Pi / (3 * Ring_Nummer) berechnen. Die Drehung des Bildes hat jedoch keinen Einfluss darauf, sodass wir den Pi / 6-Teil verwerfen können (um 6 Bytes zu sparen). Wenn wir dies mit der vorherigen Formel kombinieren und vereinfachen, erhalten wirPi(#/(3r@#)+1-r@#)&

Leider ist dies für Zelle 0 undefiniert, da deren Ringnummer 0 ist. Daher müssen wir dies umgehen. Eine natürliche Lösung wäre so etwas wie t=If[#==0,0,Pi(#/(3r@#)+1-r@#)]&. Da uns aber der Winkel für Zelle 0 egal ist und weil er r@#wiederholt wird, können wir hier mit tatsächlich ein Byte speichernt=Limit[Pi(#/(3x)+1-x),x->r@#]&

Nun, da wir die Ringnummer und den Winkel haben, können wir die Position einer Zelle (Mitte) finden, um auf Nachbarschaft zu testen. Das Auffinden der tatsächlichen Position ist ärgerlich, da die Ringe sechseckig sind, aber wir können einfach so tun, als wären die Ringe perfekte Kreise, sodass wir die Ringnummer als den Abstand zum Zentrum von Zelle 0 behandeln. Dies ist kein Problem, da die Annäherung hübsch ist schließen. Mit der polaren Form einer komplexen Zahl können wir diese ungefähre Position in der komplexen Ebene mit einer einfachen Funktion darstellen:p = r@#*Exp[I*t@#] &;

Der Abstand zwischen zwei komplexen Zahlen auf der komplexen Ebene wird durch den absoluten Wert ihrer Differenz angegeben. Dann können wir das Ergebnis abrunden, um etwaige Fehler aus der Näherung zu beseitigen, und prüfen, ob diese gleich 1 sind. Die Funktion that finally hat diese Arbeit keinen Namen, ist aber Round@Abs[p@#-p@#2]==1&.


Sie können es online in der Wolfram Cloud-Sandbox versuchen, indem Sie den folgenden Code einfügen und auf Zahnrad -> "Zelle auswerten" klicken oder Umschalt + Eingabetaste oder die Zifferntaste drücken:

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]

Oder für alle Testfälle:

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}}]]&
Mark S.
quelle