Für Part2 wird hier der Jordanscher Kurvensatz verwendet.
Der besagt grob, dass von einem Punkt ein Strahl in einer x-beliebigen Richtung gesendet wird - und dann die "Kreuzungen" mit dem Polygon gezählt werden.
Man kann selber ein paar Bsp. zeichnen und probieren.
Das Problem sind die Geraden die "längs" getroffen werden. Und hier habe ich eine Weile überlegt - aber es ist genial - wie damit alle Fälle erschlagen werden.
Angenommen der Strahl bewegt sich in x-Richtung - dann werden erstmal nur die "|" Zeichen gezählt.
Dann müssen folgende Fälle unterschieden werden: Gerade, die die Richtung beibehalten und Geraden die Richtung wechseln.
Durch die verwendeten Symbole wird im ersten Fall eine gerade Zahl (2 oder 0) und im zweiten Fall eine 1 zurück geliefert.
Dies mit der Anzahl von "|" ergibt die richtige Lösung - ist verblüffend.
jensgutow
Heute war wirklich schwierig. Deine Lösung für Part 2 ist echt schlau, da bin ich leider nicht drauf gekommen. Ich habe stattdessend eine ganz andere Lösung gefunden:
Ich habe zunächst das Feld in einer 2d-Liste gespeichert. Um die umschlossenen Bereiche zu finden, habe ich dann das gesamte Feld einschließlich der Loop "ausgedehnt". Das heißt, ich habe die Höhe und die Breite des Feldes verdoppelt und dabei die fehlenden Rohre der Loop hinzugefügt. Dadurch eröffnen sich neue Wege, zwischen den Teilen der Loop, die direkt nebeneinander verlaufen. Auf diese Weise besitzen jetzt alle Bereiche, die nicht von der Loop umschlossen sind, einen Weg zum Rand des Feldes. Mit mehreren Breitensuchen findet man nun die umschlossenen Bereiche und zählt die Anzahl der Kacheln. Hierbei muss man die Anzahl der 2x2 Blöcke zählen, weil man das Spielfeld ja vergrößert hat.
Diese Lösung ist umständlich zu programmieren aber funktioniert :)
Programmieren-mit-Pascal
wie immer eine geniale Lösung.
Die loop ist ein Polygon. Ich habe aus dem shapely.geometry Modul Point und Polygon importiert. Damit kann man Punkte innerhalb eines Polgons ermitteln. Dauert aber wesentlich länger (158 sek)
ruwenda
18:16min -> "....war doch gar nicht so schwer" . Jetzt trennt sich die Spreu vom Weizen - mein Name ist "Spreu". 😞
romanbuchta
Die Lösung für Part 2 liefert nicht in allen Fällen das korrekte Ergebnis. Für eine allgemein funktionierende Lösung muss das Startsymbol S durch das passende Symbol für das Tile ersetzt werden.
Beim Input aus dem Video macht das keinen Unterschied, aber z.B. für meinem Input wird ein zu großes Ergebnis zurück geliefert.
