Ihre Aufgabe ist es, die Länge des längsten Abstiegs auf einem "Berg" zu bestimmen, der als Gitter aus ganzzahligen Höhen dargestellt wird. Ein "Abstieg" ist ein beliebiger Weg von einer Startzelle zu orthogonal benachbarten Zellen mit streng abnehmenden Höhen (dh nicht diagonal und nicht auf dieselbe Höhe). Sie können beispielsweise von 5-4-3-1, aber nicht von 5-5-4-3-3-2-1 wechseln. Die Länge dieses Pfades gibt an, wie viele Zellbewegungen von der Startzelle zur Endzelle vorhanden sind. 5-4-3-1 ist also Länge 3.
Sie erhalten ein rechteckiges Gitter als Eingabe und sollten eine Ganzzahl ausgeben, die den längsten Abstieg angibt.
Beispiele
1 2 3 2 2
3 4 5 5 5
3 4 6 7 4
3 3 5 6 2
1 1 2 3 1
Die Länge des längsten Abstiegs auf diesem Berg beträgt 5. Der längste Weg beginnt bei der 7 und bewegt sich nach links, oben, links, oben und dann nach links (7-6-5-4-2-1). Da dieser Pfad 5 Bewegungen enthält, beträgt die Pfadlänge 5.
Sie könnten alle die gleiche Nummer sein.
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
Da diese Höhenkarte flach ist, ist der längste Abstieg 0. (nicht 19, da die Pfadsequenz streng absteigend sein muss)
Höhenkarten können aus größeren Zahlen als einstelligen Zahlen bestehen.
10 12 13 14 15 15
17 14 15 15 15 16
18 20 21 15 15 15
21 14 10 11 11 15
15 15 15 15 15 15
Der längste Weg hat hier die Länge 6. (21, 20, 18, 17, 14, 12, 10)
... und noch größere Zahlen sind auch in Ordnung.
949858 789874 57848 43758 387348
5848 454115 4548 448545 216464
188452 484126 484216 786654 145451
189465 474566 156665 132645 456651
985464 94849 151654 151648 484364
Der längste Abstieg ist hier von Länge 7. (786654, 484216, 484126, 474566, 156665, 151654, 151648, 132645)
Regeln und Hinweise
- Raster können in jedem geeigneten Format erstellt werden. Geben Sie Ihr Format in Ihrer Antwort an.
- Sie können davon ausgehen, dass die Höhenzuordnung perfekt rechteckig ist, nicht leer ist und nur positive Ganzzahlen im vorzeichenbehafteten 32-Bit-Ganzzahlbereich enthält.
- Der längste Abstiegsweg kann an einer beliebigen Stelle im Raster beginnen und enden.
- Sie müssen den längsten Abstiegsweg in keiner Weise beschreiben. Nur seine Länge ist erforderlich.
- Der kürzeste Code gewinnt
Antworten:
JavaScript (ES7),
106 103 10298 ByteProbieren Sie es online aus!
Kommentiert
Wie?
quelle
Gelee ,
23 2120 Bytes-2 danke an Erik den Outgolfer
Probieren Sie es online aus! (viel zu ineffizient für die Beispiele - Pfad hier ist
95 94 93 83 77 40 10
so6
ergibt sich)Wie?
quelle
Python 2,
150147140136134132125123120 BytesProbieren Sie es online aus!
Nimmt Eingaben in Form eines Wörterbuchs vor
(x, y): value
.-7 Bytes dank wizzwizz4, -2 Bytes dank Jonathan Allen, -2 Bytes dank BMO
Alternative
123121 BytesProbieren Sie es online aus!
Im Wesentlichen die gleiche Lösung, nur dass das endgültige Lambda durch ein tatsächliches Programm ersetzt wird. Ich persönlich mag den ersten besser, aber dieser kommt der Anzahl der Bytes sehr nahe
g
, da er als globale Variable verwendet werden kann.quelle
Sauber ,
211207 BytesProbieren Sie es online aus!
Eine Brute-Force-Lösung, die eine Liste von Listen mit ganzen Zahlen (
[[Int]]
) verwendet.Der TIO-Treiber hat das gleiche Format wie die Beispiele über STDIN.
Es ist zu langsam, eines der Beispiele auf TIO und wahrscheinlich auch lokal auszuführen, funktioniert aber theoretisch.
Dieser macht das gleiche schneller, kann 3x3 oder 2x4 auf TIO und 4x4 und 3x5 lokal machen.
Eingerückt:
quelle
Python 3 , 219 Bytes
Probieren Sie es online aus!
Das Raster wird als Liste von Listen dargestellt:
Ursprünglicher ungolfed Code:
quelle
Haskell ,
188186 BytesProbieren Sie es online aus!
notElem
(not.).(#)
Probieren Sie es online aus!
Erklärung & Ungolfed
Strategie: Probieren Sie rekursiv alle möglichen Pfade aus, verfolgen Sie die besuchten Einträge und maximieren Sie deren Länge.
elem
notElem
(#)
elem
maximize
Jetzt können wir unsere rekursive Funktion definieren
fun :: [[Integer]] -> Integer
:quelle
[[Integer]]
Liste der Listen. Obwohl Sie in der verknüpften TIO einen Wrapper habenparse :: String -> [[Integer]]
, st. Sie können Zeichenfolgen verwenden, die auf Leerzeichen und neue Zeilen aufgeteilt sind.Python 3,
263227 BytesProbieren Sie es online aus!
-2 Bytes dank BMO
Nimmt Gitter im Format auf
{(0, 0): 1, (1, 0): 2, ...}
. Dieses Format kann aus dem Beispielformat mit der folgenden Dienstprogrammfunktion generiert werden:quelle