#!/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                     """