cig/i_n_f/script.py

'''
>> https://www.codingame.com/ide/173171838252e7c6fd6f3ff9cb8169431a08eec1
@author: olivier.massot, may 2019
'''
from collections import Counter
import heapq
import sys
import time

# TODO
# * when building a tower, check that there is not already one, and block the cell for moving
# * do not train a unit of a cell if it is in a threatened pivot zone, especially not a level 3 unit!
# * take units and towers in account when computing the threat
# * take units and towers in account when computing the strategig value
# * review the tower placement in case of threat


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 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.strategic_value = 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

        # eval strategic value
        self.strategic_value = self.cell.strategic_value
        
        # covers (towers only)
        self.covers = self.strategic_value + sum([grid[n].strategic_value for n in self.cell.neighbors])
        
        # eval pivot
        self.pivot = sum([1 + grid[p].get_unit_level() for p in self.cell.pivot_for])

        # 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)
        
        # priorize adjacent cells
        self.union = len([n for n in self.cell.neighbors if grid[n].active_owned])
        
        # include 'depthmap'
        self.depth = self.cell.depth
        
        # 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

    def __repr__(self):
        detail = [self.possession, self.threat, self.strategic_value, self.pivot, self.dist_to_goal,
                  self.union, 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, emergency = False):
        super().__init__(cell)
        self.emergency = emergency
    
    def __repr__(self):
        detail = [self.threat, self.covers, self.pivot, self.emergency, self.dist_to_hq]
        return "<{} {}: {}, {} ({})>".format(self.__class__.__name__, self.pos, self.interest, self.min_level, detail)
    
    def eval(self):
        self.pre_eval()
        self.interest = 100 \
                        - 10 * self.threat \
                        - self.covers // 5 \
                        - 5 * self.pivot \
                        - 20 * self.emergency * (22 - self.dist_to_hq)
        
class Attack(Position):
    def eval(self):
        self.pre_eval()
        self.interest = 15 * self.possession \
                        - 5 * self.pivot \
                        - 2 * self.union \
                        + 3 * self.depth \
                        + self.dist_to_goal \
                        - 30 * self.tower \
                        - 15 * self.mine \
                        - 100 * self.hq
        
class MinePosition(BasePosition):
    def __init__(self, target, type_):
        self.type_ = type_
        super().__init__(target, type_)
    
    def eval(self):
        # the lower the better
        self.interest = 0
        
        if self.type_ == Building.MINE:
            self.interest -= self.target.depth
            
        elif self.type_ == Building.TOWER:
            if self.target.pivot:
                self.interest -= 20

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

    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 max_affordable(self):
        for lvl in range(3, 0, -1):
            if (self.gold - self.spent) >= Unit.cost[lvl] and (self.income - self.new_charges) >= Unit.maintenance[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.strategic_value = 0
        self.threat = 0
        
        # front cells
        self.facing = []
        self.support = []
        self.in_front_of = []
        
    @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.strategic_value = 0
        self.threat = 0
    
        self.facing = []
        self.support = []
        self.in_front_of = []
    
    @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 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 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))

        self.update_pivots()
        self.update_state()
        

    def update_state(self):
        self.update_tower_areas()
        self.update_frontlines()
        self.update_depth_map()
        self.update_threats()

    @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):
        c = self.cells[pos]
        return c.owner == player_id and c.active
    
    def update_pivot_for(self, player_id):
        start = self.get_hq(player_id).pos
        start_node = Node(start)
        
        buffer = [start_node]
        nodes = {start_node}
        
        ignored = [p for p in self.cells if len([n for n in self.neighbors(*p, diags=True) if self._active_owned(n, player_id)]) == 8]
        
        while buffer:
            new_buffer = []
            for node in buffer:
                if node.pos in ignored:
                    continue
                for n in self.neighbors(*node.pos):
                    if not n in node.path and self._active_owned(n, player_id):
                        new_node = Node(n, node.path + [node.pos])
                        nodes.add(new_node)
                        new_buffer.append(new_node)
            buffer = new_buffer
        
        paths_to = {}
        for node in nodes:
            if not node.pos in paths_to:
                paths_to[node.pos] = []
            paths_to[node.pos].append(node.path)
    
        pivots = {}
        for candidate in paths_to:
            if candidate == start:
                continue
            for p, paths in paths_to.items():
                if not paths or not paths[0] or p in ignored:
                    continue
                if all(candidate in path for path in paths):
                    if not candidate in pivots:
                        pivots[candidate] = []
                    pivots[candidate].append(p)
        
        for pivot, pivot_for in pivots.items():
            self.cells[pivot].pivot_for = pivot_for
            
        occurrences = Counter(sum(sum(paths_to.values(), []), []))
        
        while ignored:
            new_ignored = set()
            for p in ignored:
                occured_neighbors = [occurrences[n] for n in self.neighbors(*p) if n in occurrences]
                if not occured_neighbors:
                    new_ignored.add[p]
                    continue
                occurrences[p] = 2 * sum(occured_neighbors) // len(occured_neighbors)
            ignored = new_ignored
        
        max_occ = max(occurrences.values()) if occurrences else 1
        for p, occ in occurrences.items():
            self.cells[p].strategic_value = (100 * occ) // max_occ
            
