Ich stehe an einem Punkt (0,0)
in einem H
xW
Karte dem die Höhe durch Ziffern dargestellt wird. Beispiel:
1132
2221
1230 # H = 3, W = 4
Ich möchte die Aussicht von jedem Gipfel aus erleben, in diesem Fall von den Gebieten mit Höhenunterschieden 3
. Das Klettern auf Hügeln ist jedoch keine leichte Aufgabe, und mir geht auch die Zeit aus.
Herausforderung
Die Herausforderung besteht darin, den schnellsten Weg zu finden, um alle Gipfel zu besuchen und zurückzukehren.
Kürzeste Sendung gewinnt.
Eingang
- H, W - Höhe und Breite der Karte (Ganzzahlen) (optional, kann eine Liste / ein Tupel oder zwei separate Ganzzahleingaben sein)
- Die Karte wird in Form
H
vonW
Ziffern (0
-9
) in einem beliebigen Format (2D-Liste, durch Zeilenumbrüche getrennte Zeichenfolge usw.) angegeben.
Ausgabe
- Kürzeste Zeit, die benötigt wird, um jeden Gipfel zu besuchen und zu Ihrem Ausgangspunkt zurückzukehren (Integer)
Bedingungen
- Die Höhe eines bestimmten Gebiets wird durch eine Ziffer von
0
bis dargestellt9
. - Der "Gipfel" wird durch das Gebiet mit der höchsten Höhe definiert.
- Der Pfad muss oben links (0,0) beginnen und enden .
- Sie können sich nur in Bereiche bewegen, die an Ihren aktuellen Bereich angrenzen, und Sie können sich möglicherweise nicht diagonal bewegen.
- Es dauert 3 Minuten , um von einem Gebiet in ein anderes zu gelangen, wenn sich die Höhe nicht ändert.
- Der Aufstieg dauert 11 Minuten . Das heißt, Sie wechseln von einem Bereich zu einem anderen, der genau eine
1
Einheit höher liegt. - Der Abstieg dauert 2 Minuten . Das heißt, Sie wechseln von einem Bereich in einen anderen, der genau eine
1
Einheit tiefer liegt. - Sie können nicht zu Bereichen wechseln , die
1
höher oder niedriger als Ihre Position sind. (Sie können nicht von einem Gebiet mit Höhe1
zu einem angrenzenden Gebiet mit Höhe gehen, sagen wir,3
)
- Ein Weg zu allen Gipfeln ist garantiert
- Die maximale Anzahl von Peaks beträgt
15
.
Proben
Eingang
4 5
32445
33434
21153
12343
Ausgabe
96
Erläuterung
Sie beginnen oben links 3
. Sie müssen die beiden 5
s besuchen , die sich in (0,4)
und befinden, (3,3)
und in kürzester Zeit zum 3
at (0,0)
zurückkehren.
3 2 4->4->5
V ^
3->3->4 3 4
2 1 1 5 3
1 2 3 4 3 # 3 + 3 + 11 + 3 + 3 + 11 = 34 minutes to visit 1st peak
3 2 4 4 5
V
3 3 4 3 4
V
2 1 1 5 3
^ V
1 2 3 4<-3 # 2 + 2 + 3 + 11 + 11 = 29 minutes to visit 2nd
3 2 4 4 5
^
3 3 4 3 4
^
2 1 1 5 3
^ V
1<-2<-3<-4 3 # 2 + 2 + 2 + 2 + 11 + 11 + 3 = 33 minutes to come back
# 34 + 29 + 33 = 96 minutes total is the answer
Eingang
2 7
6787778
5777679
Ausgabe
75
code-golf
path-finding
puzzle-solver
graph-theory
gemütliches Conemotel
quelle
quelle
Antworten:
Mathematica
745681 BytesDie Grundidee ist, ein gewichtetes Diagramm der möglichen Bewegungen zu erstellen. Gewichte sind die Zeit, die benötigt wird, um von einem Ort zum nächsten zu gelangen. Der Weg mit dem geringsten Gewicht ist der schnellste.
Die Eingabestellen werden in ein Rechteckarray von r x c (Zeilen x Spalten) eingefügt, und dann kommen drei verschiedene Darstellungen ins Spiel: (1) ein Gittergraph von r x c, wobei jeder Scheitelpunkt einer Zelle im Array entspricht. (2) (r c) durch (r c) eine gewichtete Adjazenzmatrix, die Gewichte enthält, die der Zeit entsprechen, die (2, 3 oder 11 Minuten) benötigt, um sich von einer Stelle (im Gitterdiagramm) zu einer anderen zu bewegen, und (3) eine gerichtete gewichteter Adjazenzgraph aus der Matrix.
Das Gitterdiagramm hilft zu bestimmen, welche Zellen (dh welche Eckpunkte) möglicherweise von jedem Eckpunkt aus erreichbar sind - "möglicherweise erreichbar", da eine benachbarte Zelle nicht nur rechts, links, über oder unter einer bestimmten Zelle sein darf. Der Wert muss sich auch innerhalb einer Entfernungseinheit zum Nachbarn befinden (z. B. eine 3 verbindet sich nicht mit einer benachbarten 5 oder einer 1). Wenn Eckpunkt
a
nicht mit dem Scheitelpunkt verbunden ist, habenb
die Adjazenzmatrixzellen {a, b} und {b, a} den Wert ∞. Dementsprechend weist der gewichtete Nachbarschaftsgraph weder eine Kante von a nach b noch von b nach a auf.Der gewichtete Adjazenzgraph dient dazu, den Mindestabstand (
GraphDistance
) und den kürzesten Weg zwischen den Eckpunkten zu bestimmen . Der optimale Pfad muss mit 1 beginnen, jeden der Gipfel berühren und zu 1 zurückkehren. In diesem Fall ist "kürzeste Route" nicht unbedingt diejenige mit den wenigsten Zügen. Es ist das mit der kürzesten Gesamtzeit, gemessen in Kantengewichten.Golf gespielt
Längere, besser lesbare Form
Tests
96.
75.
51.
Erläuterung
Denken Sie an die Zeilen 2-5 der folgenden Eingabe
als Darstellung eines Arrays mit 4 Zeilen und 5 Spalten:
Dabei entspricht jeder Scheitelpunkt einer Ziffer aus dem Eingabearray: 3 befindet sich bei Scheitelpunkt 1, 2 befindet sich bei Scheitelpunkt 2, 4 befindet sich bei Scheitelpunkt 3, weitere 4 bei Scheitelpunkt 4, 5 bei Scheitelpunkt 5 usw. Der Gittergraph ist nur eine grobe Darstellung Annäherung des Diagramms, das wir anstreben. Es ist ungerichtet. Darüber hinaus sind einige der Kanten nicht verfügbar. (Denken Sie daran: Wir können nicht von einer Position zu einer anderen wechseln, die mehr als 1 Höheneinheit über oder unter der aktuellen liegt.) Mit dem Gitterdiagramm können wir jedoch die Eckpunkte finden, die sich neben einem ausgewählten Eckpunkt befinden. Dies reduziert die Anzahl der Kanten, die wir im ersten Beispiel (ein 4 × 5-Raster) berücksichtigen müssen, von 400 (20 × 20) auf 62 (31 × 2 ist die Anzahl der Kanten im Gitterdiagramm). Im selben Beispiel sind nur 48 der Kanten wirksam. 14 sind nicht.
Die folgende 20 x 20 gewichtete Adjazenzmatrix repräsentiert den Abstand zwischen allen Knotenpaaren aus dem Gitterdiagramm.
Der Schlüsselcode, der über die zuzuweisende Nummer entscheidet, ist unten angegeben.
Die Zelle {1,2} enthält - bei einer Indizierung - den Wert 2, da die Verschiebung von Scheitelpunkt 1 zu Scheitelpunkt 2 bergab verläuft. Zelle {2,1} enthält 11, da der Übergang von Scheitelpunkt 2 zu Scheitelpunkt 1 bergauf verläuft. Die 3en in den Zellen {1,6} und {6,1} bedeuten, dass die Bewegung weder nach oben noch nach unten gerichtet ist. Zelle {1,1} enthält ∞, weil sie nicht mit sich selbst verbunden ist.
Das folgende Diagramm zeigt die Struktur, die der obigen Eingabe zugrunde liegt. Die farbigen Pfeile zeigen den optimalen Pfad von Scheitelpunkt 1 zu den Gipfeln (bei 5 und 14) und zurück zu 1. Blaue Pfeile entsprechen Bewegungen auf derselben Ebene (3 Minuten); rote Pfeile bedeuten Aufstieg (11 min) und grüne Pfeile Abstieg (2 min).
Der Pfad von Scheitelpunkt 1 (Zelle {1,1} zu den beiden Gipfeln und zurück zu Scheitelpunkt 1:
96
quelle
Pyth, 92 Bytes
Das Eingabeformat ist ein dict Koordinaten Höhen Mapping:
{(0, 0): 3, (0, 1): 2, (0, 2): 4, …}
. Mit dem Floyd-Warshall-Algorithmus werden die schnellsten Pfade zwischen allen Punktpaaren ermittelt und anschließend die Gesamtzeit des gewünschten Zyklus über alle Permutationen von Peaks hinweg minimiert.Probieren Sie es online aus
quelle