64 lines
1.7 KiB
Python
64 lines
1.7 KiB
Python
#!/usr/bin/env python3
|
|
import heapq
|
|
|
|
import numpy as np
|
|
|
|
lines = np.array([np.array([ord(y) for y in x.strip()]) for x in open("input.txt")])
|
|
start = tuple(np.array(np.where(lines == ord('S'))).T[0])
|
|
end = tuple(np.array(np.where(lines == ord('E'))).T[0])
|
|
|
|
lines[np.where(lines == ord('S'))] = ord('a')
|
|
lines[np.where(lines == ord('E'))] = ord('z')
|
|
lines = lines-ord('a')
|
|
|
|
def neighbors(n):
|
|
x, y = n
|
|
if x > 0 and lines[n] - 1 <= lines[x-1, y]:
|
|
yield x - 1, y
|
|
if y > 0 and lines[n] - 1 <= lines[x, y-1]:
|
|
yield x, y - 1
|
|
if x+1 < len(lines) and lines[n] - 1 <= lines[x+1, y]:
|
|
yield x + 1, y
|
|
if y+1 < len(lines[0]) and lines[n] - 1 <= lines[x, y+1]:
|
|
yield x, y + 1
|
|
|
|
def distance(n1, n2):
|
|
return 1
|
|
|
|
def cost(n):
|
|
return lines[n]
|
|
|
|
def is_end(n):
|
|
return lines[n] == 0
|
|
|
|
|
|
def find_path(start, end_fnct, neighbors_fnct, heuristic_cost_estimate_fnct, distance_between_fnct):
|
|
open = [(0, 0, start, None)]
|
|
closed = dict()
|
|
while open:
|
|
_, prio, n, prev = heapq.heappop(open)
|
|
if n in closed:
|
|
continue
|
|
closed[n] = (prio, prev)
|
|
if end_fnct(n):
|
|
path = [n]
|
|
while path[-1] is not None:
|
|
path.append(closed[path[-1]][1])
|
|
return path[:-1]
|
|
|
|
for neighbor in neighbors_fnct(n):
|
|
dist = prio + distance_between_fnct(n, neighbor)
|
|
heuristic = dist + heuristic_cost_estimate_fnct(neighbor)
|
|
heapq.heappush(open, (heuristic, dist, neighbor, n))
|
|
return None
|
|
|
|
|
|
path = list(find_path(
|
|
end,
|
|
end_fnct=is_end,
|
|
neighbors_fnct=neighbors,
|
|
heuristic_cost_estimate_fnct=cost,
|
|
distance_between_fnct=distance
|
|
))
|
|
|
|
print(len(path)-1) |