cig/i_n_f/test_pivot.py

'''

@author: olivier.massot, 2019
'''
from collections import Counter
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: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 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 [(11,11), (10,11), (9,11), (8,11), (7,11), (6,11), (5,11), (4,11),
                       (11,10), (10,10), (9,10), (8,10), (7,10), (6,10), (5,10), (4,10),
                       (11,9),  (10,9),  (9,9),  (8,9),  (7,9),  (6,9),  (5,9),
                                                         (7,8),  (6,8),  (5,8),  (4,8),
                                                         (7,7),                  (4,7)]
        
    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 = (11,11)
        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


    def __update_pivot_for(self, player_id):
#         start = self.get_hq(player_id).pos
        start = (11,11)
        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())
print()

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