Hypersonic Draft

import heapq
from queue import PriorityQueue
import sys

sys.setrecursionlimit(20000)


def eprint(msg):
    return
    print(msg, file=sys.stderr, flush=True)


def iprint(msg):
    # return
    print(msg, file=sys.stderr, flush=True)


PLAYER = 0
BOMB = 1
OBJECT = 2
XTRARANGE = 1
XTRABOMB = 2
COUNTDOWN = 8


class Action:
    def __init__(self, type, target):
        self.type = type
        self.target = target

    def __repr__(self):
        return "{} {}".format(self.type, self.target)


class Pos(object):
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def distance(self, other):
        return abs(self.x - other.x) + abs(self.y - other.y)

    # fonction pour transformer les coordonnées d'une cellule pour pouvoir utiliser l'algorithme AStar
    def transpose(self):
        return self.x, game.grid.height - 1 - self.y

    def __repr__(self):
        return f'{self.x} {self.y}'


class Cell(Pos):
    def __init__(self, x, y, reachable=True, value=None):
        """Initialize new cell.

        @param reachable is cell reachable? not a wall?
        @param x cell x coordinate
        @param y cell y coordinate
        @param g cost to move from the starting cell to this cell.
        @param h estimation of the cost to move from this cell
                 to the ending cell.
        @param f f = g + h
        """
        super().__init__(x, y)
        self.value = value
        self.reachable = reachable
        self.x = x
        self.y = y
        self.parent = None
        self.g = 0
        self.h = 0
        self.f = 0

    def update(self, value, bombs):
        self.value = value
        if value in ['X', '0', '1', '2'] or self in bombs:
            self.reachable = False

    def is_safe_from(self, bomb):
        if self.x == bomb.x:
            if self.distance(bomb) > bomb.range:
                return True
            else:
                y_range = range(bomb.y, self.y + 1) if bomb.y < self.y else range(bomb.y, self.y - 1, -1)
                for y in y_range:
                    c = game.grid.get_cell(self.x, y)
                    if not c.reachable:
                        return True
        elif self.y == bomb.y:
            if self.distance(bomb) > bomb.range:
                return True
            else:
                x_range = range(bomb.x, self.x + 1) if bomb.x < self.x else range(bomb.x, self.x - 1, -1)
                for x in x_range:
                    c = game.grid.get_cell(x, self.y)
                    if not c.reachable:
                        return True
        return False

    def __hash__(self):
        return hash((self.x, self.y))

    def __lt__(self, other):
        return self.f < other.f


class AStar(object):
    def __init__(self):
        # open list
        self.opened = []
        heapq.heapify(self.opened)
        # visited cells list
        self.closed = set()
        # grid cells
        self.cells = []
        self.grid_height = None
        self.grid_width = None

    def init_grid(self, width, height, walls, start, end):
        """Prepare grid cells, walls.
        @param width grid's width.
        @param height grid's height.
        @param walls list of wall x,y tuples.
        @param start grid starting point x,y tuple.
        @param end grid ending point x,y tuple.
        """
        self.grid_height = height
        self.grid_width = width
        for x in range(self.grid_width):
            for y in range(self.grid_height):
                if (x, y) in walls:
                    reachable = False
                else:
                    reachable = True
                self.cells.append(Cell(x, y, reachable))
        self.start = self.get_cell(*start)
        self.end = self.get_cell(*end)

    def get_heuristic(self, cell):
        """Compute the heuristic value H for a cell.

        Distance between this cell and the ending cell multiply by 10.

        @returns heuristic value H
        """
        return 10 * (abs(cell.x - self.end.x) + abs(cell.y - self.end.y))

    def get_cell(self, x, y):
        """Returns a cell from the cells list.

        @param x cell x coordinate
        @param y cell y coordinate
        @returns cell
        """
        return self.cells[x * self.grid_height + y]

    def get_adjacent_cells(self, cell):
        """Returns adjacent cells to a cell.

        Clockwise starting from the one on the right.

        @param cell get adjacent cells for this cell
        @returns adjacent cells list.
        """
        cells = []
        if cell.x < self.grid_width - 1:
            cells.append(self.get_cell(cell.x + 1, cell.y))
        if cell.y > 0:
            cells.append(self.get_cell(cell.x, cell.y - 1))
        if cell.x > 0:
            cells.append(self.get_cell(cell.x - 1, cell.y))
        if cell.y < self.grid_height - 1:
            cells.append(self.get_cell(cell.x, cell.y + 1))
        return cells

    def get_path(self):
        cell = self.end
        path = [(cell.x, cell.y)]
        while cell.parent and cell.parent is not self.start:
            cell = cell.parent
            path.append((cell.x, cell.y))

        path.append((self.start.x, self.start.y))
        path.reverse()
        return path

    def update_cell(self, adj, cell):
        """Update adjacent cell.

        @param adj adjacent cell to current cell
        @param cell current cell being processed
        """
        adj.g = cell.g + 10
        adj.h = self.get_heuristic(adj)
        adj.parent = cell
        adj.f = adj.h + adj.g

    def solve(self):
        """Solve maze, find path to ending cell.

        @returns path or None if not found.
        """
        # add starting cell to open heap queue
        heapq.heappush(self.opened, (self.start.f, self.start))
        while len(self.opened):
            # pop cell from heap queue
            f, cell = heapq.heappop(self.opened)
            # add cell to closed list so we don't process it twice
            self.closed.add(cell)
            # if ending cell, return found path
            if cell is self.end:
                return self.get_path()
            # get adjacent cells for cell
            adj_cells = self.get_adjacent_cells(cell)
            for adj_cell in adj_cells:
                if adj_cell.reachable and adj_cell not in self.closed:
                    if (adj_cell.f, adj_cell) in self.opened:
                        # if adj cell in open list, check if current path is
                        # better than the one previously found
                        # for this adj cell.
                        if adj_cell.g > cell.g + 10:
                            self.update_cell(adj_cell, cell)
                    else:
                        self.update_cell(adj_cell, cell)
                        # add adj cell to open list
                        heapq.heappush(self.opened, (adj_cell.f, adj_cell))

    # Similitude transformation: Translate X Axis (- height) * X-Axis symmetry
    def transpose(self, cells):
        return [(c.x, self.height - 1 - c.y) for c in cells]


