Das Zeichnen des Sierpinski-Dreiecks wurde zu Tode gebracht . Es gibt aber noch andere interessante Dinge, die wir damit machen können. Wenn wir stark genug auf das Dreieck blinzeln, können wir umgedrehte Dreiecke als Knoten eines fraktalen Graphen anzeigen. Lassen Sie uns unseren Weg durch diese Grafik finden!
Weisen wir zunächst jedem Knoten eine Nummer zu. Das größte umgedrehte Dreieck ist der Knoten Null, und dann gehen wir Schicht für Schicht (Breite zuerst) nach unten und weisen fortlaufende Nummern in der Reihenfolge oben links rechts zu:
Klicken Sie für eine größere Version, bei der die kleinen Zahlen etwas weniger verschwommen sind.
(Natürlich wird dieses Muster fortgesetzt ad infinitum im blauen Dreiecke.) Eine weitere Möglichkeit , die Nummerierung zu definieren , ist , dass der Mittelpunkt Knotenindex hat 0
, und die Kinder des Knotens i
(benachbarte Dreiecken des nächsten kleineren Maßstabs) haben Indizes 3i+1
, 3i+2
und 3i+3
.
Wie bewegen wir uns in dieser Grafik? Es gibt bis zu sechs natürliche Schritte, die von einem bestimmten Dreieck ausgeführt werden können:
- Man kann sich immer durch den Mittelpunkt einer der Kanten zu einem der drei untergeordneten Knoten des aktuellen Knotens bewegen. Wir werden diese Bewegungen als bezeichnen
N
,SW
undSE
. Zum Beispiel , wenn wir zur Zeit auf dem Knoten sind2
, würden diese zu Knoten führen7
,8
,9
, respectively. Andere Bewegungen durch die Kanten (zu indirekten Nachkommen) sind nicht zulässig. - Man kann sich auch durch eine der drei Ecken bewegen, vorausgesetzt, sie berührt nicht den Rand des Dreiecks, entweder zu dem direkten Elternteil oder zu einem von zwei indirekten Vorfahren. Wir werden diese Bewegungen als bezeichnen
S
,NE
undNW
. Wenn wir uns gerade auf dem Knoten befinden31
,S
würde dies zu10
,NE
wäre ungültig undNW
würde zu führen0
.
Die Herausforderung
Geben Sie zwei nicht negative ganze Zahlen ein x
und y
finden Sie den kürzesten Weg von x
nach y
, indem Sie nur die oben beschriebenen sechs Züge verwenden. Wenn es mehrere kürzeste Pfade gibt, geben Sie einen davon aus.
Beachten Sie, dass Ihr Code für mehr als nur die in der obigen Abbildung gezeigten 5 Ebenen funktionieren sollte. Sie können das annehmen x, y < 1743392200
. Dadurch wird sichergestellt, dass sie in eine 32-Bit-Ganzzahl mit Vorzeichen passen. Beachten Sie, dass dies 20 Ebenen des Baums entspricht.
Ihr Code muss alle gültigen Eingaben in weniger als 5 Sekunden verarbeiten . Während dies eine Brute-Force-Breitensuche ausschließt, sollte es eine ziemlich lockere Einschränkung sein - meine Referenzimplementierung verarbeitet willkürliche Eingaben für die Tiefe 1000 in einer halben Sekunde (das sind ~ 480-stellige Zahlen für die Knoten).
Sie können ein Programm oder eine Funktion schreiben, indem Sie eine Eingabe über STDIN (oder die nächstgelegene Alternative), ein Befehlszeilenargument oder ein Funktionsargument vornehmen und das Ergebnis über STDOUT (oder die nächstgelegene Alternative), einen Funktionsrückgabewert oder einen Funktionsparameter (out) ausgeben.
Die Ausgabe sollte eine flache, eindeutige Liste der Saiten sein N
, S
, NE
, NW
, SE
, SW
, unter Verwendung eines beliebigen angemessenen Separators (Leerzeichen, Zeilenumbrüche, Kommas, ","
...).
Es gelten die Standardregeln für Code-Golf .
Testfälle
Die ersten Testfälle können anhand des obigen Diagramms von Hand herausgearbeitet werden. Die anderen sorgen dafür, dass die Antworten ausreichend effizient sind. Für diese gibt es möglicherweise andere Lösungen mit der gleichen Länge, die nicht aufgeführt sind.
0 40 => N N N N
66 67 => S SW N N N
30 2 => NW NW -or- NE SW
93 2 => NE SW
120 61 => NW NW NW NW N SE SW N
1493682877 0 => S S NW NW
0 368460408 => SW SW N N SW SW SE SW SW N SE N N SW SW N SE SE
1371432130 1242824 => NW NW NE NW N SE SW SW SW SE SE SW N N N N SW
520174 1675046339 => NE NW NE NE SE SE SW SW N SE N SW N SW SE N N N N SE SE SW SW
312602548 940907702 => NE NW S SW N N SW SE SE SE SW SE N N SW SE SE SE SW
1238153746 1371016873 => NE NE NE SE N N SW N N SW N SE SE SW N SW N N SE N SE N
547211529 1386725128 => S S S NE NW N N SE N SW N SE SW SE SW N SE SE N SE SW SW N
1162261466 1743392199 => NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE
quelle
APL (Dyalog Unicode) ,
144132129118133132130124117 Byte SBCSVielen Dank an Ven und ngn für ihre Hilfe beim Golfspielen in The APL Orchard , einem großartigen Ort, um die APL-Sprache zu lernen.
⎕IO←0
. Golfvorschläge sind willkommen.Edit: -12 Bytes dank Ven und ngn durch Änderung der
n
Definition und Umstellung von 1-Indizierung auf 0-Indizierung. -3 aufgrund der Behebung eines Fehlers, bei dem nicht alles auf 0-Indizierung umgestellt wurde. -11 Bytes aufgrund von Änderungen in der ArtP
und Weise derQ
Definition. +15 Bytes, da ein Problem behoben wurde, bei dem mein Algorithmus nicht korrekt war. Vielen Dank an ngn für die Hilfe beim Ermitteln dess[⊃⍋|M-s]
Abschnitts. -2 Bytes von der Neuordnung der Methode zum Auffinden des Backtracking-Pfades und +1 Byte bis zur Fehlerbehebung. -2 Bytes dank Adám von der Neuordnung der Definition vonI
. -6 Byte dank ngn aus der Neuordnung der Definition'S' 'NE' 'NW' 'N' 'SW' 'SE'
und aus der Neuordnung dert
Definition (es ist keine separate Variable mehr). -7 bytes dank ngn vom golf wies
definiert.Probieren Sie es online!
Eine Erklärung des Fehlers im Algorithmus
Das Grundproblem ist, dass ich dachte, der kürzeste Weg würde direkt durch den gemeinsamen Vorfahren verlaufen und könnte tatsächlich nicht durch einen Vorfahren des gemeinsamen Vorfahren verlaufen. Dies ist nicht korrekt, wie die folgenden Beispiele zeigen.
Von 66 bis 5
Von 299792458 bis 45687
Erklärung des Codes
Alternative Lösung mit Dyalog Extended und dfns
Wenn wir verwenden
⎕CY 'dfns'
‚s -adic
Funktion implementiert er unsere bijective Basis-n numeration (die die Inspiration für die Version , die ich benutzt wurde) für weit weniger Bytes. Der Wechsel zu Dyalog Extended spart auch eine ganze Reihe von Bytes und so sind wir hier. Vielen Dank an Adám für seine Hilfe beim Golfspielen. Golfvorschläge willkommen!Bearbeiten: -8 Bytes aufgrund einer Änderung, wie
P
undQ
definiert sind. -14 Bytes aufgrund der Umstellung auf Dyalog Extended. -2 aufgrund der Verwendung eines vollständigen Programms zum Entfernen der dfn-Klammern{}
. +17 Bytes, da ein Problem behoben wurde, bei dem mein Algorithmus nicht korrekt war. Vielen Dank an ngn für die Hilfe beim Ermitteln dess[⊃⍋|M-s]
Abschnitts. +1 Byte zur Fehlerbehebung. -2 Bytes dank Adám von der Neuordnung der Definition vonI
und -1 Bytes von der Erinnerung daran, meine Golfs in beide Lösungen zu stecken. -3 Bytes dank ngn durch Neuordnung der Generierung der Hauptrichtungen, +1 Byte durch Korrektur eines fehlerhaften Golfs und -3 Bytes dank ngn durch Neuordnung dert
Definition (es ist keine separate Variable mehr). -7 Bytes dank ngn durch Neuordnung wies
definiert.APL (Dyalog Extended) ,
12311510199116117114109102 ByteProbieren Sie es online!
quelle