cig/unleash/unleash.py

'''

@author: olivier.massot, oct. 2019
'''
import heapq
import sys
import time


# TODO
# * poser les mines de préférence sur des emplacements qui sont sous radar ennemi
# * si une case est suspectée d'abriter un radar, regarder s'il se passe 3 tours sans que les ennemis y creuse. Si c'est le cas, baisser l'intérêt de toutes ces cases 
# * prevoir le mouvements suivant lors du retour au qg


debug = True
verbose_input = False

t0 = time.time()

def log(*msg):
    if debug:
        print("{} - ".format(str(time.time() - t0)[1:5]), *msg, file=sys.stderr)
        sys.stderr.flush()

def input_():
    s = input()
    if verbose_input:
        log("I>", s)
    return s

# OWNER
ME = 0
OPPONENT = 1

# ENTITIES AND ITEMS
NONE = -1
ROBOT = 0
OPP_ROBOT = 1
RADAR = 2
TRAP = 3
ORE = 4

# PARAMS
COOLDOWN = 5
RADAR_SCOPE = 4
MOVING = 4

class Base():
    def __repr__(self):
        return f"<{self.__class__.__name__}: {self.__dict__}>"

class Queue(Base):
    def __init__(self):
        self.items = []
        self.indices = {}
    
    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):
        
        indice = 0
        if priority in self.indices:
            indice = self.indices[priority] + 1
            
        self.indices[priority] = indice
        self.put(item, (priority, indice))

    def get(self):
        return heapq.heappop(self.items)[1]

    @classmethod
    def from_iter(cls, iterable):
        q = cls()
        for item, p in iterable:
            q.fput(item, p)
        return q
           

class Task(Base):
    def __init__(self, target = None):
        self.target = target

class GoDig(Task):
    pass

class GetOre(Task):
    pass

class BringBackOre(Task):
    pass

class GetRadar(Task):
    pass

class GetTrap(Task):
    pass

class SetRadar(Task):
    pass

class SetTrap(Task):
    pass

class Lure(Task):
    pass

class Dispose(Task):
    pass

class Sabotage(Task):
    pass



class Action(Base):
    def resolve(self, command):
        log(f"  >> {command}")
        print(command)
    
class Wait(Action):
    def resolve(self):
        print("WAIT")
        
class Move(Action):
    def __init__(self, x, y):
        self.x = int(x)
        self.y = int(y)
    
    @property
    def target(self):
        return self.x, self.y
    
    def resolve(self):
        super().resolve(f"MOVE {self.x} {self.y}")

class Dig(Action):
    def __init__(self, x, y):
        self.x = int(x)
        self.y = int(y)
    
    @property
    def target(self):
        return self.x, self.y
    
    def resolve(self):
        super().resolve(f"DIG {self.x} {self.y}")
        
class Request(Action):
    def __init__(self, item):
        self.item = item
        
    def resolve(self):
        super().resolve(f"REQUEST {self.item}")
        
class RequestRadar(Request):
    def __init__(self):
        super().__init__("RADAR")
        
    def resolve(self):
        me.radar_cooldown = COOLDOWN
        super().resolve()
        
class RequestTrap(Request):
    def __init__(self):
        super().__init__("TRAP")
        
    def resolve(self):
        me.trap_cooldown = COOLDOWN
        super().resolve()
        

class Entity(Base):
    def __init__(self, id_, x, y):
        self.id_ = int(id_)
        self.x = int(x)
        self.y = int(y)

    @property
    def pos(self):
        return self.x, self.y

    def update(self, x, y, _):
        self.x = x
        self.y = y

class Radar(Entity):
    def __init__(self, id_, x, y):
        super().__init__(id_, x, y)

class Trap(Entity):
    def __init__(self, id_, x, y):
        super().__init__(id_, x, y)
        self.area = [self.pos] + grid.neighbors(*self.pos, diags = False)

class Ore(Entity):
    def __init__(self, id_, x, y):
        super().__init__(id_, x, y)

