''' >> https://www.codingame.com/ide/173171838252e7c6fd6f3ff9cb8169431a08eec1 @author: olivier.massot, may 2019 ''' import heapq import sys import time # TODO # * take units and towers in account when computing the threat # ? when priority needs a lvl3 unit, find a way to spare # * resurrect the strategic value: number of cells depending of the cell # * consider defending also cells not owned # * make a first turn of moves for units deep inside the territory, to avoid unecessary training and computing # x reduce interest of defend a pivot it has no movable cell around # ! ensure lvl3 units are working! debug = True t0 = time.time() def log(*msg): if debug: print("{} - ".format(str(time.time() - t0)[1:5]), *msg, file=sys.stderr) # OWNER ME = 0 OPPONENT = 1 # BUILDING TYPE HQ = 0 class Base(): def __repr__(self): return f"<{self.__class__.__name__}: {self.__dict__}>" class Queue(Base): 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 InterestQueue(Queue): def __add__(self, other): self.items += other.items return self def put(self, item): heapq.heappush(self.items, item) def get(self): return heapq.heappop(self.items) class BasePosition(Base): def __init__(self, cell, *args, **kwargs): self.interest = 0 self.cell = cell @property def x(self): return self.cell.x @property def y(self): return self.cell.y @property def pos(self): return self.cell.pos def __lt__(self, other): return self.interest < other.interest def eval(self): raise NotImplementedError class Position(BasePosition): def __init__(self, cell): super().__init__(cell) self.possession = 0 self.threat = 0 self.pivot = 0 self.union = 0 self.depth = 0 self.hq = 0 self.tower = 0 self.mine = 0 self.dist_to_goal = 0 self.min_level = 1 def pre_eval(self): # *** Eval interest: the lower the better self.interest = 0 self.min_level = 1 # eval possession if self.cell.active_owned: self.possession = 1 elif self.cell.active_opponent: self.possession = -1 # eval threat self.threat = 0 if self.cell.active_owned: self.threat = self.cell.threat self.covers = sum([grid[n].owned for n in self.cell.neighbors]) # eval pivot self.pivot = self.cell.pivot_value self.next_to_pivot = any(grid[n].pivot_value for n in self.cell.neighbors) # cell is not easily reachable self.protected = len([n for n in grid.neighbors(*self.cell.pos, True) if not grid[n].movable]) == 6 # distance to the ennemy HQ self.dist_to_goal = Grid.manhattan(self.cell.pos, opponent.hq.pos) # distance to the own HQ self.dist_to_hq = Grid.manhattan(self.cell.pos, player.hq.pos) # distance to the center of the map self.dist_to_center = Grid.manhattan(self.cell.pos, (6,6)) # priorize adjacent cells self.union = len([n for n in self.cell.neighbors if grid[n].active_owned]) # favorize dispersion self.concentration = len([n for n in self.cell.neighbors if grid[n].unit and grid[n].unit.owned]) self.deadends = len([n for n in self.cell.neighbors if not grid[n].movable]) # include 'depthmap' self.depth = self.cell.depth self.under_tower = self.cell.under_tower self.overlaps_tower = sum([grid[n].under_tower for n in self.cell.neighbors]) # priorize mines or HQ if self.cell.building: self.hq = int(self.cell.building.type_ == Building.HQ) self.tower = int(self.cell.building.type_ == Building.TOWER) self.mine = int(self.cell.building.type_ == Building.MINE) # *** Min level to go there if self.cell.unit and self.cell.unit.opponents: self.min_level = min([self.cell.unit.level + 1, 3]) if self.cell.under_tower: self.min_level = 3 def eval(self): self.pre_eval() self.interest = 3 * self.depth + self.dist_to_goal + 2 * self.concentration + 2 * self.deadends def __repr__(self): detail = [self.possession, self.threat, self.pivot, self.dist_to_goal, self.union, self.concentration, self.depth, self.hq, self.tower, self.mine] return "<{} {}: {}, {} ({})>".format(self.__class__.__name__, self.pos, self.interest, self.min_level, detail) class Defend(Position): def __init__(self, cell): super().__init__(cell) def __repr__(self): detail = [self.threat, self.covers, self.pivot, self.dist_to_hq, self.cell.danger, self.cell.critical, self.under_tower, self.overlaps_tower] return "<{} {}: {}, {} ({})>".format(self.__class__.__name__, self.pos, self.interest, self.min_level, detail) def eval(self): self.pre_eval() self.interest = 20 \ - 2 * self.covers \ - (8 * self.pivot if not self.protected else 4 * self.pivot) \ - 80 * self.cell.critical \ - 25 * self.cell.danger \ + 25 * self.cell.under_tower \ + 10 * self.overlaps_tower \ + self.dist_to_hq class Secure(Position): def __init__(self, cell, emergency = False): super().__init__(cell) self.emergency = emergency def __repr__(self): detail = [self.threat, self.covers, self.pivot, self.under_tower, self.overlaps_tower] return "<{} {}: {}, {} ({})>".format(self.__class__.__name__, self.pos, self.interest, self.min_level, detail) def eval(self): self.pre_eval() self.interest = 30 \ - 2 * self.threat \ - 2 * self.covers \ - (8 * self.pivot if not self.protected else 2 * self.pivot) \ + 25 * self.cell.under_tower \ + 10 * self.overlaps_tower \ + self.dist_to_center class Attack(Position): def eval(self): self.pre_eval() self.interest = 15 * self.possession \ - 5 * self.pivot \ - 3 * self.next_to_pivot \ - 2 * self.union \ + 4 * self.dist_to_goal \ - 25 * self.tower \ - 15 * self.mine \ - 100 * self.hq \ - 50 * self.cell.critical \ - 20 * self.cell.danger \ + 10 * (self.min_level - 1) \ - 15 * (self.cell.pos in sum(grid.divide, [])) class Colonize(Position): def eval(self): self.pre_eval() self.interest = 15 * self.possession \ - 5 * self.next_to_pivot \ - 2 * self.union \ + 3 * self.concentration \ + 2 * self.deadends \ + 4 * self.depth \ + 2 * self.dist_to_goal \ - max([0, 3 - self.dist_to_hq]) \ + 2 * self.dist_to_center class MinePosition(BasePosition): def __init__(self, target): super().__init__(target) def eval(self): # the lower the better self.interest -= self.cell.depth class BaseLoc(Base): def __init__(self, x, y): self.x = x self.y = y @property def pos(self): return self.x, self.y class MineSite(BaseLoc): def __init__(self, x, y): super().__init__(x, y) class BaseOwnedLoc(BaseLoc): def __init__(self, x, y, owner): super().__init__(x, y) self.owner = owner @property def owned(self): return self.owner == ME @property def opponents(self): return self.owner == OPPONENT class Building(BaseOwnedLoc): HQ = 0 MINE = 1 TOWER = 2 cost = {0: 0, 1: 20, 2: 15} maintenance = {0: 0, 1: 0, 2: 0} def __init__(self, owner, type_, x, y): super().__init__(x, y, owner) self.type_ = type_ @property def hq(self): return self.type_ == Building.HQ class Unit(BaseOwnedLoc): cost = {1: 10, 2: 20, 3: 30} maintenance = {1: 1, 2: 4, 3: 20} def __init__(self, owner, id_, level, x, y): super().__init__(x, y, owner) self.id_ = id_ self.level = level self.has_moved = False class Player(Base): def __init__(self, id_): self.id_ = id_ self.gold = 0 self.income = 0 self.units = [] self.buildings = [] self.hq = None self.spent = 0 self.new_charges = 0 self.to_spare = 0 def update(self, gold, income, units, buildings): self.gold = gold self.income = income self.units = [u for u in units if u.owner == self.id_] self.buildings = [b for b in buildings if b.owner == self.id_] self.hq = next((b for b in self.buildings if b.type_ == HQ)) self.spent = 0 self.new_charges = 0 @property def current_gold(self): return self.gold - self.spent @property def current_income(self): return self.income - self.new_charges def training_capacity(self): return min([(self.gold - self.spent) // Unit.cost[1], (self.income - self.new_charges) // Unit.maintenance[1]]) def can_afford(self, lvl): return (self.gold - self.spent) >= Unit.cost[lvl] and (self.income - self.new_charges) >= Unit.maintenance[lvl] def max_affordable(self): for lvl in range(3, 0, -1): if self.can_afford(lvl): return lvl return 0 def can_act(self): return self.training_capacity() > 0 or self.gold >= 15 or any(not unit.has_moved for unit in self.units) class Cell(Base): def __init__(self, x, y): self.x = x self.y = y self._content = "#" self.neighbors = [] self.unit = None self.building = None self.mine_site = None self.under_tower = False self.depth = 0 self.pivot_for = [] self.pivot_value = 0 self.critical = False self.danger = False self.threat = 0 self.threat_by = None @property def pos(self): return self.x, self.y @property def raw_val(self): return self._content def update(self, content, unit = None, building = None): self._content = content self.unit = unit self.building = building self.under_tower = False self.depth = 0 self.pivot_for = [] self.pivot_value = 0 self.threat = 0 self.threat_by = None self.critical = False self.danger = False @property def movable(self): return self._content != "#" @property def owned(self): return self._content.lower() == "o" @property def opponents(self): return self._content.lower() == "x" @property def owner(self): if self.owned: return ME elif self.opponents: return OPPONENT else: return None @property def headquarter(self): return self.pos in Grid.hqs @property def occupied(self): return self.unit or self.building @property def active(self): return self._content.isupper() @property def active_owned(self): return self._content == "O" @property def active_opponent(self): return self._content == "X" def is_active_owner(self, player_id): if player_id == ME: return self.active_owned elif player_id == OPPONENT: return self.active_opponent else: return False def owned_unit(self): if self.unit and self.unit.owned: return self.unit def owned_building(self): if self.building and self.building.owned: return self.building def take_possession(self): self._content = "O" def desactivate(self): self._content = self._content.lower() def get_unit_level(self): return self.unit.level if self.unit else 0 class Node(Base): def __init__(self, pos, path=[]): self.pos = pos self.path = path 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}>" class Grid(Base): dim = 12 hqs = [(0,0), (11,11)] def __init__(self, mines_sites = []): self.cells = {(x, y): Cell(x, y) for x in range(Grid.dim) for y in range(Grid.dim)} for pos, cell in self.cells.items(): cell.neighbors = [p for p in self.neighbors(*pos) if p in self.cells] self.units = [] self.buildings = [] for m in mines_sites: self.cells[(m.x, m.y)].mine_site = m self.threat_level = 0 def print_grid(self): return "\n".join(["".join([c for c in row]) for row in self.grid]) @property def pos(self): return self.x, self.y @property def grid(self): return [[self.cells[(x, y)].raw_val for x in range(Grid.dim)] for y in range(Grid.dim)] def __getitem__(self, key): return self.cells[key] def update(self, grid, buildings, units): buildings_ix = {(b.x, b.y): b for b in buildings} units_ix= {(u.x, u.y): u for u in units} self.buildings = list(buildings) self.units = list(units) for y, row in enumerate(grid): for x, c in enumerate(row): self.cells[(x, y)].update(c, units_ix.get((x, y), None), buildings_ix.get((x, y), None)) log(" * update pivots") # self.update_pivots() self.update_propagation(ME) self.update_propagation(OPPONENT) log(" * update threats") self.update_threats() self.update_state() self.update_divide_and_conquer() def update_state(self): self.update_tower_areas() self.update_frontlines() self.update_depth_map() @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] @classmethod def zone(cls, center, radius): return [(x, y) for x in range(0, cls.dim) for y in range(0, cls.dim) if cls.manhattan(center, (x, y)) <= radius] def zone_set(self, center, radius): zone = set(center) for _ in range(radius): for p in zone: zone |= self.neighbors(*p) @staticmethod def closest(from_, in_): return min(in_, key=lambda x: Grid.manhattan(from_, x)) def get_hq(self, player_id): return next((b for b in self.buildings if b.owner == player_id and b.hq)) def update_tower_areas(self): for b in self.buildings: if b.type_ == Building.TOWER: self.cells[b.pos].under_tower = True for n in self.cells[b.pos].neighbors: self.cells[n].under_tower = True def update_frontlines(self): # update the current frontlines self.frontline = [] self.frontex = [] for cell in self.cells.values(): if cell.active_owned: if any(self.cells[c].movable and not self.cells[c].active_owned for c in cell.neighbors): self.frontline.append(cell) def update_depth_map(self): buffer = [c.pos for c in self.frontline] for p in buffer: self.cells[p].depth = 1 next_buffer = [] while buffer: for p in buffer: for n in self.cells[p].neighbors: if self.cells[n].active_owned and not self.cells[n].depth: self.cells[n].depth = self.cells[p].depth + 1 next_buffer.append(n) buffer = list(next_buffer) next_buffer = [] def _active_owned(self, pos, player_id): try: return self.cells[pos].is_active_owner(player_id) except KeyError: return False def update_propagation(self, player_id): start = self.get_hq(player_id).pos lvl = 0 propagation = {start: (lvl, [])} pivots_cells = [] for x, y in self.cells: if (x, y) != start and self._active_owned((x, y), player_id): around = [(x, y - 1), (x + 1, y - 1), (x + 1, y), (x + 1, y + 1), (x, y + 1), (x - 1, y + 1), (x - 1, y), (x - 1, y - 1)] owned = [self._active_owned(p, player_id) for p in around] changes = [x for x in zip(owned, owned[1:]) if x == (True, False)] if len(changes) > 1: pivots_cells.append((x, y)) pivots = {p: [] for p in pivots_cells} buffer = [start] while buffer: new_buffer = [] lvl += 1 for pos in buffer: for n in self.neighbors(*pos): if self._active_owned(n, player_id): if not n in propagation: propagation[n] = (lvl, [pos]) new_buffer.append(n) else: # already visited if propagation[pos][1] != [n] and propagation[n][0] >= propagation[pos][0]: propagation[n][1].append(pos) buffer = new_buffer self.propagation = propagation children = {} for p, data in self.propagation.items(): _, parents = data for parent in parents: if not parent in children: children[parent] = [] children[parent].append(p) for pivot in pivots: buffer = set(children.get(pivot, [])) while buffer: new_buffer = set() for child in buffer: new_buffer |= set(children.get(child, [])) pivots[pivot] += list(buffer) buffer = new_buffer # cleaning 'false children' for pivot, children in pivots.items(): invalid = [] for child in children: parents = self.propagation[child][1] if any((p != pivot and p not in children) or p in invalid for p in parents): invalid.append(child) for p in invalid: children.remove(p) log("player {}, pivots: {}".format(player_id, {k: len(v) for k, v in pivots.items()})) for pivot, pivot_for in pivots.items(): self.cells[pivot].pivot_for = pivot_for self.cells[pivot].pivot_value = sum([1 + grid[p].get_unit_level() for p in pivot_for]) def update_divide_and_conquer(self): segs = [] for c in self.frontline: for n in c.neighbors: if n in self.cells and self.cells[n].active_opponent: seg = [] x, y = c.pos xn, yn = n if xn > x: dx = 1 elif xn < x: dx = -1 else: dx = 0 if yn > y: dy = 1 elif yn < y: dy = -1 else: dy = 0 x, y = x + dx, y + dy while (x, y) in self.cells and self.cells[(x, y)].active_opponent: seg.append((x, y)) x, y = x + dx, y + dy if seg: segs.append(seg) self.divide = [s for s in segs if len(s) <= 4] log(self.divide) def update_threats(self): # 1 + max number of units opponents can produce in one turn self.threat_level = 2 + (opponent.gold + opponent.income) // Unit.cost[1] ennemy_frontier = [c for c in self.cells.values() if c.active_opponent \ and any(self.cells[n].movable and not self.cells[n].opponents for n in c.neighbors)] for cell in self.cells.values(): if cell.owned: closest, dist = min([(o, Grid.manhattan(cell.pos, o.pos)) for o in ennemy_frontier], key=lambda x: x[1]) if cell.unit: dist += cell.unit.level if cell.under_tower: dist += 2 if dist < self.threat_level: cell.threat = self.threat_level - dist cell.threat_by = closest hqcell = grid[player.hq.pos] self.emergency = hqcell.threat > 0 self.update_threat_path() def update_threat_path(self): hqcell = grid[player.hq.pos] if not hqcell.threat > 0: return closest_threat = hqcell.threat_by log(f"* {closest_threat.pos} threats HQ") path = self.path(closest_threat.pos, player.hq.pos) if path: log(f"* Path to HQ: {path}") extended_path = set() for p in path: extended_path |= set(self.neighbors(*p)) extended_path -= set(path) for p in path: self.cells[p].critical = True for p in extended_path: self.cells[p].danger = True def path(self, start, target): nodes = Queue() its, break_on = 0, 2000 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: its += 1 if its > break_on: log(" pathfinding broken") return None if (x, y) == current.parent: continue cell = self.cells[(x, y)] if not cell.movable: continue moving_cost = 1 if cell.unit and cell.unit.owned: moving_cost += cell.unit.level if cell.under_tower: moving_cost += 2 cost = current.cost + moving_cost priority = cost + 10 * Grid.manhattan((x, y), target) node = PathNode(x, y, current) node.cost = cost nodes.put(node, priority) return None def influence_zone(self, player_id): owned, neighbors = {p for p, c in self.cells.items() if c.owner == player_id and c.active}, set() for p in owned: neighbors |= set(self.neighbors(*p)) return (self.cells[p] for p in (owned | neighbors) if self.cells[p].movable) def training_places(self): return (c for c in self.influence_zone(ME) if self.can_move(c.pos)) def get_next_training(self, max_level=3): q = InterestQueue() for cell in self.training_places(): q.put(Position(cell)) if not q: return None action = q.get() if max_level < 3: while action.cell.under_tower: try: action = q.get() except IndexError: return None level = 1 for ennemy in opponent.units: if Grid.manhattan(action.cell.pos, ennemy.pos) < 3: level = min(ennemy.level + 1, max_level) break action.level = level return action def can_move(self, pos, level=1): cell = self.cells[pos] can_move = True can_move &= cell.movable can_move &= not cell.owned_unit() can_move &= not cell.owned_building() if level != 3: can_move &= (cell.unit is None or cell.unit.level < level) can_move &= cell.owned or not cell.under_tower return can_move def moving_zone(self, unit): return (self.cells[p] for p in self.cells[unit.pos].neighbors if self.can_move(p, unit.level)) def get_next_move(self, unit): q = InterestQueue() for cell in self.moving_zone(unit): o = Position(cell) o.eval() q.put(o) if not q: return None objective = q.get() return objective def building_zone(self, type_): if type_ == Building.MINE: return [cell for cell in self.cells.values() if cell.mine_site and cell.depth > 3] else: return [] def get_building_site(self, type_): q = InterestQueue() for cell in self.building_zone(type_): q.put(MinePosition(cell)) if not q: return None return q.get() def remove_unit_from(self, cell): opponent.units.remove(cell.unit) self.units.remove(cell.unit) cell.unit = None def cost_for_new_mine(self): return Building.cost[Building.MINE] + 4 * len([b for b in player.buildings if b.type_ == Building.MINE]) def apply(self, action): if type(action) is Move: old_cell, new_cell = self.cells[action.unit.pos], action.cell if new_cell.unit: if new_cell.unit.owned: log("ERROR: impossible move (owned unit here)") return if action.unit.level < 3 and new_cell.unit.level >= action.unit.level: log("ERROR: impossible move (unit here, level too low)") return # cell is occupied by an opponent's unit with an inferior level self.remove_unit_from(new_cell) if new_cell.building and new_cell.building.type_ == Building.TOWER: if new_cell.owned: log("ERROR: impossible move (allied tower here)") if action.unit.level < 3: log("ERROR: impossible move (tower here, level too low)") opponent.buildings.remove(new_cell.building) self.buildings.remove(new_cell.building) new_cell.building = None old_cell.unit = None action.unit.x, action.unit.y = new_cell.pos new_cell.unit = action.unit action.unit.has_moved = True if not new_cell.owned: if new_cell.opponents: for p in new_cell.pivot_for: self.cells[p].desactivate() if self.cells[p].unit and self.cells[p].unit.opponents: self.remove_unit_from(self.cells[p]) new_cell.take_possession() self.update_state() elif type(action) is Train: new_cell = action.cell unit = Unit(ME, None, action.level, *new_cell.pos) unit.has_moved = True player.spent += Unit.cost[action.level] player.new_charges += Unit.maintenance[action.level] if new_cell.unit: if new_cell.unit.owned: log("ERROR: impossible training") return if unit.level < 3 and new_cell.unit.level >= unit.level: log("ERROR: impossible training") return # cell is occupied by an opponent's unit with an inferior level self.remove_unit_from(new_cell) if new_cell.building and new_cell.building.opponents and new_cell.building.type_ == Building.TOWER: if unit.level < 3: log("ERROR: impossible training") opponent.buildings.remove(new_cell.building) self.buildings.remove(new_cell.building) new_cell.building = None new_cell.unit = unit if not new_cell.owned: if new_cell.opponents: for p in new_cell.pivot_for: self.cells[p].desactivate() if self.cells[p].unit and self.cells[p].unit.opponents: self.remove_unit_from(self.cells[p]) new_cell.take_possession() self.update_state() elif type(action) is BuildTower: new_cell = action.cell building = Building(ME, Building.TOWER, *new_cell.pos) new_cell.building = building player.buildings.append(building) player.spent += Building.cost[Building.TOWER] if building.type_ == Building.TOWER: new_cell.under_tower = True for n in new_cell.neighbors: self.cells[n].under_tower = True self.update_state() if self.emergency: self.update_threat_path() elif type(action) is BuildMine: player.spent += self.cost_for_new_mine() new_cell = action.cell building = Building(ME, Building.MINE, *new_cell.pos) new_cell.building = building player.buildings.append(building) class Action(Base): def command(self): raise NotImplementedError() class Wait(Action): def command(self): return "WAIT" class Move(Action): def __init__(self, unit, cell): self.unit = unit self.cell = cell def __repr__(self): return f"<{self.__class__.__name__}: {self.unit.id_} {self.cell.pos}>" def command(self): return f"MOVE {self.unit.id_} {self.cell.x} {self.cell.y}" class Train(Action): def __init__(self, level, cell): self.level = level self.cell = cell def __repr__(self): return f"<{self.__class__.__name__}: {self.level} {self.cell.pos}>" def command(self): return f"TRAIN {self.level} {self.cell.x} {self.cell.y}" class Build(Action): str_types = {1: "MINE", 2: "TOWER"} def __init__(self, type_, cell): self.type_ = type_ self.cell = cell def __repr__(self): return f"<{self.__class__.__name__}: {self.str_types[self.type_]} {self.cell.pos}>" def command(self): return f"BUILD {self.str_types[self.type_]} {self.cell.x} {self.cell.y}" class BuildTower(Build): def __init__(self, cell): super().__init__(Building.TOWER, cell) class BuildMine(Build): def __init__(self, cell): super().__init__(Building.MINE, cell) # ******** MAIN ************* test = False if test: mines_input = [] else: mines_input = [input() for _ in range(int(input()))] mines_sites = [MineSite(*[int(j) for j in item.split()]) for item in mines_input] # log(f"* mines: {mines_sites}") grid = Grid(mines_sites) player = Player(ME) opponent = Player(OPPONENT) def cmd_wait(): return "WAIT" def get_input(): if test: gold, income = 20, 1 opponent_gold, opponent_income = 20, 1 new_grid_input = ['O..#########', '...###...###', '...###....##', '#..##.....##', '...#......##', '#.........##', '##.........#', '##......#...', '##.....##..#', '##....###...', '###...###...', '#########..X'] buildings_input = ['0 0 0 0', '1 0 11 11'] units_input = [] else: gold, income = int(input()), int(input()) opponent_gold, opponent_income = int(input()), int(input()) new_grid_input = [input() for _ in range(12)] buildings_input = [input() for _ in range(int(input()))] units_input = [input() for _ in range(int(input()))] # log(gold, income, opponent_gold, opponent_income) # log(new_grid_input) # log(buildings_input) # log(units_input) return gold, income, opponent_gold, opponent_income, new_grid_input, buildings_input, units_input while True: # <--- get and parse input gold, income, opponent_gold, opponent_income, new_grid_input, buildings_input, units_input = get_input() new_grid = [list(row) for row in new_grid_input] buildings = [Building(*[int(j) for j in item.split()]) for item in buildings_input] # log(f"* buildings: {buildings}") units = [Unit(*[int(j) for j in item.split()]) for item in units_input] # log(f"* units: {units}") # ---> log("## Start ##") log("* Update") # <--- update player.update(gold, income, units, buildings) # log(f"player: {player}") opponent.update(opponent_gold, opponent_income, units, buildings) # log(f"opponent: {opponent}") grid.update(new_grid, buildings, units) # log(f"grid:\n{grid.print_grid()}") # ---> commands = [] # start log(f"Threat level: {grid.threat_level}") if grid.emergency: log(" HQ is threaten!") todo = [] played, abandonned = [], [] acted = True defs, max_def = 0, 8 to_spare = len([c for c in grid.cells.values() if c.owned]) while player.can_act(): if acted: # only re-eval if an action occured q = InterestQueue() for cell in grid.influence_zone(ME): if cell.movable and not cell in abandonned and not cell in played: if cell.owned and cell.threat > 0 and cell.pos != player.hq.pos: if defs > max_def: continue if grid.emergency: p = Defend(cell) else: p = Secure(cell) elif cell.opponents: p = Attack(cell) elif not cell.owned: p = Colonize(cell) else: continue p.eval() q.put(p) if not q: break acted = False objective = q.get() if type(objective) is Secure: if (player.current_gold - to_spare) > Building.cost[Building.TOWER] \ and not objective.cell.mine_site \ and not objective.cell.building: action = BuildTower(objective.cell) defs += 1 else: abandonned.append(objective.cell) continue elif type(objective) is Defend: if player.current_gold > Building.cost[Building.TOWER] \ and not objective.cell.mine_site \ and not objective.cell.building: action = BuildTower(objective.cell) defs += 1 elif objective.cell.unit and objective.cell.unit.owned: # already a unit here: stay on place objective.cell.unit.has_moved = True continue elif player.can_afford(1): action = Train(1, objective.cell) defs += 1 else: near_unit = next((grid[n].unit for n in objective.cell.neighbors if grid[n].unit and grid[n].unit.owned and grid[n].unit.level == 1 and not grid[n].unit.has_moved), None) if near_unit and grid.can_move(objective.cell.pos, near_unit.level): action = Move(near_unit, objective.cell) defs += 1 else: abandonned.append(objective.cell) continue elif type(objective) in (Colonize, Attack): near_units = [grid[n].unit for n in objective.cell.neighbors if grid[n].unit \ and grid[n].unit.owned \ and not grid[n].unit.has_moved \ and grid[n].unit.level == objective.min_level] if len(near_units) == 1: near_unit = near_units[0] elif len(near_units) > 1: near_unit = min(near_units, key=lambda u: len([u.pos == o.cell.pos for o in q.items])) else: near_unit = None if near_unit and grid.can_move(objective.cell.pos, near_unit.level): action = Move(near_unit, objective.cell) else: if objective.min_level > player.max_affordable() or player.gold < (to_spare + Unit.cost[objective.min_level]): abandonned.append(objective.cell) continue action = Train(objective.min_level, objective.cell) log(f"priority: {objective}") # a unit occupy the cell already_there = action.cell.unit if already_there and already_there.owned: if already_there.has_moved: log("cell is occupied: abandon") abandonned.append(objective.cell) continue log(f"* needs to evacuate unit {already_there.id_} before") evacuate = grid.get_next_move(already_there) if evacuate: evac_action = Move(already_there, evacuate.cell) log(f"forced: {evac_action}") grid.apply(evac_action) todo.append(evac_action) else: log(f" No move available for unit {already_there.id_}") abandonned.append(objective.cell) continue acted = True log(f"> Apply action {action}") played.append(action.cell) grid.apply(action) todo.append(action) # units which did not move for unit in player.units: if not unit.has_moved: objective = grid.get_next_move(unit) if objective: action = Move(unit, objective.cell) log(f"default: {action}") grid.apply(action) todo.append(action) else: log(f" No move available for unit {unit.id_}") unit.has_moved = True # can build mines? if player.current_gold > grid.cost_for_new_mine(): site = grid.get_building_site(Building.MINE) if site: action = BuildMine(site.cell) if action: log(f"default: {action}") grid.apply(action) todo.append(action) log(f"* todo: {todo}") commands = [action.command() for action in todo] if not commands: log("nothing to do: wait") commands = ["WAIT"] log(f"* commands: {commands}") print(";".join(commands))