2025_07.md

Tag 07 - Pfad-Verzweigungen mit Dynamic Programming

Aufgabe

Simulation von Pfaden, die sich bei Hindernissen verzweigen:

• Teil 1: Wie viele Hindernisse werden getroffen?
• Teil 2: Wie viele verschiedene Pfade gibt es am Ende?

Lösung

Eingabeformat

Eine 2D-Karte mit:

• S: Startposition (in erster Zeile)
• .: Freier Weg (Pfad geht gerade weiter)
• Andere Zeichen: Hindernisse (Pfad verzweigt sich)

Beispiel:

...S...
...|...
..|^|..
..|.|..

Algorithmus

Dynamic Programming mit Dictionary für Pfad-Zählung:

def main():
    positionen = {aufgabe.zeilen[0].index("S"): 1}
    for zeile in aufgabe.zeilen[1:]:
        if zeile.count(".") == len(zeile):
            continue
        neue_positionen = {}
        for position, anzahl in positionen.items():
            if zeile[position] == ".":
                neue_positionen[position] = neue_positionen.get(position, 0) + anzahl
            else:
                neue_positionen[position-1] = neue_positionen.get(position-1, 0) + anzahl
                neue_positionen[position+1] = neue_positionen.get(position+1, 0) + anzahl
                aufgabe.loesung1 += 1
        positionen = neue_positionen
    aufgabe.loesung2 = sum(positionen.values())

Funktionsweise

1. Initialisierung

positionen = {aufgabe.zeilen[0].index("S"): 1}

Logik:

• Finde die Spalten-Position von "S" in der ersten Zeile
• Starte mit 1 Pfad an dieser Position
• Dictionary: {position: anzahl_pfade}

Beispiel: "...S..." → positionen = {3: 1}

2. Zeilen-Optimierung

if zeile.count(".") == len(zeile):
    continue

Logik:

• Wenn Zeile nur . enthält (keine Hindernisse)
• Überspringe Zeile (Pfade bleiben gleich)
• Optimierung: Spart unnötige Berechnungen

3. Pfad-Propagierung

Für jede Position mit Pfaden:

for position, anzahl in positionen.items():

• position: Spalten-Index
• anzahl: Wie viele Pfade sind an dieser Position

Fall A: Freier Weg (.):

if zeile[position] == ".":
    neue_positionen[position] = neue_positionen.get(position, 0) + anzahl

• Pfad geht gerade weiter (gleiche Position)
• Alle Pfade dieser Position bleiben zusammen
• Addiere zur neuen Position (falls mehrere Pfade dort zusammenkommen)

Fall B: Hindernis (nicht .):

else:
    neue_positionen[position-1] = neue_positionen.get(position-1, 0) + anzahl
    neue_positionen[position+1] = neue_positionen.get(position+1, 0) + anzahl
    aufgabe.loesung1 += 1

• Pfad verzweigt sich nach links und rechts
• Jeder der anzahl Pfade spaltet sich → beide Richtungen bekommen anzahl Pfade
• Wichtig: Hindernisse werden pro Position einmal gezählt, nicht pro Pfad!
• loesung1 zählt Anzahl der Hindernisse, nicht Anzahl Verzweigungen

4. Position Update

positionen = neue_positionen

• Ersetze alte Positionen durch neue
• Bereitet nächste Zeile vor

5. Endergebnis

aufgabe.loesung2 = sum(positionen.values())

• Summiere alle Pfade an allen Positionen
• Ergibt Gesamtzahl verschiedener Pfade am Ende

Beispiel-Durchlauf

Eingabe:

..S..
.....
..#..
.....

Zeile 0: ..S..

• positionen = {2: 1} (S ist an Index 2)

Zeile 1: ..... (nur Punkte)

• Übersprungen (Optimierung)
• positionen = {2: 1} (unverändert)

Zeile 2: ..#..

