Tag 17 - Clumsy Crucible

Lösungshinweise Teil 1

  • Die Aufgabe ist ein "Shortest Path Problem" ("Kürzester Pfad Problem") und lässt sich z. B. mit dem Dijkstra-Algorithmus lösen!
  • Die Lösung ist allerdings trotzdem nicht trivial, denn es genügt nicht, die Ziffern in der 2D-Matrix als einzige Knoten aufzufassen. Die Einschränkung, dass Wege maximal 3 Schritte lang in einer Richtung verlaufen dürfen, zwingt einen dazu, jede Koordinate als insgesamt 12 mögliche Knoten aufzufassen. Beispiel zu einer beliebigen Koordinate mitten im Feld: Je nachdem, ob ich die Koordinate von links, rechts, oben oder unten betreten habe und jeweils zuvor 1, 2 oder 3 Schritte lang geradeaus lief, kann die Koordinate unterschiedliche Distanzen aufweisen.
  • Ein gutes Beispiel zu diesem Tag, das man auf reddit finden kann, ist folgender kleiner Input:
112999
911111

Das korrekte Ergebnis muss 7 sein! Dazu muss dein Algorithmus in der Lage sein, auch den zunächst nachteilig erscheinenden Schritt horizontal in die "2" zu betrachten.

Der nachfolgende Lösungsvorschlag ist mangels Zeit leider weder besonders performant, noch besonders schön aufgeräumt oder kommentiert. Es gibt ein zweidimensionales Array, das Koordinaten speichert. Koordinaten sind eine eigene Klasse. Pro Koordinate werden 4 Arrays à 3 Blöcken gespeichert. Jedes Array ist für eine Richtung, in die man sich auf dem jeweiligen Block bewegt. Jeder Block ist ebenso eine eigene Klasse, die nochmals einige Informationen speichert und insbesondere die individuelle Distanz und den Hitzeverlust speichert.

Lösungsvorschlag Klasse Block

Lösungsvorschlag Klasse Koordinaten

Lösungsvorschlag Teil 2

Lösungshinweise Teil 2

Für Teil 2 müssen die Wege-Einschränkungen aus Teil 1 nur minimal überarbeitet werden: jeder Abschnitt muss genau zwischen 4-10 Schritte lang in einer Richtung verlaufen.