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) 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 Player(BaseClass): ME = 1 OPPONENT = 0 NONE = -1 def __init__(self, id_): self.id = id_ self.matter = 0 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 def is_movable(self): return self.amount > 0 and not self.recycler 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): self.x = x self.y = y self.owner = owner self.amount = amount @property def pos(self): return self.x, self.y 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 Action(BaseClass): pass class Wait(Action): @staticmethod def do(): return "WAIT" class Move(Action): def __init__(self, from_, to, amount): self.from_ = from_ self.to = to self.amount = amount 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 def __init__(self, pos): self.pos = pos def do(self): x, y = self.pos return f'BUILD {x} {y}' class Spawn(Action): COST = 10 def __init__(self, pos, amount): self.pos = pos self.amount = amount 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 = {} @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])) @staticmethod def manhattan(from_, to_): xa, ya = from_ xb, yb = to_ return abs(xa - xb) + abs(ya - yb) def neighbors(self, x, y): return [ (x, y) for x, y in [(x, y - 1), (x - 1, y), (x + 1, y), (x, y + 1)] if 0 <= x < self.width and 0 <= y < self.height ] @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): 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) # 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) 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 act(self): build_actions = Queue() # List available build actions places = [c for c in self.cells.values() if c.owned and c not in self.units] k0 = 100 k_available_amount = -1 k_already_exploited = 30 for place in places: action = Build(place.pos) k = k0 area = [place.pos] + self.neighbors(*place.pos) for pos in area: k += k_available_amount * self.cells[pos].amount k += k_already_exploited * self.cells[pos].in_range_of_recycler build_actions.put(k, action) # List available spawn actions places = [c for c in self.cells.values() if c.owned] k0 = 60 for place in places: action = Spawn(place.pos, 1) k = k0 build_actions.put(k, action) # List available move actions move_actions_per_unit = {} # targets = Queue() k0 = 100 k_blitzkrieg = -2 k_occupy = -5 k_destroy = -2 for u in self.owned_units(): move_actions_per_unit[u.pos] = Queue() nearest_enemy_cell = min( (c for c in self.cells.values() if c.is_opponents), key=lambda c: self.manhattan(c.pos, u.pos) ) nearest_enemy_cell_dist = self.manhattan(nearest_enemy_cell.pos, u.pos) for pos in self.neighbors(*u.pos): place = self.cells[pos] action = Move(u.pos, place.pos, u.amount) if not place.owned and place.is_movable(): k = k0 k += k_blitzkrieg * (nearest_enemy_cell_dist - self.manhattan(place.pos, nearest_enemy_cell.pos)) if place.is_opponents: k += k_occupy if place.pos in self.units: k += k_destroy * self.units[place.pos].amount move_actions_per_unit[u.pos].put(k, action) actions = [] expanse = 0 while build_actions and expanse <= self.me.matter: action = build_actions.get() actions.append(action) expanse += action.COST for move_actions in move_actions_per_unit.values(): if not move_actions: continue action = move_actions.get() actions.append(action) print(";".join([a.do() for a in actions])) grid = Grid.create() while True: grid.update() # grid.print(lambda x: f"{x.amount:2d}") grid.act()