'''

@author: olivier.massot, 2019
'''
from collections import Counter
import time


class Node():
    def __init__(self, pos, path=[]):
        self.pos = pos
        self.path = path

class PNode():
    def __init__(self, pos, level = 0, parent=None):
        self.pos = pos

class Grid():
    dim = 12
    owned = 3
    def __init__(self):
        
        self.cells = [(x, y) for x in range(Grid.dim) for y in range(Grid.dim)]
        self.hq = (0,0)
        self.owned = []

    def from_graph(self, graph):
        for y, row in enumerate(graph):
            row = list(row)
            for x, c in enumerate(row):
                if c != "-":
                    self.owned.append((x, y))
                if c == "H":
                    self.hq = (x, y)

    def print_grid(self):
        grid = [["" for _ in range(Grid.dim)] for _ in range(Grid.dim)]
        for x, y in self.cells:
            grid[y][x] = f"({x:02d}, {y:02d})" if self._active_owned((x, y), 0) else "________"
        return "\n".join(["".join([c for c in row]) for row in grid])
    
    @staticmethod
    def manhattan(from_, to_):
        xa, ya = from_
        xb, yb = to_
        return abs(xa - xb) + abs(ya - yb) 
    
    def neighbors(self, x, y, diags=False):
        neighs = [(x, y - 1), (x - 1, y), (x + 1, y), (x, y + 1)]
        if diags:
            neighs += [(x - 1, y - 1), (x + 1, y - 1), (x - 1, y + 1), (x + 1, y + 1)]
        return [(x, y) for x, y in neighs if 0 <= x < Grid.dim and 0 <= y < Grid.dim]
        
    def update_frontlines(self, player_id):
        self.frontline = []
        
        for p in self.cells:
            if self._active_owned(p, player_id):
                if any(not self._active_owned(n, player_id) for n in self.neighbors(*p)):
#                     cell.update_threat()
                    self.frontline.append(p)
    
    def _active_owned(self, pos, _):
        return pos in self.owned


    def update_propagation(self, player_id):
        start = self.hq
        lvl = 0
        propagation = {start: (lvl, [])}
        
        pivots = []
        for x, y in self.cells:
            if (x, y) != start and self._active_owned((x, y), player_id):
                
                around = [(x, y - 1), (x + 1, y - 1), (x + 1, y), (x + 1, y + 1),
                             (x, y + 1), (x - 1, y + 1), (x - 1, y), (x - 1, y - 1)]
                owned = [self._active_owned(p, player_id) for p in around]
                changes = [x for x in zip(owned, owned[1:]) if x == (True, False)]
                
                if len(changes) > 1:
                    pivots.append((x, y))
        self.pivots = {p: [] for p in pivots}
        
        buffer = [start]
        while buffer:
            new_buffer = []
            lvl += 1
            for pos in buffer:
                for n in self.neighbors(*pos):
                    if self._active_owned(n, player_id):
                        if not n in propagation:
                            propagation[n] = (lvl, [pos])
                            new_buffer.append(n)
                        else:
                            # already visited
                            if propagation[pos][1] != [n] and propagation[n][0] >= propagation[pos][0]:
                                propagation[n][1].append(pos)
            
            buffer = new_buffer
        
        self.propagation = propagation

        children = {}
        for p, data in self.propagation.items():
            _, parents = data
            for parent in parents:
                if not parent in children:
                    children[parent] = []
                children[parent].append(p)
        print("*", children)
        
        for pivot in self.pivots:
            buffer = set(children[pivot])
            
            while buffer:
                new_buffer = set()
                 
                for child in buffer:
                    new_buffer |= set(children.get(child, []))
               
                self.pivots[pivot] += list(buffer)
                buffer = new_buffer
            
        # cleaning 'false children'
        for pivot, children in self.pivots.items():
            invalid = []
            for child in children:
                parents = self.propagation[child][1]
                if any((p != pivot and p not in children) or p in invalid for p in parents):
                    invalid.append(child)
            for p in invalid:
                children.remove(p)
                
        
        
        
    def update_pivot_for(self, player_id):
#         start = self.get_hq(player_id).pos
        start = self.hq
        start_node = Node(start)
        
        buffer = [start_node]
        nodes = {start_node}
        ignored = [p for p in self.cells if len([n for n in self.neighbors(*p, diags=True) if self._active_owned(n, player_id)]) == 8]
        
        while buffer:
            new_buffer = []
            for node in buffer:
                neighbors = [p for p in self.neighbors(*node.pos) if self._active_owned(p, player_id)]
                if node.pos in ignored:
                    continue
                for n in neighbors:
                    if not n in node.path:
                        new_node = Node(n, node.path + [node.pos])
                        nodes.add(new_node)
                        new_buffer.append(new_node)
            
            buffer = new_buffer
        
        paths_to = {}
        
        for node in nodes:
            if not node.pos in paths_to:
                paths_to[node.pos] = []
            paths_to[node.pos].append(node.path)
#         print(paths_to)
    
        pivots = {}
        
        for candidate in paths_to:
            if candidate == start:
                continue
            for p, paths in paths_to.items():
                if not paths or not paths[0] or p in ignored:
                    continue
                if all(candidate in path for path in paths):
                    if not candidate in pivots:
                        pivots[candidate] = []
                    pivots[candidate].append(p)
        
#         occurrences = Counter(sum(sum(paths_to.values(), []), []))
# 
#         while ignored:
#             new_ignored = []
#             for p in ignored:
#                 occured_neighbors = [occurrences[n] for n in self.neighbors(*p) if n in occurrences]
#                 if not occured_neighbors:
#                     new_ignored.append(p)
#                     continue
#                 occurrences[p] = 2 * sum(occured_neighbors) // len(occured_neighbors)
#             ignored = new_ignored
#         
#         print(occurrences)

        return pivots

grid = Grid()

graph = ["Hxxxx-------",
         "xxxxxx------",
         "xxx-xx------",
         "-x--xx------",
         "xx----------",
         "xxxxxxxxx---",
         "xxxxxxxxx---",
         "xxxxxxxxx---",
         "xxxxxxxxx---",
         "xxxxxxxxx---",
         "xxxxxx------",
         "------------",
         ]
# graph = ["Hxxxx-------",
#          "xxxxxx------",
#          "xxx-xx------",
#          "-x--xx------",
#          "xx----------",
#          "------------",
#          "------------",
#          "------------",
#          "------------",
#          "------------",
#          "------------",
#          "------------",
#          ]

grid.from_graph(graph)

Grid.owned = 5
print(grid.print_grid())
print()

t0 = time.time()
grid.update_propagation(0)
print(grid.propagation)
print(grid.pivots)
print(time.time() - t0)
 
t0 = time.time()
a = grid.update_pivot_for(0)
print(a)
print(time.time() - t0)