You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
80 lines
2.9 KiB
80 lines
2.9 KiB
from queue import PriorityQueue |
|
import sys |
|
|
|
class grid: |
|
def __init__(self): |
|
self.y = [] |
|
self.attempts = 0 |
|
self.solutions = [] |
|
self.current_smallest_solution_level = None |
|
self.point_costs = {(0, 0): 0} |
|
self.next_point_queue = PriorityQueue() |
|
self.next_point_queue.put((0, (0, 0))) |
|
|
|
def addline(self, line): |
|
self.y.append([int(i) for i in line]) |
|
self.maxy = len(self.y) - 1 |
|
self.maxx = len(self.y[0]) - 1 |
|
|
|
# print(self.maxx) |
|
# print(self.maxy) |
|
|
|
def findpath(self): |
|
while not self.next_point_queue.empty(): |
|
level, poi = self.next_point_queue.get() |
|
self.attempts += 1 |
|
if self.attempts % 100000 == 0: |
|
print('Attempt %d, solutions: %d, cost: %d' % (self.attempts, len(self.solutions), self.current_smallest_solution_level or -1)) |
|
|
|
neighbors = self.get_neighbors(poi) |
|
|
|
for i in neighbors: |
|
next_level = level + int(self.y[i[0]][i[1]]) |
|
if (self.current_smallest_solution_level is not None and |
|
next_level > self.current_smallest_solution_level): |
|
# We already found a solution that was overall less risky |
|
# than the current path, so who cares. |
|
continue |
|
if i == (self.maxy, self.maxx): |
|
self.solutions.append(next_level) |
|
if (self.current_smallest_solution_level is None or |
|
next_level < self.current_smallest_solution_level): |
|
self.current_smallest_solution_level = next_level |
|
# print('Found solution: ', i, ', orig level ', level) |
|
continue |
|
elif i in self.point_costs and self.point_costs[i] < next_level: |
|
# We already visited the point on a cheaper path. |
|
continue |
|
else: |
|
# print('Path: %s, next: %s' % (repr(path), i)) |
|
self.point_costs[i] = next_level |
|
self.next_point_queue.put((next_level, i)) |
|
|
|
def get_neighbors(self, poi): |
|
nex = {} |
|
rv = [] |
|
if poi[0] != self.maxy: |
|
nex.setdefault(self.y[poi[0] + 1][poi[1]], list()).append((poi[0] + 1, poi[1])) |
|
if poi[1] != self.maxx: |
|
nex.setdefault(self.y[poi[0]][poi[1] + 1], list()).append((poi[0], poi[1] + 1)) |
|
if poi[0] != 0: |
|
nex.setdefault(self.y[poi[0] - 1][poi[1]], list()).append((poi[0] - 1, poi[1])) |
|
if poi[1] != 0: |
|
nex.setdefault(self.y[poi[0]][poi[1] - 1], list()).append((poi[0], poi[1] - 1)) |
|
|
|
order = sorted(nex.keys()) |
|
|
|
for j in order: |
|
rv += nex[j] |
|
|
|
return rv |
|
|
|
gri = grid() |
|
|
|
with open(sys.argv[1], 'r') as f: |
|
for i in f.readlines(): |
|
gri.addline(i.strip()) |
|
|
|
gri.findpath() |
|
|
|
print(min(gri.solutions)) |