Python Tutorial deutsch, Advent of Code 2019, Tag 20 'Donut Maze'

Lösungen in Python 3.7 zu Advent of Code 2019

Wir suchen den kürzesten Weg durch ein Labyrinth voller Portale (Teil 1) und Dimensionsportalen (Teil 2).

[joerglaukemper]

Puh, der Teil zwei hat mir viel Kopfzerbrechen bereitet. Ich habe mich aufgrund der Aufgabenbeschreibung dazu verleiten lassen, den Breitensuch-Algorithmus von Teil eins im Teil 2 rekursiv aufzurufen. Das führte dann zu einer Tiefensuche in den unteren Ebenen. Und das war fatal, denn man gerät in eine Endlosschleife, die einen immer tiefer in die Level führt. Das passiert auch schon bei dem Beispiel von Teil 2. Von all dem merkt man bei dem genialen Gravitar Ansatz nichts, weil man bei der Breitensuche immer wieder in die oberen Ebenen zurückkommt. Super gemacht!
Nachdem ich die Rekursion aufgegeben, und auch die Level mit einer Breitensuche durchlaufen habe, ist mir Anfangs noch ein Fehler unterlaufen, der mich sehr verwundert hat: Bei mir ist jede Zelle im Labyrinth eine Klasse, die unter anderem auch die Anzahl der Schritte enthält. Das führt natürlich im Part zwei zu einem Fehler, weil die Schrittzahl unter Umständen in einer tieferen Ebene überschrieben wird. Das verwunderliche war, dass mein falsches Endergebnis von Lauf zu Lauf ein anderes war???? Ich habe im BFS als FIFO eine Queue genommen und die mit put_nowait und get_nowait gefüllt, bzw. gelesen. Das unterschiedliche Ergebnis von Lauf zu Lauf kann ja eigentlich nur ein Threading Problem sein, oder was sonst? Wobei ich dachte, dass das bei Verwendung von xx_nowait doch eigentlich nicht sein kann.

Noch eine kurze Anmerkung zum Video: In der Aufgabenbeschreibung ist es tatsächlich erwähnt, dass Level kleiner Null nicht zulässig sind. Es wird gesagt, dass in der Ebene Null alle außen liegenden Ports durch Wände verschlossen sind.

[tombow]

Wünsche mir rießig matrixbeispiele wie game of life und needleman algorithmus für dieses Jahr!, egal wann, nur vielleicht gefallen dir die Vorschläge.