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.
144 lines
4.3 KiB
144 lines
4.3 KiB
import copy |
|
from queue import PriorityQueue |
|
|
|
MAX_PRIO = ord('z') - ord('a') |
|
#log_this_is_n = 0 |
|
n_solutions = 0 |
|
|
|
q = PriorityQueue() |
|
|
|
|
|
#def log_every_n(message): |
|
# global log_this_is_n |
|
|
|
# log_this_is_n = (log_this_is_n + 1) % 100000 |
|
|
|
# if log_this_is_n == 0: |
|
# print(message) |
|
|
|
|
|
class PossiblePath: |
|
def __init__(self, y, x, visited): |
|
self.x = x |
|
self.y = y |
|
self.visited = tuple(visited) |
|
|
|
def __lt__(self, other): |
|
return (len(self.visited) < len(other.visited) or |
|
self.x < other.x or |
|
self.y < other.y) |
|
|
|
|
|
def MakeCandidate(x, y, visited, value_diff): |
|
if (y, x) in point_cost and point_cost[(y, x)] <= len(visited): |
|
return |
|
point_cost[(y, x)] = len(visited) |
|
|
|
prio_valuediff = value_diff * -1 |
|
prio_distance = (max(End[0], x) - min(End[0], x)) + (max(End[1], y) - min(End[1], y)) |
|
prio_lettervalue = MAX_PRIO - grid[y][x] |
|
prio_pathlen = (gridX * gridY) - len(visited) |
|
path = PossiblePath(y, x, visited) |
|
q.put((prio_valuediff, prio_distance, path)) |
|
|
|
|
|
def findPath(): |
|
global fewestSteps |
|
global n_solutions |
|
while not q.empty(): |
|
_, _, path = q.get() |
|
|
|
if (path.y, path.x) in point_cost and point_cost[(path.y, path.x)] < len(path.visited): |
|
# We already have a better path to the current point. |
|
continue |
|
|
|
#log_every_n('Inspecting: %dx%d, visited %d points, %d solutions' % (path.x, path.y, len(path.visited), n_solutions)) |
|
visited = list(path.visited) |
|
if (path.y, path.x) in visited: |
|
continue |
|
visited.append((path.y, path.x)) |
|
|
|
if (not (fewestSteps == None)) and (len(visited) - 1 >= fewestSteps): |
|
continue |
|
if [path.x, path.y] == End: |
|
n_solutions += 1 |
|
print('Solution Found! Steps taken:', len(visited) - 1, 'Total Solutions', n_solutions) |
|
fewestSteps = len(visited) - 1 |
|
|
|
continue |
|
|
|
if path.x > 0: |
|
if grid[path.y][path.x - 1] <= grid[path.y][path.x] + 1: |
|
valDiff = grid[path.y][path.x - 1] - grid[path.y][path.x] |
|
MakeCandidate(path.x - 1, path.y, visited, valDiff) |
|
if path.x < gridX: |
|
if grid[path.y][path.x + 1] <= grid[path.y][path.x] + 1: |
|
valDiff = grid[path.y][path.x + 1] - grid[path.y][path.x] |
|
MakeCandidate(path.x + 1, path.y, visited, valDiff) |
|
if path.y > 0: |
|
if grid[path.y - 1][path.x] <= grid[path.y][path.x] + 1: |
|
valDiff = grid[path.y - 1][path.x] - grid[path.y][path.x] |
|
MakeCandidate(path.x, path.y - 1, visited, valDiff) |
|
if path.y < gridY: |
|
if grid[path.y + 1][path.x] <= grid[path.y][path.x] + 1: |
|
valDiff = grid[path.y + 1][path.x] - grid[path.y][path.x] |
|
MakeCandidate(path.x, path.y + 1, visited, valDiff) |
|
|
|
|
|
with open('input12.txt','r') as f: |
|
inp = f.read().splitlines(keepends=False) |
|
|
|
grid = [] |
|
fewestSteps = None |
|
Starts = [] |
|
|
|
|
|
for i in range(len(inp)): |
|
grid.append([]) |
|
for j in range(len(inp[i])): |
|
if inp[i][j] == 'S': |
|
Starts.append([j, i]) |
|
grid[i].append(0) |
|
elif inp[i][j] == 'E': |
|
End = [j, i] |
|
grid[i].append(ord('z') - ord('a')) |
|
else: |
|
if inp[i][j] == 'a': |
|
Starts.append([j, i]) |
|
grid[i].append(ord(inp[i][j])-ord('a')) |
|
|
|
gridX = len(grid[0]) - 1 |
|
gridY = len(grid) - 1 |
|
loopN = 0 |
|
|
|
print('possible starting locations found:', len(Starts)) |
|
|
|
for Start in Starts: |
|
loopN +=1 |
|
print('Checking Location', loopN, 'out of', len(Starts)) |
|
point_cost = {} |
|
_x = Start[0] |
|
_y = Start[1] |
|
if Start[0] > 0: |
|
if grid[_y][_x - 1] <= 1: |
|
MakeCandidate(_x - 1, _y, [(_y, _x)], grid[_y][_x - 1]) |
|
if Start[0] < gridX: |
|
if grid[_y][_x + 1] <= 1: |
|
MakeCandidate(_x + 1, _y, [(_y, _x)], grid[_y][_x + 1]) |
|
if Start[1] > 0: |
|
if grid[_y - 1][_x] <= 1: |
|
MakeCandidate(_x, _y - 1, [(_y, _x)], grid[_y - 1][_x]) |
|
if Start[1] < gridY: |
|
if grid[_y + 1][_x] <= 1: |
|
MakeCandidate(_x, _y + 1, [(_y, _x)], grid[_y + 1][_x]) |
|
|
|
findPath() |
|
|
|
print('The shortest path takes', fewestSteps, 'steps') |
|
#for x in grid: |
|
# tempa = '' |
|
# for y in x: |
|
# tempa += chr(y + 97) |
|
# print(tempa) |
|
|
|
|