• Position 2 hat 1 Pfad, Zeichen ist # (Hindernis)
• Verzweigung: {1: 1, 3: 1} (links und rechts)
• loesung1 += 1 → loesung1 = 1

Zeile 3: ..... (nur Punkte)

• Übersprungen
• positionen = {1: 1, 3: 1} (unverändert)

Ende:

• loesung1 = 1 (ein Hindernis getroffen)
• loesung2 = 1 + 1 = 2 (zwei verschiedene Pfade)

Beispiel mit Pfad-Verdopplung

Eingabe:

.S.
.#.
...

Zeile 0: .S.

• positionen = {1: 1}

Zeile 1: .#.

• Position 1 hat 1 Pfad, Zeichen ist #
• Verzweigung: {0: 1, 2: 1}
• loesung1 = 1

Zeile 2: ...

• Übersprungen
• positionen = {0: 1, 2: 1}

Ende:

• loesung1 = 1
• loesung2 = 2

Beispiel mit Pfad-Zusammenführung

Eingabe:

S.S
...
.#.
...

Zeile 0: S.S

• positionen = {0: 1} (nur erstes S wird von index() gefunden)
• Achtung: Code berücksichtigt nur ein S!

Angenommen beide S würden erkannt:

• positionen = {0: 1, 2: 1}

Zeile 1: ...

• Übersprungen
• positionen = {0: 1, 2: 1}

Zeile 2: .#.

• Position 0: Pfad geht zu Position 0 (.)
• Position 2: Pfad geht zu Position 2 (.)
• Keine Verzweigung! Position 1 hat keine Pfade
• positionen = {0: 1, 2: 1}

Zeile 3: ...

• positionen = {0: 1, 2: 1}

Ende:

• loesung1 = 0 (kein Hindernis getroffen)
• loesung2 = 2

Pfad-Verdopplung durch mehrere Hindernisse

Eingabe:

..S..
..#..
.#.#.
.....

Zeile 0: ..S..

• positionen = {2: 1}

Zeile 1: ..#..

• Position 2: Hindernis → {1: 1, 3: 1}
• loesung1 = 1

Zeile 2: .#.#.

• Position 1: Zeichen ist # → Verzweigung zu {0: 1, 2: 1}
• Position 3: Zeichen ist # → Verzweigung zu {2: 1, 4: 1}
• Zusammenführung: Position 2 bekommt Pfade von beiden!
• neue_positionen = {0: 1, 2: 2, 4: 1}
• loesung1 = 3 (3 Hindernisse total)

Zeile 3: .....

• positionen = {0: 1, 2: 2, 4: 1}

Ende:

• loesung1 = 3
• loesung2 = 1 + 2 + 4 = 7 Falsch! 1 + 2 + 1 = 4

Warum Dictionary statt Liste?

Vorteile:

• Sparse Array: Nur benutzte Positionen werden gespeichert
• Automatisches Merging: .get(position, 0) für Zusammenführung
• Keine Index-Fehler: Keine Sorge um Array-Grenzen

Alternative mit Liste:

• Müsste gesamte Breite allokieren
• Viele Positionen hätten Wert 0
• Mehr Speicher, langsamere Iteration

Komplexität

• Zeit: O(n * k) wobei n = Anzahl Zeilen, k = durchschnittliche Anzahl besetzter Positionen
  • Pro Zeile: Iteration durch aktive Positionen
  • k ist meist klein (Pfade konzentrieren sich)
• Platz: O(k) für Dictionary
  • Nur aktive Positionen gespeichert

Besonderheiten

• Dynamic Programming: Speichert Pfad-Anzahl statt einzelne Pfade
• Sparse Dictionary: Effizient für breite, wenig besetzte Karten
• Optimierung: Überspringt Zeilen ohne Hindernisse
• Exponentielles Wachstum möglich: Jedes Hindernis kann Pfade verdoppeln
• Dictionary.get(): Idiomatisches Pattern für Default-Werte
• Keine Pfad-Explosion: Speichert nur Anzahl, nicht jeden Pfad einzeln