#######################@


class Player(Pos):
    def __init__(self, id, x, y, remaining_bombs, bombs_range):
        super().__init__(x, y)
        self.id = id
        self.remaining_bombs = remaining_bombs
        self.bombs_range = bombs_range

    def boxes_in_range(self, bomb_range):
        damage = 0
        boxes = ['0', '1', '2']
        for r in range(1, bomb_range):
            x1, x2, y1, y2 = self.x + r, self.x - r, self.y + r, self.y - r
            if 0 < x1 < self.grid.width and self.grid.get_cell(x1, self.y).value in boxes:
                damage += 1
            if 0 < x2 < self.grid.width and self.grid.get_cell(x2, self.y).value in boxes:
                damage += 1
            if 0 < y1 < self.grid.height and self.grid.get_cell(self.x, y1).value in boxes:
                damage += 1
            if 0 < y2 < self.grid.height and self.grid.get_cell(self.x, y2).value in boxes:
                damage += 1
        return damage

    def __str__(self):
        return "Player id {} ({},{}) -> remaining_bombs: {}, bombs_range: {}".format(self.id, self.x, self.y,
                                                                                     self.remaining_bombs,
                                                                                     self.bombs_range)


class Bomb(Pos):
    def __init__(self, owner_id, x, y, countdown, brange):
        super().__init__(x, y)
        self.owner_id = owner_id
        self.countdown = countdown
        self.range = brange

    def __str__(self):
        return "Bomb owner_id {} ({},{}) -> countdown: {}, range: {}".format(self.owner_id, self.x, self.y,
                                                                             self.countdown, self.range)


class Object(Pos):
    def __init__(self, x, y, type):
        super().__init__(x, y)
        self.type = type

    def __str__(self):
        type_name = "Extra Range +1 Bomb" if self.type == 1 else "Extra Bomb"
        return "Object ({},{}) -> type: {}".format(self.owner_id, self.x, self.y, self.type_name)


class Grid:
    def __init__(self, width=None, height=None):
        self.cells = []
        self.walls = []
        self.width, self.height = width, height

    def init(self, w, h):
        self.width, self.height = w, h
        for y in range(h):
            for x in range(w):
                self.cells.append(Cell(x, y, reachable=True, value='.'))

    def get_cell(self, x, y):
        if self.width > x >= 0 and self.height > y >= 0:
            return self.cells[x + self.width * y]
        return None


