85 lines
2.5 KiB
Python
85 lines
2.5 KiB
Python
import time
|
||
from vorlesung.L08_graphen.graph import AdjacencyListGraph
|
||
|
||
# AoC 2024, Tag 16 – erstes Beispiel-Labyrinth (Antwort: 7036)
|
||
GRID = """\
|
||
###############
|
||
#.......#....E#
|
||
#.#.###.#.###.#
|
||
#.....#.#...#.#
|
||
#.###.#####.#.#
|
||
#.#.#.......#.#
|
||
#.#.#####.###.#
|
||
#...........#.#
|
||
###.#.#####.#.#
|
||
#...#.....#.#.#
|
||
#.#.#.###.#.#.#
|
||
#.....#...#.#.#
|
||
#.###.#.#.#.#.#
|
||
#S..#.....#...#
|
||
###############""".strip().split('\n')
|
||
|
||
# Richtungen: 0=N, 1=O, 2=S, 3=W (O = Ost = Startrichtung des Rentiers)
|
||
DR = [-1, 0, 1, 0]
|
||
DC = [0, 1, 0, -1]
|
||
|
||
|
||
def build_graph(grid):
|
||
g = AdjacencyListGraph()
|
||
rows, cols = len(grid), len(grid[0])
|
||
start = end = None
|
||
|
||
for r in range(rows):
|
||
for c in range(cols):
|
||
if grid[r][c] == '#':
|
||
continue
|
||
if grid[r][c] == 'S':
|
||
start = (r, c)
|
||
elif grid[r][c] == 'E':
|
||
end = (r, c)
|
||
for d in range(4):
|
||
g.insert_vertex(f"{r},{c},{d}")
|
||
|
||
for r in range(rows):
|
||
for c in range(cols):
|
||
if grid[r][c] == '#':
|
||
continue
|
||
for d in range(4):
|
||
src = f"{r},{c},{d}"
|
||
# Vorwärtsbewegen (Kosten 1)
|
||
nr, nc = r + DR[d], c + DC[d]
|
||
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != '#':
|
||
g.connect(src, f"{nr},{nc},{d}", 1)
|
||
# Drehen links und rechts (Kosten 1000 je Drehung)
|
||
g.connect(src, f"{r},{c},{(d - 1) % 4}", 1000)
|
||
g.connect(src, f"{r},{c},{(d + 1) % 4}", 1000)
|
||
|
||
return g, start, end
|
||
|
||
|
||
# --- a) + b) Graph aufbauen und Dijkstra ausführen ---
|
||
|
||
g, start, end = build_graph(GRID)
|
||
v_count = len(list(g.all_vertices()))
|
||
e_count = len(g.all_edges())
|
||
print(f"Graph: |V| = {v_count}, |E| = {e_count}")
|
||
|
||
start_state = f"{start[0]},{start[1]},1" # Startposition, Blickrichtung Ost (1)
|
||
dist_map, pred_map = g.dijkstra(start_state)
|
||
|
||
# Bestes Zielfeld: E in beliebiger Richtung (4 zulässige Zielzustände)
|
||
end_vertices = [g.get_vertex(f"{end[0]},{end[1]},{d}") for d in range(4)]
|
||
best_end = min(end_vertices, key=lambda v: dist_map[v])
|
||
print(f"Gesamtkosten: {dist_map[best_end]}") # Erwartung: 11048
|
||
|
||
pfad = g.path(best_end.value, pred_map)
|
||
print(f"Pfad: {len(pfad)} Zustände ({len(pfad) - 1} Schritte)")
|
||
print("Erste Schritte:", " -> ".join(pfad[:5]), "...")
|
||
print("Letzte Schritte: ...", " -> ".join(pfad[-3:]))
|
||
|
||
# --- c) Laufzeitmessung ---
|
||
t0 = time.perf_counter()
|
||
g.dijkstra(start_state)
|
||
t1 = time.perf_counter()
|
||
print(f"\nLaufzeit (Beispiel): {(t1 - t0) * 1000:.3f} ms")
|