codeingame/optimization/cig.py

import heapq
import sys


def log(*msg):
    print(*msg, file=sys.stderr)

class Queue():
    def __init__(self):
        self.items = []
    
    def __bool__(self):
        return bool(self.items)

    def __repr__(self):
        return str(self.items)

    def values(self):
        return (v for _, v in self.items)

    def put(self, item, priority):
        heapq.heappush(self.items, (priority, item))

    def fput(self, item, priority):
        while priority in [p for p, _ in self.items]:
            priority += 1
        self.put(item, priority)

    def get(self):
        return heapq.heappop(self.items)[1]

class PathNode(tuple):
    def __new__(self, x, y, parent=None):
        n = tuple.__new__(self, (x, y))
        n.parent = parent
        n.cost = 0
        return n
    
    def __repr__(self):
        return f"<{self[0]}, {self[1]}, c:{self.cost}>"

h, w, n = [int(input()) for _ in range(3)]
log("INIT: ", h, w, n)

LEFT = "E"
RIGHT = "A"
DOWN = "D"
UP = "C"
STAY = "B"
ACTIONS = [LEFT, RIGHT, DOWN, UP, STAY]
MOVES = [UP, RIGHT, DOWN, LEFT] # WARNING: order matters here

class Grid():
    UNKNOWN = 0
    WALL = 1
    GROUND = 2
    
    VECT = {UP: (0,-1), RIGHT: (1,0), DOWN: (0,1), LEFT: (-1,0)}
    INV = {UP: DOWN, RIGHT: LEFT, LEFT: RIGHT, DOWN: UP, STAY: STAY}
    
    def __init__(self, w, h):
        self.w = w
        self.h = h
        self.cells = {(x, y): Grid.UNKNOWN for x in range(self.w) for y in range(self.h)}
        self.player = []
        self.ghosts = []
        self.deadends = []
        
    def update(self, player, ghosts, available_moves):
        self.player = player
        self.ghosts = ghosts
        self.available_moves = available_moves
        
        for p in [self.player] + self.ghosts:
            self.cells[p] = Grid.GROUND
            
        for m in MOVES:
            p = grid.pos_after(self.player, m)
            self.cells[p] = Grid.GROUND if m in available_moves else Grid.WALL

        self.propagate()


    def _repr_cell(self, p):
        if p == self.player:
            return "P"
        elif p in self.ghosts:
            return "G"
        elif self.cells[p] == Grid.WALL:
            return "x"
        elif self.cells[p] == Grid.GROUND:
            return "_"
        else:
            return "."
        
    def graph(self):
        return "\n".join(["".join([self._repr_cell((x, y)) for x in range(self.w)]) for y in range(self.h) if abs(y - self.player[1]) < 15])

    def set_visited(self, p):
        self.cells[p] = Grid.GROUND
        
    def set_wall(self, p):
        self.cells[p] = Grid.WALL

    @staticmethod
    def pos_after(current, move):
        x, y = current
        dx, dy = Grid.VECT[move]
        return x + dx, y + dy

    @staticmethod
    def dist(p1, p2):
        xa, ya = p1
        xb, yb = p2
        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 < self.w and 0 <= y < self.h]

    def path(self, start, target):
        nodes = Queue()
        origin = PathNode(*start)
        nodes.put(origin, 0)
        neighbors = []

        while nodes:
            current = nodes.get()
            
            if current == target:
                path = []
                previous = current
                while previous:
                    if previous != start:
                        path.insert(0, previous)
                    previous = previous.parent
                return path

            neighbors = self.neighbors(*current)

            for x, y in neighbors:
                if (x, y) == current.parent:
                    continue
                
                if self.cells[(x, y)] == Grid.WALL:
                    continue

                cost = current.cost + 1
                priority = cost + Grid.dist((x, y), target)
                
                node = PathNode(x, y, current)
                node.cost = cost
                nodes.put(node, priority)
                
        return None

    def propagate(self):
        self.propagation = {}
        for m in self.available_moves:
            self.propagation[m] = 0
            visited= set()
            start = self.pos_after(self.player, m)
            
            buffer = [start]
            visited |= set(buffer)
            
            while buffer:
                new_buffer = []
                if any(p in self.ghosts for p in buffer):
                    break
                for p in buffer:
                    for n in self.neighbors(*p):
                        if not n in visited and \
                           not n in new_buffer and \
                           not n == self.player and \
                           not self.cells[n] == Grid.WALL:
                            new_buffer.append(n)
                            visited.add(n)
                            self.propagation[m] += 2 if self.cells[n] == Grid.UNKNOWN else 1
                buffer = new_buffer
            
grid = Grid(w, h)
turn = 0
previous = STAY

while True:
    turn += 1
    available_moves = [m for m in MOVES if input() == "_"]
    log(available_moves)
    
    l = [tuple([int(j) for j in input().split()]) for _ in range(n)]
    *ghosts, player= l
    grid.update(player, ghosts, available_moves)
    log(player, ghosts)
    
    log(grid.graph())
    log(grid.propagation)
    
    q = Queue()
    for m in available_moves:
        visited = 20*(m == grid.INV[previous])
        
        danger = sum([grid.dist(grid.pos_after(player, m), e) for e in ghosts])
        danger = 100 * danger // (len(ghosts) * (w + h))
        
        perspective = grid.propagation[m]
        perspective = 100 * perspective // (max(grid.propagation.values()) or 1)
        
        interest = visited - danger - perspective
        
        log(m, visited, danger, perspective, interest)
        q.fput(m, interest)
        
    move = q.get()
    previous = move
    print(move)