cig/cultist_war/main.py

import heapq
import sys
import time

debug = True

t0 = time.time()


def log(*msg):
    if debug:
        print("{} - ".format(str(time.time() - t0)[1:5]), *msg, file=sys.stderr, flush=True)


def time_to(total, step):
    """ number of steps to reach total """
    return total // step + (1 if total % step > 0 else 0)


class BaseClass:
    def __repr__(self):
        return f"<{self.__class__.__name__}: {self.__dict__}>"


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


class PathNode(tuple):
    def __new__(cls, x, y, parent=None):
        n = tuple.__new__(cls, (x, y))
        n.parent = parent
        n.cost = 0
        return n

    def __repr__(self):
        return f"<{self[0]}, {self[1]}, c:{self.cost}>"


class DiscoverNode(tuple):
    def __new__(cls, x, y, ancestors=None):
        n = tuple.__new__(cls, (x, y))
        n.ancestors = ancestors if ancestors is not None else []
        n.cost = 0
        return n

    def __repr__(self):
        return f"<{self[0]}, {self[1]}, c:{self.cost}>"


class Queue(BaseClass):
    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, priority, item):
        while priority in [p for p, _ in self.items]:
            priority += 1
        heapq.heappush(self.items, (priority, item))

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

    def get_items(self):
        return heapq.heappop(self.items)


class Player(BaseClass):
    def __init__(self, id_):
        self.id = id_


ME = Player(int(input()))  # Input gives the player id: 0 plays first
OPPONENT = Player(1 - ME.id)

PLAYERS_INDEX = {p.id: p for p in [ME, OPPONENT]}
PLAYERS_ORDER = sorted([ME, OPPONENT], key=lambda p: p.id)


class Unit(BaseClass):
    TYPE_CULTIST = 0
    TYPE_CULT_LEADER = 1

    OWNER_0 = 0
    OWNER_1 = 1
    NO_OWNER = 2

    SHOOTING_RANGE = 6
    SHOOTING_MAX_DAMAGE = 7

    def __init__(self, id_):
        self.id = id_
        self.hp = 10
        self.x = None
        self.y = None
        self.owner = None

    @property
    def pos(self):
        return self.x, self.y

    @property
    def owned(self):
        return self.owner == ME.id

    @property
    def opponent(self):
        return self.owner == OPPONENT.id

    @property
    def neutral(self):
        return self.owner == self.NO_OWNER


class CultLeader(Unit):
    pass


class Action(BaseClass):
    pass


class ActionWait(Action):
    def __repr__(self):
        return f"<ActionWait>"

    def exec(self):
        print("WAIT")


class ActionMove(Action):
    def __init__(self, unit, pos, message=''):
        self.unit = unit
        self.pos = pos
        self.message = message

    def __repr__(self):
        return f"<ActionMove: {self.unit.id} to {self.pos} ({self.message})>"

    def exec(self):
        print(f"{self.unit.id} MOVE {self.pos[0]} {self.pos[1]}")


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

    def __repr__(self):
        return f"<ActionShoot: {self.unit.id} to {self.target.id}>"

    def exec(self):
        print(f"{self.unit.id} SHOOT {self.target.id}")


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

    def __repr__(self):
        return f"<ActionConvert: {self.unit.id} to {self.target.id}>"

    def exec(self):
        print(f"{self.unit.id} CONVERT {self.target.id}")


