| 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960 |
- from queue import PriorityQueue
- DIRECTIONS = [(0, 1), (0, -1), (1, 0), (-1, 0)]
- grid = [[c for c in line.strip()] for line in open("12.input")]
- starts = []
- for y, line in enumerate(grid):
- for x, c in enumerate(line):
- if c == 'S':
- start = (x, y)
- grid[y][x] = 'a'
- elif c == 'E':
- end = (x, y)
- grid[y][x] = 'z'
- elif c == 'a':
- starts.append((x, y))
- size = (len(grid[0]), len(grid))
- def nxt(pos):
- x, y = pos
- locs = []
- for (dx, dy) in DIRECTIONS:
- if 0 <= x + dx and x + dx < size[0]:
- if 0 <= y + dy and y + dy < size[1]:
- if ord(grid[y + dy][x + dx]) - ord(grid[y][x]) <= 1:
- locs.append((x + dx, y + dy))
- return locs
- def search(grid, start, end):
- dists = {}
- dists[start] = 0
- queue = PriorityQueue()
- queue.put((0, start))
- while not queue.empty():
- _, current = queue.get()
- dist = dists[current]
- if current == end:
- return dist
- for loc in nxt(current):
- old_dist = dists.get(loc, 1000000)
- if dist + 1 < old_dist:
- dists[loc] = dist + 1
- queue.put((dists[loc], loc))
- return 10000000
- # Part 1
- print(search(grid, start, end))
- # Part 2, disgusting brute force. Could be done faster by inverting the
- # neighbour condition and searching from 'end' to any of the positions in
- # 'starts'.
- print(min(search(grid, start, end) for start in starts))
|
