Herausforderung
Bei gegebener Gittergröße, Hindernisposition, Spielerposition und Zielposition besteht Ihre Aufgabe darin, einen Weg für den Spieler zu finden, um zum Ziel zu gelangen und die Hindernisse gleichzeitig zu umgehen (falls erforderlich).
Eingang
- N : Gittergröße
N x N
- P : Position des Spielers
[playerposx, playerposy]
- T : Zielposition
[targetposx, targetposy]
- O : Positionen der Hindernisse
[[x1, y1], [x2, y2],...,[xn, yn]]
Ausgabe
Pfad : Ein Pfadspieler kann das Ziel erreichen[[x1, y1], [x2, y2],...,[xn, yn]]
Regeln
- Der Punkt
[0,0]
befindet sich in der oberen linken Ecke des Rasters. - Die Position des Spielers befindet sich immer auf der linken Seite des Gitters.
- Die Position des Ziels befindet sich immer auf der rechten Seite des Gitters.
- Das Gitter wird immer mindestens ein Hindernis haben.
- Sie können davon ausgehen, dass kein Hindernis den Spieler oder die Zielposition überlappt.
- Sie müssen nicht unbedingt den minimalen Pfad finden.
- Der Spieler kann sich nur nach links, rechts, oben und unten bewegen, nicht diagonal.
- Sie können die Eingabe auf jede bequeme Weise vornehmen.
- Sie können davon ausgehen, dass es immer einen Weg gibt, über den der Spieler zum Ziel gelangt.
- Offensichtlich gibt es für jede Eingabe mehrere gültige Pfade. Wählen Sie einen aus.
- Angenommen
N > 2
, das Gitter wird mindestens so sein3 x 3
.
Beispiele
Input: 9
, [6, 0]
, [3, 8]
, [[0, 5], [2, 2], [6, 4], [8, 2], [8, 7]]
Mögliche Ausgabe:[[6, 0], [6, 1], [6, 2], [6, 3], [5, 3], [5, 4], [5, 5], [5, 6], [5, 7], [5, 8], [4, 8], [3, 8]]
Input: 6
, [1, 0]
, [3, 5]
, [[1, 2], [2, 5], [5, 1]]
Mögliche Ausgabe:[[1, 0], [1, 1], [2, 1], [2, 2], [2, 3], [2, 4], [3, 4], [3, 5]]
Hinweis
Beachten Sie, dass dies X
für Zeilen und Y
Spalten gilt. Verwechseln Sie sie nicht mit den Koordinaten in einem Bild.
Bearbeiten
Wie @digEmAll wies darauf hin, aufgrund Regeln #2
und #3
, playerY = 0
und targetY = N-1
. Also, wenn Sie möchten, können Sie nur playerX
und und als Eingabe nehmen targetX
(wenn das Ihren Code kürzer macht).
quelle
Antworten:
JavaScript (ES6), 135 Byte
Nimmt Eingaben als an
(width, [target_x, target_y], obstacles)(source_x, source_y)
, wobei Hindernisse eine Reihe von Zeichenfolgen im"X,Y"
Format sind.Gibt ein Array von Zeichenfolgen im
"X,Y"
Format zurück.Probieren Sie es online!
Kommentiert
quelle
R , 227 Bytes
Probieren Sie es online!
Nicht wirklich kurz und definitiv nicht auf dem kürzesten Weg (z. B. das erste Beispiel überprüfen).
Grundsätzlich führt es eine rekursive Tiefensuche durch und stoppt, sobald das Ziel erreicht ist, und druckt den Pfad aus.
Vielen Dank an JayCe für die Verbesserung der Ausgabeformatierung
quelle
x1 y1 x2 y2 ... xn yn
: Dwrite(t(mx),1,N)
stattprint
ing :)Python 2 ,
151149 BytesProbieren Sie es online!
quelle
Haskell ,
133131130 BytesProbieren Sie es online! (mit ein paar Testfällen)
Eine Funktion,
!
die als Eingabe verwendet wirdn :: Int
Größe des Gittersp :: [Int]
Spielerposition als Liste[xp, yp]
o :: [[Int]]
Hindernisse positionieren sich als Liste[[x1, y1], [x2, y2], ...]
t :: [[[Int]]]
(implizite) Position des Ziels als Liste[[[xt, yt]]]
(dreifache Liste nur zur Vereinfachung)und Zurückgeben eines gültigen Pfads als Liste
[[xp, yp], [x1, y1], ..., [xt, yt]]
.Als Bonus findet es einen der kürzesten Pfade und funktioniert für die Position jedes Spielers und Ziels. Auf der anderen Seite ist es sehr ineffizient (aber die bereitgestellten Beispiele laufen in angemessener Zeit ab).
Erläuterung
iterate
[[xt, yt]]
Der scheinbar obskure Ausdruck
[id, map (+ 1)] <*> [[x - 1,y], [x, y - 1]]
ist nur eine "golfige" (-1 Byte) Version von[[x + 1, y], [x, y + 1], [x - 1, y], [x, y - 1]]
.quelle
Retina 0.8.2 , 229 Bytes
Probieren Sie es online! Nicht sicher, ob das E / A-Format geeignet ist. Erläuterung:
Dupliziere jede Zelle. Die linke Kopie wird als temporärer Arbeitsbereich verwendet.
Markiere den Anfang des Labyrinths als besucht.
Markiere das Ende des Labyrinths als leer.
Während verfügbare Arbeitszellen vorhanden sind, zeigen Sie auf benachbarte zuvor besuchte Zellen.
Verfolgen Sie den Pfad vom Ausgang bis zum Start anhand der Arbeitszellen als Leitfaden.
Löschen Sie die Arbeitszellen.
quelle
JavaScript, 450 Byte
Übernimmt die Eingabe als
(n, {playerx, playery}, {targetx, targety}, [{obstaclex, obstacley}])
. Gibt ein Array von zurück{hopx, hopy}
.Hier ist eine ungeteilte Version meines Chaos:
quelle