class Robot(Entity):
    def __init__(self, id_, x, y, item, owner):
        super().__init__(id_, x, y)
        self.item = item if item != NONE else None
        self.owner = owner
        
        self.has_played = False
        self.moved = False
        self.may_have_item = False
        self.may_have_found_ore_at = None
        self.is_bait = False
        
        self.last_action = None
        self.todo = None
        self.last_task = None

    def update(self, x, y, item):
        
        self.has_played = False
        self.moved = (x, y) != self.pos
        self.last_task = self.todo
        self.todo = None
        
        if not self.owned and not self.ko:
            # try to guess last action
            if self.moved:
                self.last_action = Move(x, y)
            else:
                if self.in_hq():
                    self.last_action = Request("?")
                else:
                    self.last_action = Dig(x, y)
        
            if isinstance(self.last_action, Request):
                # * if is in hq and did not move: may_have_item
                self.may_have_item = True
                log(f"% [Robot {self.id_}] May have item")
                    
            elif isinstance(self.last_action, Move) and x == 0:
                # * If just get in HQ, last may_have_found_ore_at updated as has_ore=true
                if self.may_have_found_ore_at:
                    log(f"% [Robot {self.id_}] May have found ore at: {self.may_have_found_ore_at}")
                    grid.cells[self.may_have_found_ore_at].possibly_ore = True
                    self.may_have_found_ore_at = None
        
            if isinstance(self.last_action, Dig):
                
                if self.may_have_item:
                    # * if not in hq and may_have_item and dig, cell become suspect (and scope with it). may_have_item become false
                    self.may_have_item = False
                
                    may_have_digged = [self.pos] + grid.neighbors(*self.pos)
                    may_have_digged = [c for c in may_have_digged if c[0] > 0]
                    
                    log(f"% [Robot {self.id_}] Suspect cells: {may_have_digged}")
                    for n in may_have_digged:
                        grid.cells[n].suspect = 10
                    
                    grid.cells[self.pos].suspect = 10
                    
                else:
                    # had no item and digged: may have found ore
                    if self.may_have_found_ore_at:
                        grid.cells[self.may_have_found_ore_at].seems_empty = True
                    self.may_have_found_ore_at = self.pos
                    
                    for n in [self.pos] + grid.neighbors(*self.pos):
                        if grid.cells[n].memorized_ore:
                            grid.cells[n].memorized_ore -= 0.2
                            grid.cells[n].suspect -= 2

        if self.owned and not self.ko:
            if isinstance(self.last_action, Dig):
                target = grid.cells[self.last_action.target]
                if item == ORE:
                    target.had_ore = True
                    target.memorized_ore -= 1
                else:
                    target.dry = True
                    target.memorized_ore = 0
                    if target.new_hole:
                        target.was_empty = True
                target.suspect = 0
            
        self.x = x
        self.y = y
        self.item = item if item != NONE else None
        
        if self.ko:
            self.todo = None
        
    @property
    def owned(self):
        return self.owner == ME

    @property
    def ko(self):
        return self.x < 0

    def in_hq(self):
        return self.x == 0
    
    def next_to_hq(self):
        return self.x <= 1

    @property
    def hold_radar(self):
        return self.item == RADAR

    @property
    def hold_trap(self):
        return self.item == TRAP

    @property
    def hold_ore(self):
        return self.item == ORE

    def go_to(self, pos, around_ok=True):
        
        if around_ok:
            # best position to interact with the target cell (ie: the less dangerous)
            pos = min([pos] + grid.neighbors(*pos), key=lambda c: (grid.cells[c].moving_cost(), grid.distance(self.pos, c)))
            log(f"  (best position for action: {pos})")
            
        path = grid.path(self.pos, pos)
        if path:
            log(f"Path: {path}")
            new_pos = path[0]
            self.x, self.y = new_pos
        else:
            new_pos = pos
            log("<!!> No path found")
        
        for n in grid.scope2[new_pos]:
            grid.cells[n].ally_near = True
            
        self.move(*new_pos)
        
    def go_back_to_hq(self):
        self.current_digging_target = None
        c = grid.closest(self.pos, grid.hq)
        self.go_to(c, around_ok=False)
        

    def digging_queue(self):
        q = Queue()

        last_target = None
        if type(self.last_task) in (GoDig, GetOre):
            last_target = self.last_task.target

        for c, cell in grid.cells.items():
            if cell.dry or cell.is_hq or cell.has_trap or cell.suspect:
                continue
            if cell.under_radar and not cell.ore:
                continue # we know there is nothing here
            
            p = 0
            
            p += ((4 * grid.moving_distance(self.pos, c) + c[0]) // 2) # mean between dist to robot and dist to hq
            p -= max(cell.interest, 30)
            
            if c == last_target:
                p -= 3 # avoid hesitations
            
            q.put(c, p)

        return q

    def best_to_dig(self):
        try:
            return self.digging_queue().get()
        except IndexError:
            return None
        
    def radar_positioning_queue(self):
        q = Queue()

        last_target = None
        if type(self.last_task) is SetRadar:
            last_target = self.last_task.target

        for c, cell in grid.cells.items():
            if cell.is_hq or cell.under_radar or cell.has_trap or cell.suspect:
                continue
            
            p = 0
            p += ((4 * grid.moving_distance(self.pos, c) + c[0]) // 2)
            p -= cell.interest
            
            if x in (5, 8, 11, 14, 18, 22, 26) and 2 <= y <= 12:
                p -= 10
            if y in (3, 7, 11) and 5 <= x <= 26:
                p -= 10
                
            for c2 in grid.scope4[c]:
                other = grid.cells[c2]
                if not (other.dry or other.discovered or other.is_hq or other.has_trap):
                    p -= 1
            
            if c[0] < 5:
                p += 20
            
            if cell.ore: # one stone two birds: we can take the ore while setting the radar
                p -= 2
                
            if c == last_target:
                p -= 3 # avoid hesitations
            
            q.put(c, p)
            
        return q
    
    def best_for_radar(self):
        
        try:
            return self.radar_positioning_queue().get()
        except IndexError:
            grid.no_more_radar = True
            return None

    def trap_positioning_queue(self):
        q = Queue()
        
        last_target = None
        if type(self.last_task) is SetTrap:
            last_target = self.last_task.target

        for c, cell in grid.cells.items():
            if cell.is_hq or cell.has_trap or cell.suspect:
                continue
            
            if cell.scarecrow: # this cell should already have become suspect to ennemy
                continue
            
            p = 0
            p += ((4 * grid.moving_distance(self.pos, c) + c[0]) // 2)
            p -= cell.interest
            
            if cell.ore == 2:
                p -= 30
            elif cell.ore or cell.possibly_ore or cell.memorized_ore:
                p -= 10
            
            if any(r.pos in grid.scope2[c] for r in me.robots):
                p += 5
            
            if c == last_target:
                p -= 5 # avoid hesitations
            
            q.put(c, p)
        return q
            
    def best_for_trap(self):
        try:
            return self.trap_positioning_queue().get()
        except IndexError:
            return None
        
    def dispose(self):
        # dispose of the current item in the fisrt place available
        q = Queue()
        for c, cell in grid.cells.items():
            if cell.is_hq or cell.under_trap or cell.ore:
                continue
            p = 0
            p += 3 * grid.manhattan(self.pos, c)
                
            q.put(c, p)
            
        target = q.get()
        log(f"Dispose of item {self.item} at {target}")
        self.go_dig(target)
    
    def go_set_radar(self, pos):
        self.go_dig(pos)
    
    def go_set_trap(self, pos):
        self.go_dig(pos)
    
    def go_dig(self, pos):
        if pos == self.pos or pos in grid.neighbors(*self.pos):
            if self.item == TRAP:
                grid.cells[pos].has_trap = True
                grid.cells[pos].under_trap = True
            self.dig(*pos)
        else:
            self.go_to(pos)

    def collateral_for(self, trap):
        area = grid.collateral_area_for(trap.pos)
        return [e for e in self.entities if isinstance(e, Robot) and e.pos in area]
        
    # commands
    def _act(self, action):
        self.has_played = True
        self.last_action = action
        action.resolve()

    def wait(self):
        self._act(Wait())

    def move(self, x, y):
        self._act(Move(x, y))

    def dig(self, x, y):
        self._act(Dig(x, y))
        
        if self.is_bait:
            grid.cells[(x, y)].scarecrow = True
        self.is_bait = False

    def request(self, item):
        self._act(Request(item))
        
    def request_radar(self):
        me.radar_cooldown = COOLDOWN
        self._act(RequestRadar())
        
    def request_trap(self):
        me.trap_cooldown = COOLDOWN
        self._act(RequestTrap())

class Team():
    def __init__(self, player):
        self.player = player
        self.score = 0
        self.robots = []
        
        self.radar_cooldown = None
        self.trap_cooldown = None

    def update(self, entities):
        self.robots = sorted([e for e in entities if isinstance(e, Robot) and e.owner == self.player], key= lambda r: r.id_)
        
    def active_robots(self):
        return [r for r in self.robots if not r.ko]
        
class Cell():
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.ore = 0
        self.hole = 0
        
        self.had_ore = False
        self.suspect = 0
        self.possibly_ore = False
        self.new_hole = False
        self.dry = False
        self.scarecrow = False
        self.seems_empty = False
        self.was_empty = False
        self.available_ore = 0
        self.memorized_ore = 0
        self.under_radar = False
        self.discovered = False
        self.ally_near = False
        
    @property
    def pos(self):
        return self.x, self.y
    
    @property
    def is_hq(self):
        return self.x == 0
    
    def print_state(self):
        if not self.hole and not self.under_radar:
            return '?'
        elif self.has_radar:
            return 'R'
        elif self.has_trap:
            return 'T'
        elif self.had_ore:
            return '1'
        elif self.possibly_ore:
            return '*'
        else:
            return '0'

    def update(self, ore, hole):
        
        self.new_hole = hole and not self.hole
        
        if self.under_radar and self.ore:
            self.memorized_ore = self.ore
        if self.under_radar:
            self.discovered = True
        
        self.ore = int(ore) if ore != '?' else None
        self.hole = (int(hole) == 1)
        
        if self.ore:
            self.had_ore = True
        
        self.interest = 0
        self.tokens = 0
        self.has_radar = False
        self.under_radar = False
        self.has_trap = False
        self.under_trap = False
        self.occupied = False
        self.under_suspect = False
        self.ennemy_near = False
        
    def moving_cost(self):
        if self.has_trap:
            return 15 + 10 * self.ennemy_near + 5 * self.ally_near
        if self.under_trap or self.suspect:
            return 10 + 10 * self.ennemy_near + 5 * self.ally_near
        elif self.under_suspect:
            return 10 + 5 * self.ennemy_near + 5 * self.ally_near
        return 10

    def may_have_ore(self):
        return self.ore or self.memorized_ore or self.possibly_ore

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):
    w = 30
    h = 15
    
    def __init__(self):
        self.cells = {(x, y): Cell(x, y) for x in range(Grid.w) for y in range(Grid.h)}
        self.hq = [(0, y) for y in range(Grid.h)]
        self.scope2 = {c: self.zone(c, 2) for c in self.cells}
        self.scope3 = {c: self.zone(c, 3) for c in self.cells}
        self.scope4 = {c: self.zone(c, 4) for c in self.cells}
        self.dscope4 = {c: self.dzone(c, 4) for c in self.cells}
        self.scope5 = {c: self.zone(c, 5) for c in self.cells}
        self.entities = {}
        self.at = {}
        
        self.no_more_radar = False
        
    @property
    def grid(self):
        return [[self.cells[(x, y)] for x in range(Grid.w)] for y in range(Grid.h)]
        
    def print_grid(self, key=None):
        if key is None:
            key = lambda x: x
        return "\n"+ "\n".join(["".join([f"{key(c)}|" for c in row]) for row in self.grid])
        
    def update(self, edata):
        
        new_entities = {}
        just_destroyed = []
        
        for e in edata:
            id_, type_, x, y, item = e
            
            if id_ in self.entities:
                e = self.entities[id_]
                
                if e.x > 0 and x < 0:
                    just_destroyed.append(id_)
                
                e.update(x, y, item)
                new_entities[id_] = e
            else:
                if type_ == ROBOT:
                    e = Robot(id_, x, y, item, ME)
                elif type_ == OPP_ROBOT:
                    e = Robot(id_, x, y, item, OPPONENT)
                elif type_ == RADAR:
                    e = Radar(id_, x, y)
                elif type_ == TRAP:
                    e = Trap(id_, x, y)
                new_entities[id_] = e
                
        # exploded mines
        exploded = [e.pos for id_, e in self.entities.items() if type(e) is Trap and not id_ in new_entities]
        for id_, e in self.entities.items():
            if type(e) is Robot and e.owned and id_ in just_destroyed:
                # this robot was just destroyed
                if isinstance(e.last_action, Dig):
                    exploded.append(e.last_action.target)
        
        self.entities = new_entities
        
        # indexes
        self.at = {c: [e for e in self.entities.values() if e.pos == c] for c in self.cells}
    
        # update cells states
        for e in new_entities.values():
            if isinstance(e, Radar):
                self.cells[e.pos].has_radar = True
                for c in self.scope4[e.pos]:
                    self.cells[c].under_radar = True
                    self.cells[c].possibly_ore = False
                    if not self.cells[c].ore:
                        self.cells[c].memorized_ore = 0
                    
            if isinstance(e, Trap):
                self.cells[e.pos].has_trap = True
                for c in e.area:
                    self.cells[c].under_trap = True
    
            if isinstance(e, Robot):
                if e.ko:
                    continue
                self.cells[e.pos].occupied = True
                
                if e.owner == OPPONENT:
                    for c in self.scope5[e.pos]:
                        self.ennemy_near = True
                
        # interest of undiscovered cells
        for c, cell in self.cells.items():
            cell.available_ore = cell.ore or int(not cell.under_radar and cell.had_ore and not cell.dry)
            
        for c, cell in self.cells.items():
            
            suspection = cell.suspect * (((200 - round_) // 50) + 1)
            
            if cell.ore:
                cell.interest = 40 - suspection
            
            elif int(cell.memorized_ore):
                cell.interest = 20 - suspection
            
            else:
                for x, y, d in grid.dscope4[c]:
                    other = grid.cells[(x, y)]
                    di = (5 - d)
                    if other.had_ore or other.possibly_ore:
                        cell.interest += di
                    if x == 0:
                        cell.interest -= di # move away from HQ a little
                    if y == 0 or y == (grid.h - 1):
                        cell.interest -= 2 # counterbalance the advantage of border cells
                    if other.was_empty or other.seems_empty:
                        cell.interest -= di # this was an empty cell
                cell.interest //= 4
                            
                if x < 8 and round_ < 20: # 8th row seems the best to start
                    cell.interest -= abs(8 - x)
        
                if cell.available_ore:
                    cell.interest += 10
                
            if cell.suspect:
                for c2 in self.neighbors(*c):
                    grid.cells[c2].under_suspect = True
    
        for pos in exploded:
            log(f"Trap exploded at {pos}, cells around no longer suspects")
            for c in [pos] + self.neighbors(*pos):
                self.cells[c].suspect = 0
    
        me.update(new_entities.values())
        opponent.update(new_entities.values())
    
    def available_ore(self):
        return any(c.available_ore for c in self.cells.values())
    
    def is_radar_needed(self):
        if grid.no_more_radar:
            return False
        discovered = sum([cell.ore for cell in self.cells.values() if cell.discovered and cell.ore and not cell.suspect and not cell.has_trap])
        robots_alive = len([r for r in me.robots if not r.ko])
        if discovered > 4 * robots_alive:
            return False
        return True
    
    @staticmethod
    def manhattan(from_, to_):
        xa, ya = from_
        xb, yb = to_
        return abs(xa - xb) + abs(ya - yb) 

    @staticmethod
    def distance(from_, to_): # alias
        return Grid.manhattan(from_, to_)
    
    @staticmethod
    def moving_distance(from_, to_):
        q, r = divmod(max(0, Grid.manhattan(from_, to_) - 1), MOVING)
        return q + int(bool(r))
    
    def neighbors(self, x, y, diags=False, inside_only=True):
        n = [(x, y - 1), (x - 1, y), (x + 1, y), (x, y + 1)]
        if diags:
            n += [(x - 1, y - 1), (x + 1, y - 1), (x - 1, y + 1), (x + 1, y + 1)]
        if inside_only:
            n = [(x, y) for x, y in n if 0 <= x < Grid.w and 0 <= y < Grid.h]
        return n
    
    @classmethod
    def zone(cls, center, radius):
        return [(x, y) for x in range(0, cls.w) for y in range(0, cls.h) if cls.manhattan(center, (x, y)) <= radius]      
    
    @classmethod
    def dzone(cls, center, radius):
        z = []
        for y in range(0, cls.h):
            for x in range(0, cls.w):
                d = cls.manhattan(center, (x, y))
                if d <= radius:
                    z.append((x, y, d))
        return z
                    
    def collateral_area_for(self, trap_pos, current=None):
        area = {trap_pos}
        for n in self.neighbors(*trap_pos):
            if current and n in current:
                continue
            area.add(n)
            if self.cells[n].has_trap:
                area |= self.collateral_area_for(n, area)
        return area
    
    @staticmethod
    def closest(from_, in_):
        return min(in_, key=lambda x: Grid.manhattan(from_, x))
    
    def path(self, start, target):
        nodes = Queue()
        its, break_on = 0, 4000
        
        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.scope4[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)]
                moving_cost = cell.moving_cost()
                    
                if moving_cost < 0:
                    continue
                    
                cost = current.cost + moving_cost
                priority = cost + 5 * Grid.manhattan((x, y), target)
                
                node = PathNode(x, y, current)
                node.cost = cost
                nodes.put(node, priority)
                
        return None
    
    
Grid.w, Grid.h = [int(i) for i in input_().split()]

grid = Grid()
me = Team(ME)
opponent = Team(OPPONENT)
round_ = 0

while True:
    round_ += 1
    # get scores
    me.score, opponent.score = [int(i) for i in input_().split()]
    log("# Get new data")
    # get cells data
    for y in range(Grid.h):
        s = input_().split()
        data = list(zip(s[::2], s[1::2]))
        for x, args in enumerate(data):
            grid.cells[(x, y)].update(*args)
    
    # various data
    n, me.radar_cooldown, me.trap_cooldown = [int(i) for i in input_().split()]
#     log("Cooldown: ", me.radar_cooldown, me.trap_cooldown)
    
    # entities data
    e_data = [(int(j) for j in input_().split()) for i in range(n)]
    
    grid.update(e_data)
#     log("Entities: ", grid.entities)
    
#     log(grid.print_grid(key=lambda c: "{}".format("x" if c.suspect else "_")))
#     log(grid.print_grid(key=lambda c: c.print_state()))
    
    ## attributing tasks
    # Predefined tasks
    log("# Attribute task")
    get_radar_affected = False
    get_trap_affected = False
    sabotage_at = []
    
    for r in me.active_robots():
    
        if r.hold_radar:
            target = r.best_for_radar()
            
            if target:
                r.todo = SetRadar(target)
                grid.cells[target].tokens += 1
            else:
                log(f"  <!> No place found for the radar, dispose")
                r.todo = Dispose()
            
        elif r.hold_trap:
            target = r.best_for_trap()
    
            if target:
                r.todo = SetTrap(target)
                grid.cells[target].tokens += 1
            else:
                log(f"  <!> No place found for the trap, dispose")
                r.todo = Dispose()
    
        elif r.hold_ore:
            r.todo = BringBackOre()
            
        elif me.radar_cooldown == 0 and not get_radar_affected and (r.next_to_hq() or not grid.available_ore()):
            if grid.is_radar_needed():
                r.todo = GetRadar()
                get_radar_affected = True
            else:
                log("  * No radar needed at this time")
            
#         elif me.trap_cooldown == 0 and r.in_hq() and round_ < 170 and not get_trap_affected:
#             r.todo = GetTrap()
#             get_trap_affected = True
#         
#         elif r.in_hq() and round_ < 150 and not isinstance(r.last_action, Wait) and random.randint(1,3) == 2:
#             r.todo = Lure()
            
        else:
            for c in [r.pos] + grid.neighbors(*r.pos):
                cell = grid.cells[c]
                if (cell.suspect and cell.may_have_ore()) or cell.has_trap and not c in sabotage_at:
                    collateral_area = grid.collateral_area_for(c)
                    allies_victims = [r_ for r_ in me.robots if r_.pos in collateral_area]
                    opponent_victims = [r_ for r_ in opponent.robots if r_.pos in collateral_area]
                    
                    if len(opponent_victims) > len(allies_victims) or (cell.suspect and len(opponent_victims) == len(allies_victims)):
                        r.todo = Sabotage(c)
                        sabotage_at.append(c)
                        log(f"Going for sabotage at {c}, area: {len(collateral_area)}, allies: {[x.id_ for x in allies_victims]}, ennemies: {[x.id_ for x in opponent_victims]}")
                        break

    # To-Priorize tasks
    task_queue = Queue()
    
    # exploration
    for r in me.active_robots():
        for c, cell in grid.cells.items():
            if cell.dry or cell.is_hq or cell.has_trap:
                continue
            if cell.under_radar and not cell.ore:
                continue # we know there is nothing here
            
            if cell.ore or int(cell.memorized_ore):
                task_queue.fput((r, GetOre(c)), grid.distance(r.pos, c) - cell.interest)
            else:
                task_queue.fput((r, GoDig(c)), grid.distance(r.pos, c) - cell.interest)
    
    while any(r.todo is None for r in me.robots if not r.ko):
        try:
            r, task = task_queue.get()
        except IndexError:
            log("<!> Not enough task for everyone")
            break

        if r.todo:
            continue

        cell = grid.cells[task.target]
        if isinstance(task, GetOre) and cell.tokens >= cell.available_ore:
            continue

        r.todo = task
        cell.tokens += 1

    log("# Execution")
             
    for r in me.robots:
        
        log(f"** Robot {r.id_} [{r.pos}] plays (has item: {r.item})")
        if r.ko:
            log(" -- KO --")
            r.wait()
            continue
        
        log(f"> Task: {r.todo}")
        
        if type(r.todo) is GetRadar:
            log(f"  Go get a radar at HQ")
            if r.in_hq():
                r.request_radar()
            else:
                r.go_back_to_hq()
                    
        elif type(r.todo) is GetTrap:
            log(f"  Go get a trap at HQ")
            if r.in_hq():
                r.request_trap()
            else:
                r.go_back_to_hq()
            
        elif type(r.todo) is BringBackOre:
            log("  Bring back ore to HQ")
            r.go_back_to_hq()
            
        elif type(r.todo) is Lure:
            log("  $ Wait to trick")
            r.is_bait = True
            r.wait()
                
        elif type(r.todo) is GetOre:
            log(f"  Go get ore at {r.todo.target}")
            r.go_dig(r.todo.target)
            
        elif type(r.todo) is GoDig:
            log(f"  Go dig at {r.todo.target}")
            r.go_dig(r.todo.target)
            
        elif type(r.todo) is SetRadar:
            log(f"  Go set a radar at {r.todo.target}")
            r.go_set_radar(r.todo.target)
            
        elif type(r.todo) is SetTrap:
            log(f"  Go set a trap at {r.todo.target}")
            r.go_set_trap(r.todo.target)
            
        elif type(r.todo) is Dispose:
            log(f"  Dispose of item")
            r.dispose()
            
        elif type(r.todo) is Sabotage:
            log(f"  Sabotage at {r.todo.target}")
            r.go_dig(r.todo.target)
            
        else:
            log("  <!> No task (or unknown)")

        
        if not r.has_played:
            log("  <!> Has not played")
            r.wait()