#         if player_id == ME:
#             log(pivots)
#             log(occurrences)
#             log({cell.pos: cell.strategic_value for cell in self.cells.values() if cell.owned})
        
    def update_pivots(self):
        self.update_pivot_for(ME)
        self.update_pivot_for(OPPONENT)
    
    def update_threats(self):
        # 1 + max number of units opponents can produce in one turn
        self.threat_level = 1 + min([(opponent.gold + opponent.income) // Unit.cost[1], opponent.income // Unit.maintenance[1]])
        
        ennemy_frontier = [c for c in self.cells.values() if c.opponents \
                           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:
                threat = min([Grid.manhattan(cell.pos, o.pos) for o in ennemy_frontier])
                cell.threat = self.threat_level - threat
        
        self.emergency = grid[player.hq.pos].threat > 0
        
#         log({c.pos: c.threat for c in self.cells.values() if c.owned and c.threat is not 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(Position(cell, type_))
        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")
                    return
                if action.unit.level < 3 and new_cell.unit.level >= action.unit.level:
                    log("ERROR: impossible move")
                    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 action.unit.level < 3:
                    log("ERROR: impossible move")
                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.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()

        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}")   
    # --->
    
    # <--- 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 = []
    abandonned = []
    while player.can_act():
        
        q = InterestQueue()
        for cell in grid.influence_zone(ME):
            if cell.movable and not cell in abandonned:
                if cell.owned and cell.threat > 0 and cell.pos != player.hq.pos:
                    p = Defend(cell, grid.emergency)
                elif not cell.owned:
                    p = Attack(cell)
                else:
                    continue
                p.eval()
                q.put(p)
        
        if not q:
            break
        
        objective = q.get()
        if type(objective) is Defend:
            if player.current_gold > Building.cost[Building.TOWER] and not objective.cell.mine_site:
                action = BuildTower(objective.cell)
                
            else:
                # TODO: recruit units
                abandonned.append(objective.cell)
                continue
            
        elif type(objective) is Attack:
            near_unit = next((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), 
                              None)
            if near_unit:
                action = Move(near_unit, objective.cell)
            else:
                if objective.min_level > player.max_affordable():
                    abandonned.append(objective.cell)
                    continue
                action = Train(objective.min_level, objective.cell)
        
        log(f"priority: {action} -> {objective}")
        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}")
                
    # can build mines?
    if player.current_gold > grid.cost_for_new_mine():
        action = BuildMine(grid.get_building_site(Building.MINE))
        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))