cig/fall2022/fall2022.py

import heapq
import sys
import time

debug = True

t0 = time.time()


# Debugger : il y a des mouvements qui ne se font pas, faut tout vérifier
# Faire des zones à l'intérieur des contigs, pour attirer le mouvement vers les zones à coloniser
# Limiter les constructions agressives en fonction de ces zones
# penser les recycleurs comme des obstacles!
# Identifier le moment où la situation est "verrouillée" (plus d'accès entre alliés et ennemis)
#     et cesser les construction de recycleurs
# Limiter la consommation de ressources des mouvements
# si la tension autour d'une case est trop forte et que cette case est un "noeud" question passage,
#     ne pas bouger et défendre!


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


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


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 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 Player(BaseClass):
    ME = 1
    OPPONENT = 0
    NONE = -1

    SIDE_WEST = -1
    SIDE_EAST = 1

    def __init__(self, id_):
        self.id = id_
        self.matter = 0
        self.territory = 0

        self.side = None


class Cell(BaseClass):
    def __init__(self, x, y):
        self.x = x
        self.y = y

        self.amount = 0
        self.owner = Player.NONE
        self.units = 0
        self.recycler = False

        self.can_build = False
        self.can_spawn = False
        self.in_range_of_recycler = False

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

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

    @property
    def is_opponents(self):
        return self.owner == Player.OPPONENT

    @property
    def is_neutral(self):
        return self.owner == Player.NONE

    @property
    def is_grass(self):
        return self.amount == 0

    @property
    def is_movable(self):
        return not self.is_grass and not self.recycler

    @property
    def lifetime(self):
        return 10000 if not self.in_range_of_recycler else self.amount

    @property
    def unmovable_next_round(self):
        return self.amount == 1 and self.in_range_of_recycler

    def update(self, scrap_amount, owner, units, recycler, can_build, can_spawn, in_range_of_recycler):
        self.amount = scrap_amount
        self.owner = owner
        self.units = units
        self.recycler = recycler
        self.can_build = can_build
        self.can_spawn = can_spawn
        self.in_range_of_recycler = in_range_of_recycler


class RobotGroup(BaseClass):
    COST = 10

    def __init__(self, x, y, owner, amount, initial_amount=None):
        self.x = x
        self.y = y
        self.owner = owner
        self.amount = amount
        self.initial_amount = initial_amount if initial_amount is not None else amount

        self.amount_played = 0

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

    @pos.setter
    def pos(self, pos):
        self.x, self.y = pos

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

    @property
    def has_played(self):
        return self.amount_played >= self.initial_amount


class Recycler(BaseClass):
    COST = 10

    def __init__(self, x, y, owner, area):
        self.x = x
        self.y = y
        self.owner = owner
        self.area = area

    @property
    def total_available_amount(self):
        return sum(cell.amount for cell in self.area)

    @property
    def immediately_available_amount(self):
        return sum((cell.amount > 0) for cell in self.area)

    def lifetime(self):
        return min(cell.amount for cell in self.area)

    def __repr__(self):
        return f"<{self.__class__.__name__}: ({self.x}, {self.y}), {self.owner}, " \
               f"{self.immediately_available_amount}, {self.total_available_amount}, {self.lifetime()}>"


class Contig(BaseClass):
    UNKNOWN = 'U'
    OWNED = 'O'
    PARTIALLY_OWNED = 'P'
    CONFLICTUAL = 'C'
    NOT_OWNED = 'N'

    def __init__(self, start):
        self.start = start
        self.area = [start]
        self.status = Contig.UNKNOWN
        self.has_robots = False

    def __repr__(self):
        return f"<Contig(start: {self.start}, size: {len(self.area)}, status: {self.status}, robots: {self.has_robots})>"


class MoveOrder(BaseClass):
    def __init__(self, pos, amount, priority):
        self.pos = pos
        self.amount = amount
        self.priority = priority

        self.affected = 0

    @property
    def fulfilled(self):
        return self.affected >= self.amount


class MoveOrderCandidate(BaseClass):
    def __init__(self, order, unit, destination):
        self.order = order
        self.unit = unit
        self.destination = destination


class Action(BaseClass):
    pass


class Wait(Action):
    @staticmethod
    def do():
        return "WAIT"


class Move(Action):
    def __init__(self, from_, to, amount, priority):
        self.from_ = from_
        self.to = to
        self.amount = amount
        self.priority = priority

    def do(self):
        x0, y0 = self.from_
        x1, y1 = self.to
        return f'MOVE {self.amount} {x0} {y0} {x1} {y1}'


