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 Code-Golf, also gewinnt die kürzeste Antwort in Bytes. Erklärungen, auch für nicht esoterische Sprachen, sind erwünscht.
quelle
MATL ,
4745444341 BytesProbieren 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
quelle
05AB1E (Legacy) ,
302927 ByteProbieren Sie es online!
Erklärung des Codes:
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,
X
wo 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.quelle
C (GCC) ,
175173 BytesVielen Dank an Peter Taylor für den Fehler.
Danke an ceilingcat für -2 Bytes. Dieser Operator ist weiterhin mein Hauptblindpunkt.
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.
quelle
Python 3, 150 Bytes
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:
h
führt Folgendes aus:i
ist die Ringnummer.l
ist 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:l[0]+=1
in Zeile 6, die der Schritt von einem Ring zum nächsten ist.L+=l
verkettet die komplette Liste und die Ringliste.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 , dassa<b
, dh die Argumente in ansteigender Reihenfolge kommen würden, konnte ich weitere 14 Bytes durch den Ersatz abrasierenL[min(a,b):max(a,b)]
mitL[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 :)
quelle
Mathematica,
111105104 BytesErläuterung:
r=Floor[(1+Sqrt[(4#-1)/3])/2]&
definiert eine Funktion,r
die 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
r
definedr@#
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 wir
Pi(#/(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 err@#
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:
Oder für alle Testfälle:
quelle