90 lines
3.0 KiB
Python
90 lines
3.0 KiB
Python
import time
|
|
import sys
|
|
import os
|
|
|
|
from vorlesung.L08_graphen.graph import AdjacencyListGraph
|
|
|
|
GRID = [
|
|
"Sabqponm",
|
|
"abcryxxl",
|
|
"accszExk",
|
|
"acctuvwj",
|
|
"abdefghi",
|
|
]
|
|
|
|
def height(ch):
|
|
if ch == 'S': return ord('a')
|
|
if ch == 'E': return ord('z')
|
|
return ord(ch)
|
|
|
|
def build_graph(grid):
|
|
rows = len(grid)
|
|
cols = len(grid[0])
|
|
g = AdjacencyListGraph()
|
|
for r in range(rows):
|
|
for c in range(cols):
|
|
g.insert_vertex(f"{r}_{c}")
|
|
for r in range(rows):
|
|
for c in range(cols):
|
|
for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
|
|
nr, nc = r + dr, c + dc
|
|
if 0 <= nr < rows and 0 <= nc < cols:
|
|
if height(grid[nr][nc]) - height(grid[r][c]) <= 1:
|
|
g.connect(f"{r}_{c}", f"{nr}_{nc}")
|
|
return g, rows, cols
|
|
|
|
def find_start_end(grid):
|
|
start = end = None
|
|
for r, row in enumerate(grid):
|
|
for c, ch in enumerate(row):
|
|
if ch == 'S': start = f"{r}_{c}"
|
|
if ch == 'E': end = f"{r}_{c}"
|
|
return start, end
|
|
|
|
def solve(grid, label="Beispielgelände"):
|
|
g, rows, cols = build_graph(grid)
|
|
start, end = find_start_end(grid)
|
|
|
|
t0 = time.perf_counter()
|
|
dist_map, pred_map = g.bfs(start)
|
|
t1 = time.perf_counter()
|
|
|
|
pfad = g.path(end, pred_map)
|
|
|
|
def fmt(node):
|
|
r, c = node.split("_")
|
|
return f"({r},{c})"
|
|
|
|
print(f"=== {label} ===")
|
|
print(f"|V| = {rows * cols}, |E| <= {rows * cols * 4} (real |E| gezählt separat)")
|
|
print(f"Pfadlänge: {len(pfad) - 1} Schritte")
|
|
print(f"Pfad: {' -> '.join(fmt(n) for n in pfad)}")
|
|
print(f"BFS-Laufzeit: {(t1 - t0) * 1000:.4f} ms")
|
|
print()
|
|
return rows * cols, t1 - t0
|
|
|
|
# --- a) Modellierung ---------------------------------------------------------
|
|
# Adjazenzliste ist besser geeignet: Das Grid ist licht (sparse).
|
|
# Jeder Knoten hat maximal 4 Nachbarn => |E| <= 4|V|.
|
|
# Eine Adjazenzmatrix hätte |V|^2 Einträge; für ein 41x122-Grid wären das
|
|
# über 25 Millionen Einträge, obwohl nur ~4*|V| davon belegt wären.
|
|
|
|
# --- b) Pfadsuche -------------------------------------------------------------
|
|
v_small, t_small = solve(GRID, "Beispielgelände (8x5)")
|
|
|
|
# --- c) AoC-Karte (optional) --------------------------------------------------
|
|
if len(sys.argv) > 1 and os.path.exists(sys.argv[1]):
|
|
with open(sys.argv[1]) as f:
|
|
aoc_grid = [line.rstrip() for line in f if line.strip()]
|
|
v_large, t_large = solve(aoc_grid, f"AoC-Karte ({len(aoc_grid)}x{len(aoc_grid[0])})")
|
|
ratio_v = v_large / v_small
|
|
ratio_t = t_large / t_small if t_small > 0 else float('inf')
|
|
print(f"Verhältnis |V|: {ratio_v:.1f}x")
|
|
print(f"Verhältnis Laufzeit: {ratio_t:.1f}x")
|
|
print(f"Lineares Wachstum bestätigt: {'ja' if abs(ratio_t / ratio_v - 1) < 0.5 else 'nein'}")
|
|
|
|
# --- d) Optional: bester Startpunkt (AoC Teil 2) ------------------------------
|
|
# Hinweis: Statt BFS von jedem 'a'-Feld zu starten, dreht man den Graphen um
|
|
# und startet eine einzige BFS von E rückwärts. Der erste erreichte 'a'-Knoten
|
|
# liefert den kürzesten Pfad.
|