class Grid(BaseClass):
    def __init__(self, width, height):
        self.width = width
        self.height = height

        self.cells = []
        self.obstacles = []
        self._neighbors = {}

        self.index = {}
        self.units = {}
        self.round = 0
        self.threat = {}
        self.control = {}
        self.heat_map = {}

    def pre_compute(self):
        self.cells = [(x, y) for x in range(self.width) for y in range(self.height)]

        for x, y in self.cells:
            self._neighbors[(x, y)] = [(xn, yn) for xn, yn in [(x, y - 1), (x - 1, y), (x + 1, y), (x, y + 1)] if
                                      0 <= xn < self.width and 0 <= yn < self.height]

    def reinit_round(self):
        self.units = {}

    def update_unit(self, id_, type_, hp, x, y, owner):
        self.units[id_] = Unit(id_) if type_ != Unit.TYPE_CULT_LEADER else CultLeader(id_)
        unit = self.units[id_]
        unit.hp = hp
        unit.x = x
        unit.y = y
        unit.owner = owner

    def update_threat_map(self):
        self.threat = {(x, y): 0 for x in range(self.width) for y in range(self.height)}

        for u in self.opponent_cultists():
            shooting_zone = self.zone(u.pos, Unit.SHOOTING_RANGE)
            for x, y in shooting_zone:
                dist = shooting_zone[(x, y)]

                if not self.line_of_sight(u.pos, (x, y)):
                    continue

                threat = Unit.SHOOTING_RANGE + 1 - dist
                if threat > self.threat[(x, y)]:
                    self.threat[(x, y)] = threat

    def update_control(self):
        self.control = {(x, y): 0 for x in range(self.width) for y in range(self.height)}

        for u in self.allied_cultists():
            shooting_zone = self.zone(u.pos, Unit.SHOOTING_RANGE)
            for x, y in shooting_zone:
                dist = shooting_zone[(x, y)]

                if not self.line_of_sight(u.pos, (x, y)):
                    continue

                control = Unit.SHOOTING_RANGE + 1 - dist
                if control > self.control[(x, y)]:
                    self.control[(x, y)] = control

    def update_heat_map(self):
        lines = []
        self.heat_map = {(x, y): 0 for x in range(self.width) for y in range(self.height)}

        cult_leader = self.cult_leader()

        for o in self.opponent_cultists():
            if cult_leader:
                lines += self.line(o.pos, cult_leader.pos)

            for n in self.neutrals():
                lines += self.line(o.pos, n.pos)

        for pos in lines:
            self.heat_map[pos] += 1

    def update(self):
        self.index = {}
        for unit in self.units.values():
            self.index[(unit.x, unit.y)] = unit

        self.update_threat_map()
        self.update_control()
        self.update_heat_map()

    def cult_leader(self):
        return next((u for u in self.units.values() if type(u) is CultLeader and u.owned), None)

    def allied_cultists(self):
        return [u for u in self.units.values() if type(u) is not CultLeader and u.owned]

    def opponent_units(self):
        return [u for u in self.units.values() if u.opponent]

    def opponent_cult_leader(self):
        return [u for u in self.units.values() if type(u) is CultLeader and not u.owned]

    def opponent_cultists(self):
        return [u for u in self.units.values() if type(u) is not CultLeader and u.opponent]

    def neutrals(self):
        return [u for u in self.units.values() if u.neutral]

    def list_actions(self):
        actions = Queue()

        k_convert_neutrals = 10
        k_convert_danger = 30
        k_shoot_opponent_cultist = 20
        k_shoot_opponent_cult_leader = 10
        k0_protect_cult_leader = 10
        k0_position = 50
        k_position_distance = 10
        k_position_heat = -5

        cult_leader = self.cult_leader()

        # Conversion des neutres
        if cult_leader:
            paths = self.discover(
                cult_leader.pos,
                key=(lambda pos: pos in self.index and self.index[pos].neutral),
                limit=5
            )
            for path in paths:
                log(path)

            for path in paths:
                target = self.index[path[-1]]

                priority = 0
                priority += k_convert_neutrals * len(path)
                priority += k_convert_danger * sum([self.threat[pos] for pos in path])

                if target in self.neighbors(*cult_leader.pos):
                    action = ActionConvert(cult_leader, target)
                else:
                    action = ActionMove(cult_leader, path[0], f'go convert {target.id}')
                actions.put(priority, action)

        # Attaque d'unités ennemies
        for a in self.allied_cultists():
            for u in self.opponent_cultists():
                shooting_distance = self.shooting_distance(a.pos, u.pos)
                if shooting_distance and shooting_distance < u.SHOOTING_RANGE:
                    action = ActionShoot(a, u)

                    priority = (k_shoot_opponent_cult_leader if type(
                        u) is CultLeader else k_shoot_opponent_cultist) * shooting_distance

                    actions.put(priority, action)

        # Position
        for a in self.allied_cultists():
            # on garde les trois points les plus chauds
            hot_spots = sorted(self.heat_map.items(), key=lambda p: p[1], reverse=True)[:3]

            for pos, heat in hot_spots:
                action = ActionMove(a, pos)

                path = self.path(a.pos, pos)

                safe_path = []
                for step in path:
                    if self.threat[step] > 1:
                        break
                    safe_path.append(step)

                if not safe_path:
                    continue

                priority = k0_position
                priority += k_position_heat * heat
                priority += k_position_distance * len(path)

                actions.put(priority, action)

        # Mise en sécurité du chef
        if cult_leader:
            current_threat = self.threat[cult_leader.pos]
            if current_threat:
                target = min(
                    [n for n in self.neighbors(*cult_leader.pos) if self.can_move_on(n)],
                    key=lambda x: self.threat[x]
                )

                action = ActionMove(cult_leader, target)
                priority = k0_protect_cult_leader

                actions.put(priority, action)

        return actions

    def in_grid(self, pos):
        return 0 <= pos[0] < self.width and 0 <= pos[1] < self.height

    def can_see_trough(self, pos):
        return self.in_grid(pos) and pos not in self.obstacles + list(self.index.values())

    def can_move_on(self, pos):
        return self.in_grid(pos) and pos not in self.obstacles and pos not in self.index

    def can_discover(self, pos):
        return self.in_grid(pos) and pos not in self.obstacles

    def moving_cost(self, pos):
        if not self.can_move_on(pos):
            return -1
        return 1 + self.threat[pos]

    @staticmethod
    def manhattan(from_, to_):
        xa, ya = from_
        xb, yb = to_
        return abs(xa - xb) + abs(ya - yb)

    def neighbors(self, x, y):
        return self._neighbors[(x, y)]

    def zone(self, pos, radius):
        x0, y0 = pos
        zone = {}

        for x in range(max(x0 - radius, 0), min(x0 + radius, self.width)):
            for y in range(max(y0 - radius, 0), min(y0 + radius, self.height)):
                dist = self.manhattan(pos, (x, y))
                if dist <= radius:
                    zone[(x, y)] = dist

        return zone

    @classmethod
    def line(cls, from_, to_):
        """ Implementation of bresenham's algorithm """
        xa, ya = from_
        xb, yb = to_

        if (xa, ya) == (xb, yb):
            return [(xa, ya)]

        # diagonal symmetry
        vertically_oriented = (abs(yb - ya) > abs(xb - xa))
        if vertically_oriented:
            ya, xa, yb, xb = xa, ya, xb, yb

        # horizontal symmetry
        reversed_sym = (xa > xb)
        if reversed_sym:
            xb, yb, xa, ya = xa, ya, xb, yb

        # angle
        dx, dy = xb - xa, yb - ya
        alpha = (abs(dy) / dx)

        offset = 0.0
        step = 1 if dy > 0 else -1

        result = []
        y_ = ya
        for x_ in range(xa, xb + 1):
            result.append((y_, x_) if vertically_oriented else (x_, y_))

            offset += alpha
            if offset > 0.5:
                y_ += step
                offset -= 1.0

        if reversed_sym:
            result.reverse()
        return result

    def line_of_sight(self, from_, to_):
        line = self.line(from_, to_)
        return line if all(self.can_see_trough(c) for c in line) else []

    def shooting_distance(self, from_, to_):
        return len(self.line_of_sight(from_, to_))

    def path(self, start, target):
        nodes = Queue()
        its, break_on = 0, 300

        origin = PathNode(*start)
        nodes.put(0, origin)

        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:
                its += 1
                if its > break_on:
                    log("<!> pathfinding broken")
                    return None

                if (x, y) == current.parent:
                    continue

                if not self.can_move_on((x, y)):
                    continue

                moving_cost = self.moving_cost((x, y))

                cost = current.cost + moving_cost
                priority = cost + 10 * Grid.manhattan((x, y), target)

                node = PathNode(x, y, current)
                node.cost = cost
                nodes.put(priority, node)

        return None

    def discover(self, start, key, limit=5):
        paths = []
        found = []

        nodes = Queue()
        its, break_on = 0, 2000

        origin = DiscoverNode(*start)
        nodes.put(0, origin)

        while nodes:
            current = nodes.get()

            if current not in found and current != start and key(tuple(current)):
                path = []
                previous = current
                while previous.ancestors:
                    if previous != start:
                        path.insert(0, previous)
                    previous = previous.ancestors[-1]
                found.append(path[-1])
                paths.append(path)

                if len(paths) >= limit:
                    return paths

            neighbors = self.neighbors(*current)

            for x, y in neighbors:
                its += 1
                if its > break_on:
                    log("<!> discovering ended earlier than expected")
                    return paths

                if (x, y) in current.ancestors:
                    continue

                if not self.can_discover((x, y)):
                    continue

                moving_cost = self.moving_cost((x, y))

                cost = current.cost + moving_cost
                priority = cost + Grid.manhattan((x, y), start)

                ancestors = current.ancestors + [current]

                node = DiscoverNode(x, y, ancestors)
                node.cost = cost
                nodes.put(priority, node)

        return paths

    def _repr_cell(self, pos):
        # return f"{self.control[pos]}/{self.threat[pos]}"
        # return self.heat_map[pos]

        if pos in self.obstacles:
            return "X"

        unit = self.index.get(pos, None)
        if type(unit) is CultLeader:
            return "C"
        elif unit is None:
            return "."
        else:
            return "U"

    def graph(self):
        return "\n".join(
            ["|".join([str(self._repr_cell((x, y))) for x in range(self.width)]) for y in range(self.height)])


# Create grid
GRID = Grid(*[int(i) for i in input().split()])
obstacles_input = [input() for y in range(GRID.height)]
GRID.obstacles = [(x, y) for y, row in enumerate(obstacles_input) for x, val in enumerate(row) if val == 'x']

GRID.pre_compute()

while 1:
    # TODO: prendre en compte le terrain dans la ligne de visée et les déplacements
    log(f"start round {GRID.round}")

    GRID.reinit_round()
    for _ in range(int(input())):
        GRID.update_unit(*[int(j) for j in input().split()])
    GRID.update()

    actions = GRID.list_actions()

    for action in actions.items:
        log(f"* {action}")

    # print("\n" + GRID.graph(), file=sys.stderr)

    try:
        action = actions.get()
    except IndexError:
        log("no action...")
        action = ActionWait()

    log(f"exec : {action}")

    action.exec()
    GRID.round += 1