class Game:
    def __init__(self):
        self.bombs = []
        self.players = []
        self.objects = []
        self.grid = Grid()
        self.me, self.my_id = None, None
        self.reachable_cells = []

    def init(self):
        line = input()
        iprint(line)
        width, height, self.my_id = [int(i) for i in line.split()]
        self.grid.init(width, height)

    def reset(self):
        self.bombs.clear()
        self.objects.clear()
        self.reachable_cells.clear()

    def update(self):
        grid_input = []
        for i in range(self.grid.height):
            line = input()
            iprint(line)
            grid_input.append([c for c in line])

        entities = int(input())
        iprint(entities)
        for i in range(entities):
            line = input()
            iprint(line)
            entity_type, owner, x, y, param_1, param_2 = [int(j) for j in line.split()]
            if entity_type == PLAYER:
                self.players.append(Player(owner, x, y, remaining_bombs=param_1, bombs_range=param_2))
            elif entity_type == BOMB:
                self.bombs.append(Bomb(owner, x, y, countdown=param_1, brange=param_2))
            else:
                self.objects.append(Object(x, y, type=param_1))

        self.me = [p for p in self.players if p.id == self.my_id][0]

        for y in range(self.grid.height):
            for x in range(self.grid.width):
                value = grid_input[y][x]
                cell = self.grid.get_cell(x, y)
                cell.update(value, self.bombs)
                if not cell.reachable:
                    self.grid.walls.append((cell.x, cell.y))
        # print()

    def getDijkstraPath(self, source, target):
        # constitution du meilleur chemin pour se rendre vers le point cible
        pf = AStar()
        pf.init_grid(self.grid.width, self.grid.height, self.transpose(self.grid.walls), source.transpose(),
                     target.transpose())
        path = pf.solve()
        # print("Calcul chemin de  {} vers {} : {}".format(fromCell, destCell, path), file=sys.stderr)
        return self.transpose(path) if path else None

    # Similitude transformation: Translate X Axis (- height) * X-Axis symmetry
    def transpose(self, cells):
        return [(c[0], self.grid.height - 1 - c[1]) for c in cells]

    def get_adjacent_cells(self, cell):
        return [c for c in self.grid.cells if c.distance(cell) == 1 and c.value == '.']

    def dfs(self, graph, start, goal):
        visited = []
        path = []
        fringe = PriorityQueue()
        fringe.put((0, start, path, visited))

        while not fringe.empty():
            depth, current_node, path, visited = fringe.get()

            if current_node == goal:
                return path + [current_node]

            visited = visited + [current_node]

            child_nodes = graph[current_node]
            for node in child_nodes:
                if node not in visited:
                    if node == goal:
                        return path + [node]
                    depth_of_node = len(path)
                    fringe.put((-depth_of_node, node, path + [node], visited))
        return path

    def dfs_recursive(self, graph, start, goal, path=None):
        if path is None:
            path = [start]
        if start == goal:
            # yield path
            return path
        for neighbour in graph.get(start, [])[::-1]:
            if neighbour not in path:
                # yield from dfs_recursive(graph, neighbour, goal, path + [neighbour])
                self.dfs_recursive(graph, neighbour, goal, path + [neighbour])
        return []

    '''Evaluate damage of bomb b to boxes'''

    def bomb_damage(self, b):
        damage = 0
        boxes = ['0', '1', '2']
        for r in range(1, b.range):
            x1, x2, y1, y2 = b.x + r, b.x - r, b.y + r, b.y - r
            if 0 < x1 < self.grid.width and self.grid.get_cell(x1, b.y).value in boxes:
                damage += 1
            if 0 < x2 < self.grid.width and self.grid.get_cell(x2, b.y).value in boxes:
                damage += 1
            if 0 < y1 < self.grid.height and self.grid.get_cell(b.x, y1).value in boxes:
                damage += 1
            if 0 < y2 < self.grid.height and self.grid.get_cell(b.x, y2).value in boxes:
                damage += 1
        return damage


    ### TODO Predict explosions in chains
    def eval(self, action):
        score = 0
        my_pos = self.grid.get_cell(self.me.x, self.me.y)
        if action.type == 'BOMB':
            new_bomb = Bomb(self.me.id, self.me.x, self.me.y, COUNTDOWN, self.me.bombs_range)
            score = score - 1000 if not action.target.is_safe_from(new_bomb) else score
        else:  # MOVE
            reachable_cells = [my_pos] + [c for c, d in self.reachable_cells if c != action.target]
            new_bomb = Bomb(self.me.id, action.target.x, action.target.y, COUNTDOWN, self.me.bombs_range)
            score += len([c for c in reachable_cells if c.is_safe_from(new_bomb)])  # count of reachable cells to move away
            path = self.getDijkstraPath(self.me, action.target)
            score += 2 * len([o for o in self.objects if o in path and o.type in [1, 2]])
        score += self.bomb_damage(new_bomb)
        return score

    def build_output(self):
        edges_list = [*self.grid.cells]
        graph = {}
        while edges_list:
            edge = edges_list.pop(0)
            graph[edge] = set(self.get_adjacent_cells(edge))

        # Keep a list of reachable cells and distances
        # reachable_cells = [c for c in game.grid.cells if game.dfs(graph, my_pos, c)]
        my_pos = game.grid.get_cell(self.me.x, self.me.y)
        for c in self.grid.cells:
            if c != my_pos:
                path = self.getDijkstraPath(my_pos, c)
                if path is not None:
                    self.reachable_cells.append((c, len(path)))

        actions_candidates = []
        # Keep a list of bomb positions and damages
        actions = ['BOMB', 'MOVE'] if game.me.remaining_bombs else ['MOVE']
        for c, distance in self.reachable_cells:
            actions_candidates += [(Action(action, c), distance) for action in actions]
        actions_score = [(action, distance, game.eval(action)) for action, distance in actions_candidates]
        best_score = max(actions_score, key=lambda a: a[2])[2]
        best_actions = [(action, distance) for action, distance, score in actions_score if score == best_score]
        self.action = min(best_actions, key=lambda a: a[1])[0]

    def output(self):
        print(self.action)

    def debug(self):
        for p in self.players:
            eprint(p)
        eprint(self.grid)


game = Game()

game.init()
# game loop
while True:
    game.reset()
    game.update()
    game.build_output()
    game.output()