'''

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


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

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)]

    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}, {y})" 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 oriented_neighbors(self, x, y, orient):
        return [(x + 1, y), (x, y + 1)] if orient > 0 else [(x - 1, y), (x, y - 1)]
    
    def update_frontlines(self):
        self.frontline = []
        
        for p in self.cells:
            if self._active_owned(p, 0):
                if any(not self._active_owned(n, 0) for n in self.neighbors(*p)):
#                     cell.update_threat()
                    self.frontline.append(p)
    
    def _active_owned(self, pos, player_id):
        return pos in [(0,0), (1,0), (2,0), (3,0), (4, 0),
                       (0,1), (1,1), (2,1), 
                       (0,2), (1,2), (2,2), 
                       (0,3), (1,3), (2,3), 
                                     (2,4), 
                              (1,5), (2,5),
                              (1,6), (2,6),
                              (1,7), (2,7),
                              (1,8), (2,8)]
        
    def __active_owned(self, pos, player_id):
        return pos[0] < 12 and pos[1] < 12

    def update_pivot_for(self, player_id):
#         start = self.get_hq(player_id).pos
        start = (0,0)
        orient = 1 if start == (0, 0) else -1
        start_node = Node(start)
        
        buffer = [start_node]
        nodes = {start_node}
        ignored = set()
        
        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 len(neighbors) == 4:
                    ignored.add(node.pos)
                    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 = set()
            for p in ignored:
                occured_neighbors = [occurrences[n] for n in self.neighbors(*p) if n in occurrences]
                if not occured_neighbors:
                    new_ignored.add[p]
                    continue
                occurrences[p] = 2 * sum(occured_neighbors) // len(occured_neighbors)
            ignored = new_ignored
        
        print(occurrences)

        return pivots


    def __update_pivot_for(self, player_id):
#         start = self.get_hq(player_id).pos
        start = (0,0)
        orient = 1
        buffer = [(None, start)]
        bounds = []
        
        while buffer:
            new_buffer = []
            for o, p in buffer:
                for n in self.oriented_neighbors(*p, orient):
                    if self._active_owned(n, player_id) and not (p, n) in bounds and n != o:
                        bounds.append((p, n))
                        new_buffer.append((p, n))
            buffer = new_buffer
        
        print(bounds)
        
        parents_number = Counter()
        for parent, child in bounds:
            parents_number[child] += 1
        print(parents_number)
            

        pivots = set()
        for parent, child in bounds:
            if parent == start:
                continue
            if parents_number[child] == 1:
                pivots |= {parent}
                
        
        return pivots
    
grid = Grid()
Grid.owned = 5
print(grid.print_grid())

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