class Build(Action):
    COST = 10
    SUPPORT = 'S'
    AGGRESSIVE = 'A'

    def __init__(self, pos, destination, priority):
        self.pos = pos
        self.priority = priority
        self.destination = destination

    def do(self):
        x, y = self.pos
        return f'BUILD {x} {y}'


class Spawn(Action):
    COST = 10

    def __init__(self, pos, amount, priority):
        self.pos = pos
        self.amount = amount
        self.priority = priority

    def do(self):
        x, y = self.pos
        return f'SPAWN {self.amount} {x} {y}'


class Grid(BaseClass):
    def __init__(self, width, height, me, opponent):
        self.width = width
        self.height = height
        self.cells = {(x, y): Cell(x, y) for x in range(width) for y in range(height)}

        self.round = 0

        self.me = me
        self.opponent = opponent

        self.units = {}
        self.recyclers = {}
        self.contigs = []
        self._neighbors_cache = {}
        self._distance_cache = {}
        self.index_contigs = {}
        self.index_tensions = {}
        self.index_threats = {}
        self.index_nearest_enemy = {}

        self.path_cache = {}

    @property
    def grid(self):
        return [[self.cells[(x, y)] for x in range(self.width)] for y in range(self.height)]

    def print(self, key=None):
        if key is None:
            key = lambda x: x
        log("\n" + "\n".join(["".join([f"{key(c)}|" for c in row]) for row in self.grid]))

    def manhattan(self, from_, to_):
        if (from_, to_) in self._distance_cache:
            return self._distance_cache[(from_, to_)]

        xa, ya = from_
        xb, yb = to_
        dist = abs(xa - xb) + abs(ya - yb)
        self._distance_cache[(from_, to_)] = dist
        self._distance_cache[(to_, from_)] = dist
        return dist

    def neighbors(self, x, y, diags=False):
        # if (x, y, diags) in self._neighbors_cache:
        #     return self._neighbors_cache[(x, y, diags)]

        n = [(x, y - 1), (x - 1, y), (x + 1, y), (x, y + 1)]
        if diags:
            n += [(x - 1, y - 1), (x + 1, y - 1), (x - 1, y + 1), (x + 1, y + 1)]

        neighbors = [
            (x, y)
            for x, y in n
            if 0 <= x < self.width and 0 <= y < self.height
        ]
        # self._neighbors_cache[(x, y, diags)] = neighbors
        return neighbors

    @staticmethod
    def create():
        me = Player(Player.ME)
        opponent = Player(Player.OPPONENT)
        w, h = [int(i) for i in input().split()]
        return Grid(w, h, me, opponent)

    def update(self):
        self.round += 1
        my_matter, opp_matter = [int(i) for i in input().split()]

        self.me.matter = my_matter
        self.opponent.matter = opp_matter

        for y in range(self.height):
            for x in range(self.width):
                scrap_amount, owner, units, recycler, can_build, can_spawn, in_range_of_recycler = [int(k) for k in
                                                                                                    input().split()]
                self.cells[(x, y)].update(scrap_amount, owner, units, recycler, can_build, can_spawn,
                                          in_range_of_recycler)

                if owner == Player.ME and self.me.side is None:
                    self.me.side = Player.SIDE_WEST if x <= (self.width // 2) else Player.SIDE_EAST
                if owner == Player.OPPONENT and self.opponent.side is None:
                    self.opponent.side = Player.SIDE_WEST if x <= (self.width // 2) else Player.SIDE_EAST

        log('update')

        # update robots
        self.units = {}
        for cell in self.cells.values():
            if cell.units:
                self.units[cell.pos] = RobotGroup(cell.x, cell.y, cell.owner, cell.units)

        # update recyclers
        self.recyclers = {}
        seen = set()
        for cell in self.cells.values():
            if cell.recycler:
                area = [self.cells[pos] for pos in self.neighbors(*cell.pos) if cell.pos not in seen]
                seen |= set(self.neighbors(*cell.pos))
                self.recyclers[cell.pos] = Recycler(cell.x, cell.y, cell.owner, area)

        self.update_possessions()
        self.update_contigs()
        self.update_tension_map()
        self.update_threat_map()
        self.update_nearest_enemy()

    def owned_units(self):
        return [r for r in self.units.values() if r.owner == Player.ME]

    def opponent_units(self):
        return [r for r in self.units.values() if r.owner == Player.OPPONENT]

    def owned_recyclers(self):
        return [r for r in self.recyclers.values() if r.owner == Player.ME]

    def opponent_recyclers(self):
        return [r for r in self.recyclers.values() if r.owner == Player.OPPONENT]

    def tension(self, cell):
        return self.index_tensions.get(cell.pos, 0)

    def threat(self, cell):
        return self.index_threats.get(cell.pos, 0)

    def current_winner(self):
        if self.me.territory > self.opponent.territory:
            return Player.ME
        elif self.me.territory < self.opponent.territory:
            return Player.OPPONENT
        else:
            return Player.NONE

    def update_possessions(self):
        self.me.territory = 0
        self.opponent.territory = 0

        for c in self.cells.values():
            if c.owned:
                self.me.territory += 1
            elif c.is_opponents:
                self.opponent.territory += 1

    def update_contigs(self):
        """ contigs are isolated blocks of cells """
        self.contigs = []
        self.index_contigs = {}

        seen = []
        # build contigs
        for c in self.cells.values():
            if c.pos in seen or c.is_grass:
                continue

            contig = Contig(c.pos)

            candidates = self.neighbors(*c.pos)

            while candidates:

                candidate = candidates.pop()
                seen.append(candidate)

                if self.cells[candidate].is_grass or self.cells[candidate].recycler or candidate in contig.area:
                    continue

                for n in self.neighbors(*candidate):
                    if n not in contig.area:
                        candidates.append(n)

                contig.area.append(candidate)

            self.contigs.append(contig)

        self.index_contigs = {p: None for p in self.cells}

        for contig in self.contigs:
            owners = set()

            # update index
            for p in contig.area:
                self.index_contigs[p] = contig
                owners.add(self.cells[p].owner)

                if self.cells[p].owned and self.cells[p].units:
                    contig.has_robots = True

            # status
            if Player.ME in owners:
                if Player.OPPONENT in owners:
                    contig.status = Contig.CONFLICTUAL
                elif Player.NONE in owners:
                    contig.status = Contig.PARTIALLY_OWNED
                else:
                    contig.status = Contig.OWNED
            else:
                contig.status = Contig.NOT_OWNED

    def update_tension_map(self):
        self.index_tensions = {}

        for c in self.cells.values():

            if not c.units:
                continue

            k = 1 if c.is_opponents else -1
            tension = k * c.units
            self.index_tensions[c.pos] = self.index_tensions.get(c.pos, 0) + tension

    def update_threat_map(self):
        self.index_threats = {}

        for c in self.cells.values():
            if not c.is_opponents or not c.units:
                continue

            threat = c.units
            for n in self.neighbors(*c.pos):
                self.index_threats[n] = self.index_threats.get(n, 0) + threat

    def update_nearest_enemy(self):
        self.index_nearest_enemy = {pos: 0 for pos in self.cells}

        for contig in self.contigs:
            for pos in contig.area:
                c = self.cells[pos]
                if not c.owned or not any(self.cells[n].owned for n in self.neighbors(*pos)):
                    continue

                nearest = None

                for other_pos in contig.area:
                    other = self.cells[other_pos]
                    if not other.is_opponents:
                        continue

                    dist = self.manhattan(c.pos, other.pos)

                    if not nearest or dist < nearest[1]:
                        nearest = (other.pos, dist)

                if nearest:
                    self.index_nearest_enemy[c.pos] = nearest[1]

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

        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(f"<!> pathfinding broken from {start} to {target}")
                    return None

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

                cell = self.cells[(x, y)]

                if not cell.is_movable:
                    continue

                if cell.lifetime <= (current.cost + 1):
                    continue

                cost = current.cost + 1
                priority = cost + self.manhattan((x, y), target)

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

        return None

    def get_next_build_action(self):

        build_actions = Queue()

        # List available build actions
        k0 = 80000
        kmax_build = 70000
        k_available_amount = -1000
        k_already_exploited = 30000
        k_area_unit = 500
        k_area_owned = 1000
        k_area_neutral = 0
        k_area_opponents = -4000
        k_area_opponent_unit = -1000
        k_recyclers_owned = 5000
        k_space_around = -1000
        k_aggressive_build = 8000
        k_aggressive_build_for_defense = -6000
        k_aggressive_build_tension = -1000
        k_first_rounds = 8000  # on décourage le build lors des premiers rounds, il bloque l'avancée

        k0_recyclers_owned = k_recyclers_owned * len(self.owned_recyclers())

        for contig in self.contigs:
            if contig.status in (Contig.OWNED, Contig.PARTIALLY_OWNED, Contig.NOT_OWNED):
                # nothing to do
                continue

            for p in contig.area:
                place = self.cells[p]
                if not place.owned or place.units or place.recycler:
                    continue

                k = k0

                if self.round <= 3:
                    k += (4 - self.round) * k_first_rounds

                area = [place.pos] + self.neighbors(*place.pos)
                destination = Build.SUPPORT if not any(self.cells[p].is_opponents for p in area) else Build.AGGRESSIVE
                k0_already_exploited = 0

                for pos in area:
                    k += k_available_amount * self.cells[pos].amount
                    k0_already_exploited += k_already_exploited * self.cells[pos].in_range_of_recycler

                    if self.cells[pos].owned:
                        k += k_area_owned
                        k += k_area_unit * self.cells[pos].units
                    elif self.cells[pos].is_opponents:
                        k += k_area_opponents
                        k += k_area_opponent_unit * self.cells[pos].units
                    else:
                        k += k_area_neutral

                if destination == Build.SUPPORT:
                    neighborhood = {n for p in area for n in self.neighbors(*p) if n not in area}

                    for n in neighborhood:
                        if self.cells[n].amount > 1:
                            k += k_space_around

                    k += k0_recyclers_owned
                    k += k0_already_exploited

                else:
                    k += k_aggressive_build
                    if self.current_winner() == Player.ME:
                        k += k_aggressive_build_for_defense

                    for n in self.neighbors(p[0], p[1], True):
                        k += k_aggressive_build_tension * self.index_tensions.get(n, 0)

                if k > kmax_build:
                    continue

                action = Build(place.pos, destination, k)
                build_actions.put(k, action)

        # List available spawn actions
        k0 = 54000
        kmax_spawn = 70000
        k_opportunities = -1000
        k_conquest = -3000
        k_tension = -1000
        k_tension_bridgehead = -1000
        k_tension_around = -300
        k_tension_around_bridgehead = -300
        k_dist_to_enemy = 400
        k_bridgehead = -6000
        k_reinforcement = 500
        ki = 0  # little hack to avoid the while in queue.put

        for contig in self.contigs:
            if contig.status == Contig.OWNED:
                # nothing to do
                continue

            if contig.status == Contig.PARTIALLY_OWNED and contig.has_robots:
                # nothing to do
                continue

            for p in contig.area:
                place = self.cells[p]

                if not place.owned or not place.is_movable or place.unmovable_next_round:
                    continue

                k = k0 + ki
                ki += 1

                is_bridgehead = sum(self.cells[n].is_opponents for n in self.neighbors(p[0], p[1], True)) > 5

                tension = self.index_tensions.get(place.pos, 0)
                for pos in self.neighbors(place.pos[0], place.pos[1], True):
                    tension += self.index_tensions.get(pos, 0)
                k += k_tension * tension + k_tension_bridgehead * is_bridgehead

                for pos in self.neighbors(*place.pos):
                    n = self.cells[pos]
                    if not n.is_movable:
                        continue

                    if n.is_neutral:
                        k += k_opportunities
                    elif n.is_opponents:
                        k += k_conquest

                    k += k_tension_around * self.tension(n) + k_tension_around_bridgehead * is_bridgehead

                k += k_dist_to_enemy * self.index_nearest_enemy[p]

                amount = max(sum([self.index_tensions.get(n, 0) for n in self.neighbors(*p)]), 1)

                if k > kmax_spawn:
                    continue

                for _ in range(amount):
                    action = Spawn(place.pos, 1, k)
                    build_actions.put(k, action)
                    k += k_reinforcement

        # log('---')
        # for action in sorted([a for a in build_actions.values() if type(a) is Spawn], key=lambda x: x.priority)[:10]:
        #     log(action)

        if not build_actions:
            return None

        action = build_actions.get()

        # update cells to take this order into account
        place = self.cells[action.pos]

        if type(action) is Build:
            place.recycler = True
            area = [action.pos] + self.neighbors(*action.pos)
            self.recyclers[action.pos] = Recycler(action.pos[0], action.pos[1], Player.ME, area)
            for pos in area:
                self.cells[pos].in_range_of_recycler = True

            self.update_contigs()

        if type(action) is Spawn:
            place.units += action.amount

            if action.pos in self.units:
                self.units[action.pos].amount += action.amount
            else:
                self.units[action.pos] = RobotGroup(action.pos[0], action.pos[1], Player.ME, action.amount, 0)

            if action.pos in self.index_tensions:
                self.index_tensions[action.pos] -= action.amount
            else:
                self.index_tensions[action.pos] = -1 * action.amount

        return action

    def build_move_actions(self):
        # List possible destinations per contig
        move_actions = []

        k0_position = 60000
        k_position_distance = 3000
        k_position_opponents = -5000
        k_position_destroy = -3000
        k_dist_to_enemy = 1000
        k_colonize = -5000
        k_consolidate = -2000
        k_expand = -600
        k_threat = -1500
        ki = 0  # little hack to avoid the while in queue.put

        for contig in self.contigs:
            orders = []
            units = []

            if contig.status in (Contig.NOT_OWNED, Contig.OWNED):
                # nothing to do
                continue

            # on ne conserve que les cases voisines ou limitrophes du territoire
            move_area = []
            for pos in contig.area:
                c = self.cells[pos]

                if (c.owned and any(not self.cells[n].owned for n in self.neighbors(*pos))) or \
                        (not c.owned and any(self.cells[n].owned for n in self.neighbors(*pos))):
                    move_area.append(pos)

            # list destinations
            for pos in move_area:
                c = self.cells[pos]
                k = k0_position + ki
                ki += 1

                if c.owned or not c.is_movable:
                    continue

                amount_needed = 1

                if c.is_opponents:
                    k += k_position_opponents
                    if c.units:
                        k += k_position_destroy
                        amount_needed = c.amount

                k += k_dist_to_enemy * self.index_nearest_enemy[pos]
                k += k_threat * self.threat(c)

                for n in self.neighbors(pos[0], pos[1], True):
                    if not self.cells[n].is_grass and not self.cells[n].owned:
                        k += k_expand

                order = MoveOrder(pos, amount_needed, k)

                orders.append(order)

            # Prioritize units per distance
            for pos in contig.area:
                if pos in self.units:
                    unit = self.units[pos]
                    if not unit.owned or not unit.initial_amount:
                        continue
                    units.append(unit)

            q = Queue()
            for unit in units:
                for order in orders:
                    destination = order.pos
                    dist = self.manhattan(unit.pos, destination)

                    priority = order.priority
                    priority += k_position_distance * dist

                    if contig.status == Contig.CONFLICTUAL:
                        # advance
                        if self.me.side == Player.SIDE_WEST and order.pos[0] > unit.pos[0] \
                                or self.me.side == Player.SIDE_EAST and order.pos[0] < unit.pos[0]:
                            priority += k_colonize

                        # consolidate the frontline
                        if self.me.side == Player.SIDE_WEST and order.pos[0] == unit.pos[0] \
                                or self.me.side == Player.SIDE_EAST and order.pos[0] == unit.pos[0]:
                            priority += k_consolidate

                    candidate = MoveOrderCandidate(order, unit, destination)

                    q.put(priority, candidate)

            # for priority, candidate in sorted(q.items, key=lambda x: x[0])[:18]:
            #     log(f"{candidate.unit.pos} -> {candidate.order.pos}, p:{priority}, a:{candidate.order.amount}")

            # affect orders
            while q:
                k, candidate = q.get_items()
                if candidate.unit.has_played:
                    continue
                if candidate.order.fulfilled:
                    continue

                # attention, on prend le montant initial car les unités spawned ce tour ne peuvent pas bouger
                amount = min(candidate.order.amount, candidate.unit.initial_amount)

                from_, to_ = candidate.unit.pos, candidate.destination

                if from_ == to_:
                    # already there
                    continue

                action = Move(from_, to_, amount, k)

                candidate.unit.amount_played += amount
                candidate.order.affected += amount

                # update situation
                # next_pos = None
                # if to_ in self.neighbors(*from_):
                #     next_pos = to_
                # # else:
                # #     path = self.path(from_, to_)
                # #     if path:
                # #         next_pos = path[0]
                #
                # self.cells[from_].units -= amount
                # self.index_tensions[from_] += amount
                # if next_pos:
                #     self.cells[next_pos].units -= amount
                #     candidate.unit.pos = next_pos
                #     self.index_tensions[next_pos] = self.index_tensions.get(next_pos, 0) - amount

                move_actions.append(action)

        return move_actions

    def act(self):
        # Resolve
        actions = []
        expanse = 0
        log('compute build actions')
        while expanse < self.me.matter:
            action = self.get_next_build_action()
            if action is None:
                break

            if (expanse + action.COST) > self.me.matter:
                break

            actions.append(action)
            expanse += action.COST

        log('computes move actions')
        actions += self.build_move_actions()

        if not actions:
            actions.append(Wait())

        log('resolve')
        for action in actions:
            log(action)

        print(";".join([a.do() for a in actions]))


grid = Grid.create()

while True:
    grid.update()
    log(f"round {grid.round}")
    # for contig in grid.contigs:
    #     log(contig)
    # grid.print(lambda x: f"{grid.threat(x):02d}")

    grid.act()