96 lines
2.8 KiB
Python
Executable File
96 lines
2.8 KiB
Python
Executable File
#!/usr/bin/env python3
|
|
# -*- coding: utf-8 -*-
|
|
from collections import defaultdict
|
|
|
|
file = "./input.txt"
|
|
cheat_time = 100
|
|
#file = "./ex.txt"
|
|
#cheat_time = 25
|
|
|
|
from time import time
|
|
from copy import deepcopy
|
|
import heapq
|
|
start_time = time()
|
|
|
|
def print_grid(f):
|
|
for r in f:
|
|
for s in r:
|
|
print(s, end="")
|
|
print()
|
|
|
|
def fill_grid(gri:list[list[str]], ma:list[tuple[int,int]], filler:str)->list[list[str]]:
|
|
result = deepcopy(gri)
|
|
for m in ma:
|
|
x , y = m[0],m[1]
|
|
result[y][x] = filler
|
|
return result
|
|
|
|
|
|
def read_input(input_file:str, ) -> list[list[str]]:
|
|
result_grid = []
|
|
f = open(input_file, "r")
|
|
for line in f:
|
|
line = line.strip()
|
|
if line == "":
|
|
continue
|
|
else:
|
|
temp = []
|
|
for b in line:
|
|
temp.append(b)
|
|
result_grid.append(temp)
|
|
f.close()
|
|
return result_grid
|
|
|
|
def find_start_end(maze:list[list[str]])->tuple[tuple[int,int],tuple[int,int]]:
|
|
rows, cols = len(maze), len(maze[0])
|
|
for r in range(rows):
|
|
for c in range(cols):
|
|
if maze[r][c] == 'S':
|
|
start_point = (r, c)
|
|
elif maze[r][c] == 'E':
|
|
end_point = (r, c)
|
|
return start_point, end_point
|
|
|
|
def shortest_path(maze,start,end):
|
|
rows, cols = len(maze), len(maze[0])
|
|
# Dijkstra-Algorithmus
|
|
queue = [(0, start, [])]
|
|
visited = set()
|
|
while queue:
|
|
distance, current, path = heapq.heappop(queue)
|
|
if current == end:
|
|
# return distance, path + [current]
|
|
return distance, [(y, x) for x, y in path + [current]]
|
|
if current in visited:
|
|
continue
|
|
visited.add(current)
|
|
for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
|
|
nx, ny = current[0] + dx, current[1] + dy
|
|
if 0 <= nx < rows and 0 <= ny < cols and maze[nx][ny] != '#':
|
|
heapq.heappush(queue, (distance + 1, (nx, ny), path + [current]))
|
|
return None, []
|
|
|
|
if __name__ == "__main__":
|
|
grid = read_input(file)
|
|
p_start, p_end = find_start_end(grid)
|
|
sol = shortest_path(grid, p_start, p_end)
|
|
full_path_len = sol[0]
|
|
#print(sol)
|
|
#print(f"Shortest Path Length: {sol[0]}")
|
|
#print_grid(fill_grid(grid,sol[1],"O"))
|
|
counts = defaultdict(int)
|
|
for i in range(1,len(grid)-1):
|
|
for j in range(1,len(grid[0])-1):
|
|
if grid[i][j] == "#":
|
|
grid[i][j] = "."
|
|
t_sol = shortest_path(grid, p_start, p_end)
|
|
if t_sol and t_sol[0] < sol[0]:
|
|
counts[abs(t_sol[0]-sol[0])] += 1
|
|
grid[i][j] = "#"
|
|
p1_solution = 0
|
|
print(counts)
|
|
for key in counts.keys():
|
|
if key >= cheat_time:
|
|
p1_solution += counts[key]
|
|
print(f"Solution Part 1: {p1_solution}")
|
|
print(f'Runtime: {time()-start_time:.4f} s') |