forked from hofmannol/AlgoDatSoSe25
60 lines
2.4 KiB
Python
60 lines
2.4 KiB
Python
from utils.project_dir import get_path
|
|
from vorlesung.L08_graphen.graph import AdjacencyListGraph
|
|
|
|
DIRECTIONS = [(1,0), (0, 1), (-1, 0), (0, -1)]
|
|
|
|
class D16Solution:
|
|
|
|
def __init__(self):
|
|
with open(get_path("data/aoc2416.txt"), "r") as file:
|
|
self.puzzle = [line.strip() for line in file]
|
|
self.cells = set()
|
|
self.start = None
|
|
self.end = None
|
|
|
|
def get_cells_start_end(self):
|
|
for row in range(len(self.puzzle)):
|
|
for col in range(len(self.puzzle[row])):
|
|
if self.puzzle[row][col] != '#':
|
|
self.cells.add((col, row))
|
|
if self.puzzle[row][col] == 'S':
|
|
self.start = (col, row)
|
|
if self.puzzle[row][col] == 'E':
|
|
self.end = (col, row)
|
|
|
|
def get_label(self, cell, direction):
|
|
"""Generate a label for a cell based on its coordinates and direction."""
|
|
return f"{cell[0]},{cell[1]}_{direction}"
|
|
|
|
def create_graph(self):
|
|
graph = AdjacencyListGraph()
|
|
for cell in self.cells:
|
|
for direction in DIRECTIONS:
|
|
label = self.get_label(cell, direction)
|
|
graph.insert_vertex(label)
|
|
for cell in self.cells:
|
|
for d, direction in enumerate(DIRECTIONS):
|
|
label = self.get_label(cell, direction)
|
|
dx, dy = direction
|
|
neighbor = (cell[0] + dx, cell[1] + dy)
|
|
if neighbor in self.cells:
|
|
graph.connect(label, self.get_label(neighbor, direction))
|
|
direction_left = DIRECTIONS[(d - 1) % 4]
|
|
direction_right = DIRECTIONS[(d + 1) % 4]
|
|
graph.connect(label, self.get_label(cell, direction_left), 1000)
|
|
graph.connect(label, self.get_label(cell, direction_right), 1000)
|
|
return graph
|
|
|
|
if __name__ == "__main__":
|
|
solution = D16Solution()
|
|
solution.get_cells_start_end()
|
|
graph = solution.create_graph()
|
|
start = solution.get_label(solution.start, DIRECTIONS[0])
|
|
print(f"Start: {start}")
|
|
distance_map, predecessor_map = graph.dijkstra(start)
|
|
end_labels = [solution.get_label(solution.end, direction) for direction in DIRECTIONS]
|
|
end_vertices = [graph.get_vertex(label) for label in end_labels]
|
|
min_weight = min([distance_map[vertex] for vertex in end_vertices])
|
|
print(f"Minimum distance to End {solution.end}: {min_weight}")
|
|
|