''' >> https://www.codingame.com/ide/173171838252e7c6fd6f3ff9cb8169431a08eec1 @author: olivier.massot, may 2019 ''' 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) # 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 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 Action(Base): def __init__(self, target, *args, **kwargs): self.interest = 0 self.target = target self.x, self.y = target.pos self.eval(target, *args, **kwargs) def __lt__(self, other): return self.interest < other.interest def eval(self): raise NotImplementedError class Move(Action): def eval(self, target, unit): # the lower the better self.interest = 0 if target.owned and target.active: self.interest += 15 # already owned and active elif target.opponents and target.active: self.interest -= 15 # owned by opponents and active # non-passable cells around self.interest += 3 * len([n for n in target.neighbors if not grid[n].movable]) # an ennemy here if target.unit and target.unit.opponents: self.interest -= 20 # an ennemy nearby if any((grid[n].unit and grid[n].unit.opponents) for n in target.neighbors): self.interest += 15 # priorize adjacent cells self.interest -= (2 * len([n for n in target.neighbors if grid[n].owned])) # include 'heatmap' self.interest += 3 * target.heat class Train(Move): def eval(self, target): # the lower the better self.interest = 0 if target.owned and target.active: self.interest += 15 # already owned and active elif target.opponents and target.active: self.interest -= 15 # owned by opponents and active # non-passable cells around self.interest += 3 * len([n for n in target.neighbors if not grid[n].movable]) # an ennemy nearby if any((grid[n].unit and grid[n].unit.opponents) for n in target.neighbors): self.interest += 15 # priorize adjacent cells self.interest -= (2 * len([n for n in target.neighbors if grid[n].owned])) # include 'heatmap' self.interest += 3 * target.heat class BaseLoc(Base): def __init__(self, x, y): self.x = x self.y = y @property def pos(self): return self.x, self.y class Mine(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 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): def __init__(self, owner, id_, level, x, y): super().__init__(x, y, owner) self.id_ = id_ self.level = level class Player(Base): def __init__(self, id_): self.id_ = id_ self.gold = 0 self.income = 0 self.units = [] self.buildings = [] self.hq = None 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)) 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.heat = 0 @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.heat = 0 @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 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() class Grid(Base): dim = 12 hqs = [(0,0), (11,11)] def __init__(self, mines = []): 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 = {} self.mines = {(m.x, m.y): m for m in mines} 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): self.buildings = {(b.x, b.y): b for b in buildings} self.units = {(u.x, u.y): u for u in units} for y, row in enumerate(grid): for x, c in enumerate(row): self.cells[(x, y)].update(c, self.units.get((x, y), None), self.buildings.get((x, y), None)) self.update_heat_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] def get_hq(self, player): return next((b for b in self.buildings if b.owner == player and b.hq)) def update_heat_map(self): frontier = [] for p, cell in self.cells.items(): if not p in frontier and cell.owned and cell.active \ and any(self.cells[c].movable and (not self.cells[c].owned or not self.cells[c].active) for c in cell.neighbors): cell.heat = 1 frontier.append(p) buffer = frontier next_buffer = [] while buffer: for p in buffer: for n in self.cells[p].neighbors: if self.cells[n].owned and self.cells[n].active and not self.cells[n].heat: self.cells[n].heat = self.cells[p].heat + 1 next_buffer.append(n) buffer = list(next_buffer) next_buffer = [] def training_places(self): owned, neighbors = {p for p, c in self.cells.items() if c.owned}, set() for p in owned: neighbors |= set(self.neighbors(*p)) return (self.cells[p] for p in (owned | neighbors) if not self.cells[p].occupied) def get_next_training(self): q = InterestQueue() for cell in self.training_places(): q.put(Train(cell)) if not q: return None return q.get() def moving_zone(self, unit): return (self.cells[p] for p in self.cells[unit.pos].neighbors if self.cells[p].movable and (not self.cells[p].building or self.cells[p].building.opponents) and (not self.cells[p].unit or self.cells[p].unit.opponents)) def get_next_move(self, unit): q = InterestQueue() for cell in self.moving_zone(unit): q.put(Move(cell, unit)) if not q: return None return q.get() # ******** MAIN ************* test = False if test: mines_input = [] else: mines_input = [input() for _ in range(int(input()))] log(mines_input) mines = [Mine(*[int(j) for j in item.split()]) for item in mines_input] log(f"* mines: {mines}") grid = Grid() player = Player(ME) opponent = Player(OPPONENT) def cmd_train(target, level=1): return f"TRAIN {level} {target.x} {target.y}" def cmd_move(unit, target): return f"MOVE {unit.id_} {target.x} {target.y}" 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}") # ---> # <--- update grid.update(new_grid, buildings, units) # log(f"grid:\n{grid.print_grid()}") player.update(gold, income, units, buildings) log(f"player: {player}") opponent.update(opponent_gold, opponent_income, units, buildings) log(f"opponent: {opponent}") # ---> commands = [] # start if not player.units or (player.gold > 20 and player.income > (5 * len(player.units))): target = grid.get_next_training() if target: commands.append(cmd_train(target)) for unit in player.units: target = grid.get_next_move(unit) if target: commands.append(cmd_move(unit, target)) if not commands: log("nothing to do: wait") commands = ["WAIT"] log(commands) print(";".join(commands))