codeingame/i_n_f/script.py

'''
>> 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))