267 lines
7.5 KiB
Python
267 lines
7.5 KiB
Python
#!/usr/bin/env python3
|
|
|
|
from collections import defaultdict
|
|
|
|
|
|
WALL = '#'
|
|
PATH = '.'
|
|
|
|
A = ("out", "AA")
|
|
Z = ("out", "ZZ")
|
|
|
|
|
|
class WeightedGraph(dict):
|
|
def edges_of(self, a):
|
|
return self[a]
|
|
|
|
def add_edge(self, a, b, w):
|
|
self[a].append((b, w))
|
|
self[b].append((a, w))
|
|
|
|
def add_node(self, a):
|
|
if a not in self:
|
|
self[a] = []
|
|
|
|
def rm_loops(self):
|
|
for a in self.keys():
|
|
for i, (b, w) in enumerate(self[a]):
|
|
if a == b:
|
|
del self[a][i]
|
|
|
|
def min_path(self, a, b):
|
|
weights = dict()
|
|
visited = set()
|
|
|
|
node, w = a, 0
|
|
while node != b:
|
|
for c, edge_w in self.edges_of(node):
|
|
if c in visited:
|
|
continue
|
|
if c in weights and weights[c] <= w + edge_w:
|
|
continue
|
|
weights[c] = w + edge_w
|
|
node, w = min(weights.items() , key=lambda nw: nw[1])
|
|
del weights[node]
|
|
visited.add(node)
|
|
return w
|
|
|
|
def min_paths(self, a):
|
|
weights = dict()
|
|
def aux(a, w):
|
|
if a in weights.keys() and weights[a] <= w:
|
|
return
|
|
|
|
weights[a] = w
|
|
|
|
for b, ab_w in graph[node]:
|
|
best = aux(b, w + w2, best)
|
|
|
|
aux(a, 0, None)
|
|
return weights
|
|
|
|
def copy(self):
|
|
return WeightedGraph({a : [bw for bw in bws]for a, bws in self.items()})
|
|
|
|
|
|
def neighbours(maze, vec):
|
|
x, y = vec
|
|
ns = [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]
|
|
width = max(map(len, maze))
|
|
return filter(lambda vec: 0 <= vec[0] < len(maze) and 0 <= vec[1] < len(maze[x]), ns)
|
|
|
|
def find_full_name(maze, vec):
|
|
x, y = vec
|
|
A = maze[x][y]
|
|
assert A.isalpha()
|
|
for a, b in neighbours(maze, (x, y)):
|
|
B = maze[a][b]
|
|
if B.isalpha():
|
|
return ''.join(sorted(A+B))
|
|
return None
|
|
|
|
def find_node(maze, vec):
|
|
x, y = vec
|
|
width = max(map(len, maze))
|
|
name = find_full_name(maze, (x, y))
|
|
if x < 2 or len(maze) - 2 <= x or y < 2 or width - 2 <= y:
|
|
loc = "out"
|
|
else:
|
|
loc = "in"
|
|
node = (loc, name)
|
|
return node
|
|
|
|
def other_node(packed):
|
|
loc, name = packed
|
|
if loc == "in":
|
|
return ("out", name)
|
|
return ("in", name)
|
|
|
|
def make_graph(maze):
|
|
graph = dict()
|
|
def search(node, vec, w, visited):
|
|
x, y = vec
|
|
if (x, y) in visited:
|
|
return
|
|
visited.append((x, y))
|
|
c = maze[x][y]
|
|
if c.isalpha():
|
|
node2 = find_node(maze, (x, y))
|
|
if node != node2:
|
|
graph[node].append((node2, w-1))
|
|
elif c == PATH:
|
|
for n in neighbours(maze, (x, y)):
|
|
search(node, n, w+1, visited)
|
|
|
|
visited = []
|
|
for x, line in enumerate(maze):
|
|
for y, c in enumerate(line):
|
|
if not c.isalpha():
|
|
continue
|
|
node = find_node(maze, (x, y))
|
|
if node in visited:
|
|
continue
|
|
paths = [(x,y) for (x,y) in neighbours(maze, (x,y)) if maze[x][y] == PATH]
|
|
if paths == []:
|
|
continue
|
|
visited.append(node)
|
|
start = paths[0]
|
|
graph[node] = []
|
|
search(node, start, 0, [])
|
|
graph = WeightedGraph(graph)
|
|
graph.rm_loops()
|
|
return graph
|
|
|
|
def preproc(puzzle_input):
|
|
maze = puzzle_input.split('\n')
|
|
return make_graph(maze)
|
|
|
|
def partI(graph):
|
|
graph = graph.copy()
|
|
for node in graph.keys():
|
|
if node[1] in ["AA", "ZZ"]:
|
|
continue
|
|
graph.add_edge(node, other_node(node), 1)
|
|
return graph.min_path(A, Z)
|
|
|
|
class RecGraph(WeightedGraph):
|
|
def edges_of(self, packed):
|
|
lvl, a = packed
|
|
edges = [((lvl, b), w) for b, w in self[a]]
|
|
|
|
loc, _ = a
|
|
|
|
lvl2 = lvl + (1 if loc == "in" else -1)
|
|
b = other_node(a)
|
|
|
|
if b not in self or lvl2 < 0:
|
|
return edges
|
|
b_edge = (lvl2, b), 1
|
|
if lvl2 < lvl:
|
|
edges = [b_edge] + edges
|
|
else:
|
|
edges.append(b_edge)
|
|
return edges
|
|
|
|
|
|
def partII(graph):
|
|
graph = RecGraph(graph)
|
|
return graph.min_path((0, A), (0, Z))
|
|
|
|
test =""" A
|
|
A
|
|
#######.#########
|
|
#######.........#
|
|
#######.#######.#
|
|
#######.#######.#
|
|
#######.#######.#
|
|
##### B ###.#
|
|
BC...## C ###.#
|
|
##.## ###.#
|
|
##...DE F ###.#
|
|
##### G ###.#
|
|
#########.#####.#
|
|
DE..#######...###.#
|
|
#.#########.###.#
|
|
FG..#########.....#
|
|
###########.#####
|
|
Z
|
|
Z """
|
|
|
|
|
|
test2 = """ A
|
|
A
|
|
#################.#############
|
|
#.#...#...................#.#.#
|
|
#.#.#.###.###.###.#########.#.#
|
|
#.#.#.......#...#.....#.#.#...#
|
|
#.#########.###.#####.#.#.###.#
|
|
#.............#.#.....#.......#
|
|
###.###########.###.#####.#.#.#
|
|
#.....# A C #.#.#.#
|
|
####### S P #####.#
|
|
#.#...# #......VT
|
|
#.#.#.# #.#####
|
|
#...#.# YN....#.#
|
|
#.###.# #####.#
|
|
DI....#.# #.....#
|
|
#####.# #.###.#
|
|
ZZ......# QG....#..AS
|
|
###.### #######
|
|
JO..#.#.# #.....#
|
|
#.#.#.# ###.#.#
|
|
#...#..DI BU....#..LF
|
|
#####.# #.#####
|
|
YN......# VT..#....QG
|
|
#.###.# #.###.#
|
|
#.#...# #.....#
|
|
###.### J L J #.#.###
|
|
#.....# O F P #.#...#
|
|
#.###.#####.#.#####.#####.###.#
|
|
#...#.#.#...#.....#.....#.#...#
|
|
#.#####.###.###.#.#.#########.#
|
|
#...#.#.....#...#.#.#.#.....#.#
|
|
#.###.#####.###.###.#.#.#######
|
|
#.#.........#...#.............#
|
|
#########.###.###.#############
|
|
B J C
|
|
U P P """
|
|
|
|
test3 = """ Z L X W C
|
|
Z P Q B K
|
|
###########.#.#.#.#######.###############
|
|
#...#.......#.#.......#.#.......#.#.#...#
|
|
###.#.#.#.#.#.#.#.###.#.#.#######.#.#.###
|
|
#.#...#.#.#...#.#.#...#...#...#.#.......#
|
|
#.###.#######.###.###.#.###.###.#.#######
|
|
#...#.......#.#...#...#.............#...#
|
|
#.#########.#######.#.#######.#######.###
|
|
#...#.# F R I Z #.#.#.#
|
|
#.###.# D E C H #.#.#.#
|
|
#.#...# #...#.#
|
|
#.###.# #.###.#
|
|
#.#....OA WB..#.#..ZH
|
|
#.###.# #.#.#.#
|
|
CJ......# #.....#
|
|
####### #######
|
|
#.#....CK #......IC
|
|
#.###.# #.###.#
|
|
#.....# #...#.#
|
|
###.### #.#.#.#
|
|
XF....#.# RF..#.#.#
|
|
#####.# #######
|
|
#......CJ NM..#...#
|
|
###.#.# #.###.#
|
|
RE....#.# #......RF
|
|
###.### X X L #.#.#.#
|
|
#.....# F Q P #.#.#.#
|
|
###.###########.###.#######.#########.###
|
|
#.....#...#.....#.......#...#.....#.#...#
|
|
#####.#.###.#######.#######.###.###.#.#.#
|
|
#.......#.......#.#.#.#.#...#...#...#.#.#
|
|
#####.###.#####.#.#.#.#.###.###.#.###.###
|
|
#.......#.....#.#...#...............#...#
|
|
#############.#.#.###.###################
|
|
A O F N
|
|
A A D M """
|
|
|