Tag 18 - Lavaduct Lagoon

Ich habe für Teil 1 und Teil 2 verschiedene Lösungswege genutzt.

Lösungshinweise Teil 1

  • Finde zunächst heraus, wie groß der auszugrabende Bereich in die Breite und die Höhe sein muss.
  • Erstelle ein char[][]-Array mit der passenden Größe.
  • Trage den Input-Befehlen folgend ein 't' für "Trench" (Graben) in das char[][]-Array an jeder nötigen Stelle ein. Dadurch erhältst du den kompletten geschlossenen Verlauf des äußeren Grabens.
  • Abschließend füllst du von jedem äußeren Pixel an den Kanten des char[][]-Arrays per Breitensuche die leeren Felder mit einem 'o' für "outside". Danach ist jedes leere Feld ein inneres Feld. Die Summe aller Lava-Pool-Felder ist die summe aller leeren Felder und aller 't'-Felder.

Lösungsvorschlag

Lösungshinweise Teil 2

  • Für Teil 2 werden die Zahlen zu groß, sodass die Lösung aus Teil 1 nicht mehr ausreicht. Die Hauptvorgehensweise ist folgende:

  • Gehe der Reihe nach die Befehle entlang. Trage aber keine Kreuze in eine 2-dimensionale Matrix, sondern betrachte nur die einzelnen Spalten (x-Werte). Führe eine ArrayList, um pro Spalte mehrere y-Werte eintragen zu können, an denen "etwas passiert".:
    • Wenn du gerade nach rechts läufst, dann markierst du, dass du mit dem aktuellen y-Wert das obere Ende des Lava-Pools.
    • Beim nach links laufen markierst du mit dem y-Wert das untere Ende des Lava-Pools.
    • Wenn du nach unten läufst, dann ist dein oberer Startpunkt, das obere Ende des Lava-Pools. Als weiteren y-Wert trägst du ein, wie viele y-Werte du weiter nach unten zu gehen hast (das ist dann ein mögliches unteres Ende des Pools).
    • Beim nach oben laufen ist der untere Startpunkt ein unteres Ende des Pools, und beim "Ziel" des nach-oben-laufens ist das obere Ende des Pools.
  • Beispiel für das rechte Bild (Annahme, dass die Erstellung des Pfades im Uhrzeigersinn geschah): in der Spalte für x=5 stehen folgende y-Werte drin:
0 (wegen "rechts")
0 (wegen oberes Ende von "oben")
1 (wegen "rechts")
1 (wegen unteres Ende von "oben")
3 (wegen "links")
5 (wegen "rechts")
5 (wegen oberes Ende von "unten")
7 (wegen unteres Ende von "unten")
7 (wegen "links")

Nun muss man zusätzlich noch unterscheiden, ob die Eintragung jeweils das obere oder untere Ende vom Pool markiert. Platzsparend kann man dies z. B. tun, indem man die Zahlen als String abspeichert und hinten eine 0 für oberes Ende und 1 für unteres Ende anhängt. Damit steht eigentlich in der Spalte:

00
00
10
11
31
50
50
71
71

Hat man diese Werte, kann man schnell die Differenzen ausrechnen und damit die Fläche über alle Spalten aufsummieren. Wichtig ist nun, die Werte noch zu bereinigen: y=1 hat die Endung 0 und 1 (kommt doppelt vor). Wir können daher y=1 gänzlich aus der Liste streichen. Ebenso können wir alle anderen Dopplungen streichen und müssen die Einträge sortieren (der Pfad kann "chaotisch" verlaufen und die Werte müssen nicht bereits automatisch aufsteigend sortiert sein. Am Ende bleibt übrig:

00
31
50
71

Die Fläche in der einen Spalte ist also: ( (3-1) + 1) + ( (7-5) + 1)

Lösungsvorschlag Teil 2