codeingame/caribbean/script.py

'''

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


# TODO:
# * find a way to change direction without slowing down if possible
# * Try to integer extra steps into the path algo, instead of adding independents paths
# * Increase the shooting rate in the second part of the game (no barrels left)
# * get_shooting_spots: try to intercept ennemy
# * make a difference between moving cost, mines, cannonballs, out of grid and other ships
# * Try to temporize when taking barrel, the more the ship can wait the better
# * try to cut the road to ennemies when getting barrels
# * if an ennemy has more rum that every owned ship: hunt!

# Enhancements
# * interception trajectories
# * paths with extra-steps
# * Part 1: Speed up
# * Part 2: Increase shooting rate

debug = True

t0 = time.time()

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

current_turn = 0

class Queue():
    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]

    @classmethod
    def merge(cls, *args, reverse=False):
        q = cls()
        q.items = list(heapq.merge(*[a.items for a in args], key=lambda x: x[1], reverse=reverse))
        return q

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)
    
    @classmethod
    def merge(cls, *args, reverse=False):
        q = cls()
        q.items = list(heapq.merge(*[a.items for a in args], reverse=reverse))
        return q
    
class ObjectivesQueue(InterestQueue):
    
    @classmethod
    def re_eval(cls, q, pos=None, d=None):
        new_q = cls()
        while q:
            o = q.get()
            o.eval(pos, d)
            new_q.put(o)
        return new_q
    
class Base():
    def __repr__(self):
        return f"<{self.__class__.__name__}: {self.__dict__}>"



class BaseObjective(Base):
    def __init__(self, target):
        self.target = target
        self.interest = 0

    def __lt__(self, other):
        return self.interest < other.interest

    def __repr__(self):
        return f"<{self.__class__.__name__}: target={self.target.id};int={self.interest})>"

    def _pre_eval(self, pos = None, d = None):
        self.distance = Grid.manhattan(pos, self.target.pos) if pos is not None else 0
        self.alignment = abs(Grid.diff_directions(Grid.direction_to(*pos, *self.target.pos), d)) if d is not None else 0
        
    def eval(self, pos = None, d = None):
        self._pre_eval(pos, d)
        self._compute_interest()
        
    def _compute_interest(self):
        self.interest = 7 * self.distance + 3 * self.alignment
        
class GetBarrel(BaseObjective):
    
    def _pre_eval(self, pos = None, d = None):
        super()._pre_eval(pos, d)
        self.ennemy_near = any(Grid.manhattan(e.next_pos, self.target.pos) < self.distance for e in grid.ennemy_ships)
    
    def _compute_interest(self):
        self.interest = 6 * self.distance + 9 * self.alignment + 3 * self.target.dispersal + self.target.mine_threat * 2 + 12 * self.ennemy_near
        if self.distance <= 2 and self.alignment > 1:
            # dead angle
            self.interest += 36

class Attack(BaseObjective):
    def _compute_interest(self):
        self.interest = 7 * self.distance + 3 * self.alignment + self.target.stock // 4 - 20 * self.target.blocked_since

class PathNode(tuple):
    def __new__(self, x, y, parent=None):
        n = tuple.__new__(self, (x, y))
        n.parent = parent
        n.cost = 0
        n.orientation = 0
        return n
    
    def __repr__(self):
        return f"<{self[0]}, {self[1]}, c:{self.cost}, o:{self.orientation}>"

class Grid(Base):
    w = 23
    h = 21
    _neighbors = {}
    _next_cell = {}
        
    def __init__(self):
        self.load_entities({})
        
    @classmethod
    def preload(cls):
        cls._neighbors = {}
        for x in range(-1, cls.w + 1):
            for y in range(-1, cls.h + 1):
                cls.cache_neighbors(x, y)
                
        cls._next_cell = {}
        for x in range(0, cls.w):
            for y in range(0, cls.h):
                cls.cache_next_cell(x, y)
                
        for x in range(0, cls.w):
            for y in range(0, cls.h):
                Ship.cache_area(x, y)
    
    @classmethod
    def contains(cls, x, y):
        return 0 <= x < cls.w and 0 <= y < cls.h 
    
    def __contains__(self, key):
        return self.contains(*key)

    def __iter__(self):
        for item in ((x, y) for x in range(self.w) for y in range(self.h)):
            yield item

    # data
    
    def load_entities(self, entities):
        
        # special: mines too far from ships are not recorded but still exist
        ghost_mines = []
        if hasattr(self, "mines"):
            for m in self.mines:
                if not m.id in entities:
                    if all((self.manhattan(m.pos, ship.pos) > 5) for ship in self.owned_ships):
                        m.ghost = True
                        ghost_mines.append(m)

        self.entities = entities
        self.index = {}
        self.ships = []
        self.owned_ships = []
        self.ennemy_ships = []
        self.ships = []
        self.barrels = []
        self.mines = []
        self.cannonballs = []
        
        self.threat = {}
        
        for e in list(entities.values()) + ghost_mines:
            self.index[e.pos] = e
            type_ = type(e)
            
            if type_ is Ship:
                self.ships.append(e)
                if e.owned:
                    self.owned_ships.append(e)
                else:
                    self.ennemy_ships.append(e)

            elif type_ is Barrel:
                self.barrels.append(e)

            elif type_ is Mine:
                self.mines.append(e)

            elif type_ is Cannonball:
                self.cannonballs.append(e)
                if not e.pos in self.threat or e.countdown < self.threat[e.pos]:
                    self.threat[e.pos] = e.countdown
                
        for s in self.owned_ships:
            s.allies = [other for other in self.owned_ships if other is not s]
        for s in self.ennemy_ships:
            s.allies = [other for other in self.ennemy_ships if other is not s]

        for s in self.ships:
            s.next_pos_proba(2)

        self.next_to_mine = {}
        for m in self.mines:
            for n in self.neighbors(*m.pos):
                self.next_to_mine[n] = m

        self.next_to_barrel = {}
        for b in self.barrels:
            for n in self.neighbors(*b.pos):
                self.next_to_barrel[n] = b

        self.update_moving_costs()
        
        grav_center = self.barrels_gravity_center()
        for b in self.barrels:
            b.dispersal = Grid.manhattan(grav_center, b.pos) if grav_center != None else 0
            b.mine_threat = any(type(self.at(*c)) is Mine for c in self.neighbors(*b.pos))
                
        for s in self.owned_ships:
            
            s._can_move = {c: (s.moving_cost(*c) < 1000) 
                           for c in [s.front, s.front_left, s.left, s.front_right,
                                     s.right, s.back_left, s.back_right]}
            
            s.objectives = ObjectivesQueue()
            s.ennemies = ObjectivesQueue()
            
            for b in self.barrels:
                obj = GetBarrel(b)
                obj.eval(s.prow, s.orientation)
                s.objectives.put(obj)
                
            for e in self.ennemy_ships:
                obj = Attack(e)
                obj.eval(s.pos, s.orientation)
                s.ennemies.put(obj)
        
    def at(self, x, y):
        try:
            return self.index[(x, y)]
        except KeyError:
            return None
        
    @classmethod
    def is_border(cls, x, y):
        return x == -1 or y == -1 or x == cls.w or y == cls.h
        
    def collision_at(self, x, y):
        e = self.at(x, y)
        return type(e) in [Mine, Ship, Cannonball] or not (x, y) in self.__iter__()
        
    def barrels_gravity_center(self):
        wx, wy, wtotal = 0,0,0
        for b in self.barrels:
            wx += (b.x * b.amount) 
            wy += (b.y * b.amount)
            wtotal += b.amount
        return (wx // wtotal, wy // wtotal) if wtotal else None

    def update_moving_costs(self):
        base_costs = {}
        self.collisions = []
        
        for x in range(-1, self.w + 1):
            for y in range(-1, self.h + 1):
                base_costs[(x, y)] = 10 # base moving cost
                
        for x, y in base_costs:
            if x in (-1, self.w + 1) or y in (-1, self.h):
                base_costs[(x, y)] = 1000 # out of the map
            elif x in (0, self.w - 1) or y in (0, self.h - 1):
                base_costs[(x, y)] = 15 # borders are a little more expensive     
        
        for c in self.next_to_mine:
            base_costs[c] += 30
        for m in self.mines:
            base_costs[m.pos] += 1000
            
            if m.pos in self.threat:
                if self.threat[m.pos] <= 2:
                    # avoid the area of a mines going to explode
                    for n in self.neighbors(*m.pos):
                        base_costs[n] += 1000
                        
        for c in self.cannonballs:
            if 0 < c.countdown <= 2:
                base_costs[c.pos] += 1000
                
        for ship in self.ships:
            ship._moving_costs = {}
            ship._moving_costs.update(base_costs)
            for other in self.ships:
                if other is ship:
                    continue
                dist = self.manhattan(ship.pos, other.pos)
                if dist > 6:
                    continue
                for c in self.zone(other.pos, 3):
                    ship._moving_costs[c] += 25
                
                next_positions = other.next_pos_proba()
                for c, proba in next_positions[1].items():
                    if proba >= 20:
                        ship._moving_costs[c] = ship._moving_costs.get(c, 0) + 20 * proba
                if ship.owned and not other.owned and other.behind in ship._moving_costs:
                    # the other ship could mine
                    ship._moving_costs[other.behind] += 100

    def shooting_spot(self, ship, target, current=None):
        shooting_spots = Queue()
        target_pos = target.next_pos if type(target) is Ship else target.pos
        
        for x, y in self.zone(target_pos, 8):
            if ship.moving_cost(x, y) > 100:
                continue
            if self.manhattan((x, y), target_pos) <= 2:
                continue
            
            interest = 0 # the lower the better
            
            if (x, y) == current:
                interest -= 20
            
            interest += ship.moving_cost(x, y)
            
            # avoid cells too close from borders
            if not 3 < x < (self.w - 3):
                interest += 50
            if not 3 <= y < (self.h - 3):
                interest += 50
            
            # priorize cells in the current direction
            diff = abs(Grid.diff_directions(ship.orientation, Grid.direction_to(*ship.prow, x, y)))
            interest += 10 * abs(diff)
            
            # priorize spots at distance 6 from active ship
            interest += (10 * abs(6 - self.manhattan((x, y), ship.pos)))
            
            # priorize spots at distance 6 from targetted ship
            interest += (10 * abs(6 - self.manhattan((x, y), target.pos)))
            
            shooting_spots.put((x, y), interest)
        return shooting_spots.get()
    
    def runaway_spot(self, ship):
        runaway_spot = Queue()
        
        for x, y in iter(self):
            if ship.moving_cost(x, y) > 100:
                continue
            
            interest = 0 # the lower the better
            
            interest += ship.moving_cost(x, y)
            
            # avoid cells too close from borders
            if not 3 < x < (self.w - 3):
                interest += 70
            if not 3 <= y < (self.h - 3):
                interest += 70
            
            # priorize cells in the current direction
            diff = abs(Grid.diff_directions(ship.orientation, Grid.direction_to(*ship.prow, x, y)))
            interest += 20 * abs(diff)
            
            # priorize spots at distance 6 from active ship
            interest += (20 * abs(6 - self.manhattan((x, y), ship.pos)))
            
            # max distance from ennemies
            interest -= (10 * min([Grid.manhattan((x, y), e.next_pos) for e in self.ennemy_ships]))
            
            runaway_spot.put((x, y), interest)
        return runaway_spot.get()
    
    # geometrical algorithms
    @staticmethod
    def from_cubic(xu, yu, zu):
        return (zu, int(xu + (zu - (zu & 1)) / 2))

    @staticmethod
    def to_cubic(x, y):
        zu = x
        xu = int(y - (x - (x & 1)) / 2)
        yu = int(-xu - zu)
        return (xu, yu, zu)

    @staticmethod
    def manhattan(from_, to_):
        xa, ya = from_
        xb, yb = to_
        return abs(xa - xb) + abs(ya - yb) 
    
    @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]      

    @staticmethod
    def closest(from_, in_):
        return min(in_, key=lambda x: Grid.manhattan(from_, x.pos))

    @staticmethod
    def directions(y):
        if y % 2 == 0:
            return [(1, 0), (0, -1), (-1, -1), (-1, 0), (-1, 1), (0, 1)]
        else:
            return [(1, 0), (1,-1), (0,-1), (-1, 0), (0, 1), (1, 1)]

    @staticmethod
    def direction_to(x0, y0, x, y):
        dx, dy = (x - x0), (y - y0)
        if dx > 0:
            if dy == 0:
                return 0
            elif dy > 0:
                return 5
            else:
                return 1
        elif dx < 0:
            if dy == 0:
                return 3
            elif dy > 0:
                return 4
            else:
                return 2
        else:
            if dy > 0:
                return 5 if y0 % 2 == 0 else 4
            else:
                return 1 if y0 % 2 == 0 else 2

    @staticmethod
    def add_directions(d1, d2):
        d = d2 + d1
        if d < 0:
            d += 6
        elif d > 5:
            d -= 6
        return d
    
    @staticmethod
    def diff_directions(d1, d2):
        d = d2 - d1
        if d <= -3:
            d += 6
        elif d > 3:
            d -= 6
        return d
    
#     @staticmethod
#     def next_cell(x, y, d, repeat=1):
#         for _ in range(repeat):
#             dx, dy = Grid.directions(y)[d]
#             x, y = x + dx, y + dy
#         return x, y
    
    @staticmethod
    def symetry(d):
        return d + 3 if d < 3 else d - 3
    
    @staticmethod
    def abs_neighbors(x, y):
        return ((x + dx, y + dy) for dx, dy in Grid.directions(y))
    
    @classmethod
    def cache_neighbors(cls, xc, yc):
        cls._neighbors[(xc, yc)] = [(x, y) for x, y in Grid.abs_neighbors(xc, yc) if 0 <= x < cls.w and 0 <= y < cls.h]

    @classmethod
    def neighbors(cls, x, y):
        try:
            return cls._neighbors[(x, y)]
        except KeyError:
            cls.cache_neighbors(x, y)
            return cls._neighbors[(x, y)]
    
    @classmethod
    def abs_next_cell(cls, x, y, d):
        dx, dy = Grid.directions(y)[d]
        return x + dx, y + dy
            
    @classmethod
    def cache_next_cell(cls, x, y):
        for d, dv in enumerate(Grid.directions(y)):
            dx, dy = dv
            cls._next_cell[(x, y, d)] = (x + dx, y + dy)

    @classmethod
    def next_cell(cls, x, y, d, repeat=1):
        for _ in range(repeat):
            try:
                x, y = cls._next_cell[(x, y, d)]
            except KeyError:
                x, y = cls.abs_next_cell(x, y, d)
        return x, y
    
    def rotate(self, center, coordinates, rotations):
        if coordinates == [center] or rotations % 6 == 0:
            return coordinates
        x0, y0 = center
        xu0, yu0, zu0 = self.to_cubic(x0, y0)
        result = []

        for x, y in coordinates:
            xu, yu, zu = self.to_cubic(x, y)
            dxu, dyu, dzu = xu - xu0, yu - yu0, zu - zu0
            for _ in range(rotations):
                dxu, dyu, dzu = -dzu, -dxu, -dyu
            xru, yru, zru = dxu + xu0, dyu + yu0, dzu + zu0
            xr, yr = self.from_cubic(xru, yru, zru)
            result.append((xr, yr))
        return result

    # pathfinding
    def path(self, start, start_d, target, moving_costs={}, inertia=None, incl_start=False, limit=10000):
        nodes = Queue()
        break_on, iteration = limit, 0
        broken = False
        
        effective_start = start
        origin = PathNode(*effective_start)
        origin.orientation = start_d
        
        if inertia is not None:
            for _ in range(inertia):
                effective_start = self.next_cell(*effective_start, start_d)
                origin = PathNode(*effective_start, origin)
                origin.orientation = start_d
        
        nodes.put(origin, 0)
        
        neighbors = []

        while nodes:
            current = nodes.get()

            if broken or current == target:
                
                path = []
                previous = current
                while previous:
                    if previous != start or incl_start:
                        path.insert(0, previous)
                    previous = previous.parent
                return path, iteration

            neighbors = self.neighbors(*current)

            for x, y in neighbors:
                
                if (x, y) == current.parent:
                    continue

                iteration += 1
                if break_on > 0 and iteration >= break_on:
                    broken = True
                
                moving_cost = moving_costs.get((x, y), 1000)
                if moving_cost >= 1000:
                    continue
                
                d = Grid.direction_to(*current, x, y)
                if inertia == 0:
                    # special: if started with speed 0, first move will require a speed_up, 
                    # making impossible a direction change at first node
                    if current.parent and current.parent == start and d != current.orientation:
                        continue
                
                diff = abs(Grid.diff_directions(current.orientation, d))
                if diff > 1:
                    # change direction one degree at a time
                    if current == (11,9) and (x, y) == (12,10): log("d")
                    continue
                    
                area = Ship.get_area(x, y, d)[::2]
                if diff:
                    inertial_area = Ship.get_area(x, y, current.orientation)
                    area += [inertial_area[0], inertial_area[2]]
                if any((moving_costs.get(c, 1000) >= 1000 and not Grid.is_border(*c)) for c in area):
                    continue
                    
                cost = current.cost + moving_cost + diff * 20
                    
                if (x, y) == start and inertia == 0 and d == start_d:
                    # prefer to go right at start (if no speed)
                    cost -= 10

                priority = cost + 10 * Grid.manhattan((x, y), target)
                
                node = PathNode(x, y, current)
                node.cost = cost
                node.orientation = d
                nodes.put(node, priority)
                
        return None, iteration

class Entity(Base):
    def __init__(self, ent_id):
        self.id = int(ent_id)
        self.x, self.y = 0, 0
        self.args = [0,0,0,0]

    def update(self, x, y, *args):
        self.x, self.y = int(x), int(y)
        
    @property
    def pos(self):
        return (self.x, self.y)
    
    def __lt__(self, other):
        # default comparison, used to avoid errors when used with queues and priorities are equals
        return self.id < other.id
    
    
class Position(Base):
    def __init__(self, pos, d, speed, weight=10):
        self.pos = pos
        self.d = d
        self.speed = speed
        self.weight = weight
        self.area = Ship.get_area(*self.pos, self.d)
    
class Ship(Entity):
    MAX_SPEED = 2
    SCOPE = 10
    
    SLOW_DOWN = 1
    SPEED_UP = 2
    TURN_LEFT = 3
    TURN_RIGHT = 4
    MOVES = [None, SPEED_UP, TURN_LEFT, TURN_RIGHT, SLOW_DOWN]
    COMMANDS = {SLOW_DOWN: "SLOWER", SPEED_UP: "FASTER", TURN_LEFT: "PORT", TURN_RIGHT: "STARBOARD", None: "NONE"}
    
    areas = {}
    
    def __init__(self, *args, **kwargs):
        super().__init__(*args, **kwargs)
        self.x, self.y = 0, 0
        self.orientation = 0
        self.speed = 0
        self.stock = 0
        self.owned = 0
        
        self.next_cell = None
        self.next_pos = None
        self.last_fire = None
        self.last_mining = None
        self.blocked_since = 0
        self.same_traject_since = 0
        self.last_action = ""
        self.allies = []
        self._moving_costs = {}
        
        self.objectives = ObjectivesQueue()
        self.ennemies = ObjectivesQueue()
        
        self.objective = None
        self.objectives_next = []
        self.target_ennemy = None
        
        self.path = []
        
        self.distance = 0
        self.alignment = 0
        
    def __repr__(self):
        return f"<Ship {self.id}: pos=({self.x}, {self.y}), orientation={self.orientation}, speed={self.speed}, blocked={self.blocked_since}, last_fire={self.last_fire}, next_pos={self.next_pos}, area={self.area}>"

    @classmethod
    def abs_area(cls, x, y, d):
        return [Grid.next_cell(x, y, d), (x, y), Grid.next_cell(x, y, Grid.add_directions(d, 3))]

    @classmethod
    def cache_area(cls, x, y):
        for d in range(3):
            area = [Grid.next_cell(x, y, d), (x, y), Grid.next_cell(x, y, d + 3)]
            Ship.areas[(x, y, d)] = area
            Ship.areas[(x, y, d + 3)] = list(reversed(area))
            
    @classmethod
    def get_area(cls, x, y, d):
        try:
            return list(Ship.areas[(x, y, d)])
        except KeyError:
            return cls.abs_area(x, y, d)
        
    def update(self, x, y, *args):
        previous_state = self.state()
        previous_traject = self.traject()
        
        super().update(x, y)
        self.orientation, self.speed, self.stock, self.owned = map(int, args)

        self.objectives = ObjectivesQueue()
        self.ennemies = ObjectivesQueue()
        
        self.objective = None
        self.objectives_next = []
        self.target_ennemy = None
        
        self.goto = None
        self.path = []
        
        self.area = Ship.get_area(self.x, self.y, self.orientation)
        self.prow, _, self.stern = self.area
        
        self.next_cell = self.get_next_cell()
        self.next_pos = self.get_next_pos()
        self.next_move = None
        self.next_area = Ship.get_area(*self.next_pos, self.orientation)
        
        self.front = Grid.next_cell(*self.prow, self.orientation)
        self.front_left = Grid.next_cell(*self.prow, Grid.add_directions(self.orientation, 1))
        self.left = Grid.next_cell(*self.prow, Grid.add_directions(self.orientation, 2))
        self.front_right = Grid.next_cell(*self.prow, Grid.add_directions(self.orientation, -1))
        self.right = Grid.next_cell(*self.prow, Grid.add_directions(self.orientation, -2))
        self.back_left = Grid.next_cell(*self.stern, Grid.add_directions(self.orientation, 1))
        self.back_right = Grid.next_cell(*self.stern, Grid.add_directions(self.orientation, -1))
        self.behind = Grid.next_cell(*self.stern, Grid.add_directions(self.orientation, 3))
        
        self._can_move = {}
        
        if self.traject() != previous_traject:
            self.same_traject_since += 1
        else:
            self.same_traject_since = 0
    
        if self.state() == previous_state:
            self.blocked_since += 1
        else:
            self.blocked_since = 0

    def traject(self):
        return (self.orientation, self.speed)

    def state(self):
        return (self.x, self.y, self.orientation, self.speed)

    @classmethod
    def get_pos_in(cls, current, speed, orientation, in_=1):
        return Grid.next_cell(*current, orientation, repeat=speed * in_)

    def get_next_pos(self, in_=1):
        return self.get_pos_in(self.pos, self.speed, self.orientation, in_)
    
    def next_pos_proba(self, in_=1):

        # guess next positions
        positions = {0: [Position(self.pos, self.orientation, self.speed)]}
        for i in range(in_):
            positions[i + 1] = []
            
            for p in positions[i]:
                
                pos, d, speed = p.pos, p.d, p.speed
                
                # next pos with inertia
                inertia = Grid.next_cell(*pos, d, repeat=speed)
                
                # wait, fire or mine
                p = Position(inertia, d, speed, 30)
                if self.moving_cost(*p.pos) >= 1000:
                    p.weight = 10
                    
                # turn left
                p = Position(inertia, Grid.add_directions(d, 1), speed)
                if not self.moving_cost(*p.pos) >= 1000:
                    positions[i + 1].append(p)
                    
                # turn right
                p = Position(inertia, Grid.add_directions(d, -1), speed)
                if not self.moving_cost(*p.pos) >= 1000:
                    positions[i + 1].append(p)
                    
                # speed up
                if speed < self.MAX_SPEED:
                    p = Position(Grid.next_cell(*pos, d, repeat=speed + 1), d, speed + 1)
                    if not self.moving_cost(*p.pos) >= 1000:
                        positions[i + 1].append(p)
                
                # slow down
                if speed > 1:
                    p = Position(Grid.next_cell(*pos, d, repeat=speed - 1), d, speed - 1)
                    if not self.moving_cost(*p.pos) >= 1000:
                        positions[i + 1].append(p)
        
                # we voluntary ignore the case where a ship at speed 1 would slow down, 
                # as it is not expected to be a standard behaviour for a ship
        
        # agregate
        proba = {}
        for i, plst in positions.items():
            proba[i] = {}
            weights = {}
            total_weight = sum([p.weight for p in plst])
            for p in plst:
                for c in p.area:
                    weights[c] = weights.get(c, 0) + p.weight
            
            for c in weights:
                proba[i][c] = 100 * weights[c] // total_weight

        return proba
    
    def guess_next_positions(self, in_=1):
        proba = self.next_pos_proba(in_)
        best = {}
        for i in proba:
            best[i] = max(proba[i].items(), key=lambda x: x[1])[0]
        return best
            
    def get_next_cell(self, in_=1):
        return Grid.next_cell(self.x, self.y, self.orientation, repeat=in_)

    def in_current_direction(self, x, y):
        return self.orientation == Grid.direction_to(*self.pos, x, y)

    def moving_cost(self, x, y):
        return self._moving_costs.get((x, y), 1000)
    
    def can_turn_left(self):
        return (self._can_move[self.left] or grid.is_border(*self.left)) \
            and (self._can_move[self.right] or grid.is_border(*self.right)) \
            and (self._can_move[self.back_right] or grid.is_border(*self.back_right))
    
    def can_turn_right(self):
        return (self._can_move[self.right] or grid.is_border(*self.right)) \
               and (self._can_move[self.left] or grid.is_border(*self.left)) \
               and (self._can_move[self.back_left] or grid.is_border(*self.back_left))
    
    def can_move_fwd(self):
        return self._can_move[self.front] and not Grid.is_border(*self.prow)
    
    def can_move(self):
        return self.can_move_fwd() or self.can_turn_left() or self.can_turn_left()
    
    def area_after_moving(self, move):
        new_speed = self.speed
        new_orientation = self.orientation
        if move == Ship.SPEED_UP:
            new_speed += 1
        elif move == Ship.SLOW_DOWN:
            new_speed -= 1
        elif move == Ship.TURN_LEFT:
            new_orientation = Grid.add_directions(self.orientation, 1)
        elif move == Ship.TURN_RIGHT:
            new_orientation = Grid.add_directions(self.orientation, -1)
        
        new_pos = self.get_next_cell(new_speed)
        return self.get_area(*new_pos, new_orientation)
    
    def plan_next_move(self):
        
        blocked = False
        if self.speed:
            if any(self.front in (s.area if not s.speed else [s.area[1], s.area[0], s.prow]) for s in grid.ships if s is not self):
                log("Blocked: speed 0")
                blocked = True
                self.speed = 0
            
        if self.path:
            planned = self._follow_path(self.path)
            
        if self.path is None:
            if self.can_move():
                available = {}
                if self.can_move_fwd():
                    if self.speed:
                        available[None] = 0
                    else:
                        available[Ship.SPEED_UP] = 0
                if self.can_turn_left():
                    available[Ship.TURN_LEFT] = 0
                if self.can_turn_right():
                    available[Ship.TURN_RIGHT] = 0
                    
                for m in available:
                    new_area = self.area_after_moving(m)
                    available[m] = abs(Grid.diff_directions(self.orientation, Grid.direction_to(*new_area[1], *self.goto))) + \
                                   (2 if self.moving_cost(*new_area[1]) > 10 else 0)
                    
                planned = min(available.items(), key=lambda x: x[1])[0]
                log(f"(!) broken: automove ({Ship.COMMANDS[planned]})")
            else:
                log(f"(!) broken: can not move")
                planned = None
        elif not self.path:
            return False
        
        next_move = None
        available_moves = [planned] + [m for m in Ship.MOVES if m != planned]
        risk = Queue()
        
        for move in available_moves:
                
            new_area = self.area_after_moving(move)
            
            # takes inertia in account
            if move == Ship.SPEED_UP or self.speed and move == None:
                for c in self.get_area(*Grid.next_cell(*new_area[1], self.orientation, self.speed + int(move == Ship.SPEED_UP)), self.orientation):
                    if not c in new_area:
                        new_area.append(c)
            
            r = 0
            
            for i, c in enumerate(new_area):
                mc = self.moving_cost(*c)
                
                if mc >= 1000 and (c in grid or i == 1):  # special: extra-grid cells are not consider as collisions since a part of the ship can go there
                    countdown = grid.threat.get(c, 0)
                    if countdown > 1 and mc < 2000:
                        # cannonball will hit there after next turn
                        r += 100
                        
                    else:
                        if blocked and move in (Ship.SLOW_DOWN, None, Ship.SPEED_UP):
                            r = 1000
                        if i == 1:
                            # the center of the ship is threaten
                            r += 500
                        else:
                            r += 250
            
            if not r:
                if move == planned:
                    r = -1
                elif self.speed <= 1 and move == Ship.SLOW_DOWN:
                    r = 50 # we don't want to slow down except there is a danger
                else:
                    # distance from the prow to the current objective
                    r = abs(Grid.diff_directions(self.orientation, Grid.direction_to(*new_area[1], *self.goto)))
                    r += (2 if self.moving_cost(*new_area[1]) > 10 else 0)

            risk.fput(move, r)
            if r >= 100:
                log(f"/!\ Danger: planned move <{Ship.COMMANDS[move]}> could lead to collision (risk={r}, area={new_area})")
            elif r < 0:
                next_move = move
                log(f"Safe move: {Ship.COMMANDS[move]}")
                break
            else:
                log(f"Available move <{Ship.COMMANDS[move]}> (risk={r}, area={new_area})")

        else:
            try:
                next_move = risk.get()
                log(f"* Go to the less risky: {Ship.COMMANDS[next_move]}")
            except IndexError:
                next_move = planned
                log(f"* No collision-free move was found, go to the initial one: {Ship.COMMANDS[next_move]}")
                
        self.next_move = next_move
        self.next_area = new_area
        return True

    def _follow_path(self, path):
        
        # flags represent direction changes or end of the path
        last_flag = len(path) - 1
        next_flag = next((i for i, n in enumerate(path) if n.orientation != self.orientation), last_flag)
        afternext_flag = next((i for i, n in enumerate(path[next_flag:]) if n.orientation != path[next_flag].orientation), last_flag)
        
        if not self.speed:
            diff = Grid.diff_directions(self.orientation, path[0].orientation)
            
            if diff > 0 and self.last_action == "STARBOARD" or diff < 0 and self.last_action == "PORT":
                # special: avoid the starting hesitation
                return Ship.SPEED_UP
            
            if diff and next_flag == 0:
                # start, with a direction change
                if diff > 0:
                    return Ship.TURN_LEFT
                elif diff < 0:
                    return Ship.TURN_RIGHT
                    
            # start straight
            else:
                return Ship.SPEED_UP
        
        elif self.speed == self.MAX_SPEED:
            
            if next_flag <= self.speed:
                if afternext_flag >= (next_flag + 2): # there is at least one straight cell after this drift
                    # drift
                    diff = Grid.diff_directions(self.orientation, path[next_flag].orientation)
                    if diff > 0:
                        return Ship.TURN_LEFT
                    elif diff < 0:
                        return Ship.TURN_RIGHT
                else:
                    return Ship.SLOW_DOWN
                
            if next_flag <= self.speed + 1:
                # next direction change or target will be passed at current speed
                return Ship.SLOW_DOWN

        elif self.speed == 1:
            
            if next_flag <= 1:
                diff = Grid.diff_directions(self.orientation, path[next_flag].orientation)
                if diff > 0:
                    return Ship.TURN_LEFT
                elif diff < 0:
                    return Ship.TURN_RIGHT
            
            elif next_flag >= 4:
                return Ship.SPEED_UP
            
        return None
           
    def move(self):
        if self.next_move == Ship.SPEED_UP:
            self.speed_up()
        elif self.next_move == Ship.SLOW_DOWN:
            self.slow_down()
        elif self.next_move == Ship.TURN_LEFT:
            self.turn_left()
        elif self.next_move == Ship.TURN_RIGHT:
            self.turn_right()
        else:
            return False
        return True
           
    def fire_at_will(self, *args, **kwargs):
        return self._fire_at_will(*args, **kwargs)
           
    def _fire_at_will(self):
        if not self.can_fire():
            return False
        
        avoid = []
        for ship in grid.owned_ships:
            avoid += ship.next_area
        
        barrels = [b.pos for b in grid.barrels]
        for bpos in barrels:
            if any(Grid.manhattan(ship.pos, bpos) <= Grid.manhattan(e.pos, bpos) for ship in grid.owned_ships for e in grid.ennemy_ships):
                avoid.append(bpos)
        
        for m in grid.mines:
            if any((Grid.manhattan(s.next_pos, m.pos) <= 2 or \
                    abs(Grid.diff_directions(self.orientation, Grid.direction_to(*s.next_pos, *m.pos))) <= 1)\
                    for s in grid.owned_ships):
                avoid.append(m.pos)
        
        all_shots = {}
        
        for target in grid.ennemy_ships:
        
            next_positions = target.next_pos_proba(4)
            
            # include avoid, mines, barrels, and other ennemies
            for t in next_positions:
                probas = next_positions[t]
                mines_next = {}
                
                for c, proba in probas.items():
                    if c in grid.next_to_mine:
                        mpos = grid.next_to_mine[c].pos
                        mines_next[mpos] = mines_next.get(mpos, 1) + proba
                probas.update(mines_next)
                
                for c in probas:
                    if c in barrels:
                        probas[c] *= 2
            
            for t, probas in next_positions.items():
                
                shots = sorted(probas.items(), key=lambda x: x[1], reverse=True)
                for c, proba in shots:
                    if c in avoid:
                        continue
                    if proba < 20:
                        continue
                    dist = Grid.manhattan(self.prow, c)
                    if dist > self.SCOPE:
                        continue
                    
                    # time for the cannonball to reach this pos (including fire turn)
                    delay = 1 + round(dist / 3)
                    if delay != t:
                        continue
                    
                    if not c in all_shots:
                        all_shots[c] = (proba - t)
                    else:
                        all_shots[c] += (proba - t)
                    
        if all_shots:
            best_shot = max(all_shots.items(), key=lambda x: x[1])[0]
            log(f"[x] precise shoot: pos={best_shot}")
            ship.fire(*best_shot)
            return True
                
        return False
        
    def can_mine(self):
        return self.last_mining is None or (current_turn - self.last_mining) >= 4
        
    def can_fire(self):
        return self.last_fire is None or (current_turn - self.last_fire) >= 1
            
    def mine_maybe(self):
        if self.can_mine():
            if not any(Grid.manhattan(self.prow, ally.next_pos) <= 5 for ally in self.allies):
                self.mine()
                return True
        return False
            
    # --- Basic commands
    def _act(self, cmd, *args):
        self.last_action = cmd
        output = " ".join([cmd] + [str(a) for a in args])
        log(f"ship {self.id}: {output}")
        print(output)
    
    def auto_move(self, x, y):
        self._act("MOVE", x, y)
        
    def speed_up(self):
        self._act("FASTER")
        
    def slow_down(self):
        self._act("SLOWER")    
    
    def turn_right(self):
        self._act("STARBOARD")
    
    def turn_left(self):
        self._act("PORT")
        
    def wait(self):
        self._act("WAIT")
        
    def mine(self):
        self.last_mining = current_turn
        self._act("MINE")
        
    def fire(self, x, y):
        self.last_fire = current_turn
        self._act("FIRE", x, y)

class Barrel(Entity):
    def __init__(self, *args, **kwargs):
        super().__init__(*args, **kwargs)
        self.amount = 0

        self.dispersal = 0
        self.mine_threat = False
        self.ennemy_near = False

    def __repr__(self):
        return f"<Barrel {self.id}: pos=({self.x}, {self.y}), amount={self.amount}>"
        
    def update(self, x, y, *args):
        super().update(x, y)
        self.amount = int(args[0])

class Mine(Entity):
    def __init__(self, *args, **kwargs):
        super().__init__(*args, **kwargs)
        self.ghost = False

    def __repr__(self):
        return f"<Mine {self.id}: pos=({self.x}, {self.y}), ghost={self.ghost}>"

class Cannonball(Entity):

    def update(self, x, y, *args):
        super().update(x, y)
        self.sender, self.countdown = int(args[0]), int(args[1])


entities = {}
map_entity = {"SHIP": Ship, 
             "BARREL": Barrel,
             "MINE": Mine,
             "CANNONBALL": Cannonball}

Grid.preload()
grid = Grid()

### *** Main Loop ***

while True:
    seen = []
    current_turn += 1
    
    # <--- get input
    my_ship_count, entity_count = int(input()), int(input())
    ent_input = [input().split() for _ in range(entity_count)]
    # --->

    log(f"### TURN {current_turn}")
    log(">> Load input")
    # <--- load input
    previous_ent, entities = grid.entities, {}
    for e in ent_input:
        ent_id, ent_type, *data = e
        ent_id = int(ent_id)
        entities[ent_id] = grid.entities.get(ent_id, map_entity[ent_type](ent_id))
        entities[ent_id].update(*data)
        
    grid.load_entities(entities)
    # --->
    
#     log(f"Owned Ships: {grid.owned_ships}")
    log(f"Ennemy Ships: {grid.ennemy_ships}")
    log(f"Barrels: {grid.barrels}")
#     log(f"Mines: {grid.mines}")
    log(f"Cannonballs: {grid.cannonballs}")
    
    max_it = 9000 // len(grid.owned_ships)

    ### Acquire
    log("# Acquiring")
    
    # main objective
    while not all(s.objective for s in grid.owned_ships):
        try:
            acquired = sorted([(s, s.objectives.get()) for s in grid.owned_ships if not s.objective], key= lambda x: x[1].interest)
            for s, o in acquired:
                if not s.objective and not any(al.objective.target is o.target for al in s.allies if al.objective):
                    s.objective = o
            
        except IndexError:
            break
        
    # targetted ennemy
    for s in grid.owned_ships:
        s.target_ennemy = s.ennemies.get()
        
    ### Plan
    log("# Planning")
    
    for ship in grid.owned_ships:
        log(f"---- ship {ship.id} ---")
        log(f"ship: {ship}")
        
        it_consumed = 0
        
        if ship.objective:
            ship.goto = ship.objective.target.pos
            
        elif ship.target_ennemy:
            if all(s.stock < ship.stock for s in grid.ships if not s is ship):
                log("Best stock: runaway!")
                ship.goto = grid.runaway_spot(ship)
            else:
                ship.goto = grid.shooting_spot(ship, ship.target_ennemy.target, current=ship.goto)
        else:
            log("ERROR: No target")
            continue
        
        log(f"goto: {ship.goto}")
        
        ship.path, its = grid.path(ship.pos, 
                              ship.orientation, 
                              ship.goto, 
                              moving_costs=ship._moving_costs, 
                              inertia=ship.speed, 
                              limit=(max_it - it_consumed))
        it_consumed += its
        
        if ship.objective and ship.path and ship.path[-1] == ship.goto:
            while ship.objectives and len(ship.path) < 15:
                pos, d = ship.path[-1], ship.path[-1].orientation
                
                ship.objectives = ObjectivesQueue.re_eval(ship.objectives, pos, d)
                current_obj = ship.objectives.get()
                
                ship.objectives_next.append(current_obj)
            
                new_path, its = grid.path(pos, d, 
                                       current_obj.target.pos, 
                                       moving_costs=ship._moving_costs,
                                       limit=(max_it - it_consumed))
                
                it_consumed += its
                
                if new_path and new_path[-1] == current_obj.target.pos:
                    ship.path += new_path
                else:
                    break
 
        ship.plan_next_move()

        log(f"obj: {ship.objective}; next: {ship.objectives_next}")
        log(f"target: {ship.target_ennemy}")
        log(f"path: {ship.path}")
        log(f"next_move: {Ship.COMMANDS[ship.next_move]}")
        
    ### Process
    log("# Processing")
    
    for ship in grid.owned_ships:
        log(f"---- ship {ship.id} ---")
        if not ship.objective and not ship.target_ennemy:
            log("No target: wait")
            ship.wait()
        
        if ship.move():
            continue
        
        # no movement was required, can fire
        if ship.fire_at_will():
            continue
        
        # or mine
        if ship.mine_maybe():
            continue
        
        log("ERROR: Did not act, wait")
        ship.wait()




# Changelog:
# 2019-04-17 
# * if no available move, takes the less risky
# * add the ennemy_near evaluation to the pre_eval method of GetBarrel and update it
# * ignore probas < 20 in the moving cost calc (about ennemy next positions)
# * get_shooting_spots: discurage direction changes
# * increase shooting_spots distance from 5 to 7
# * fire on mines, do not shoot mines that are in front of the ship
# * increase the weight of a dead angle in GetBarrel.eval() from 18 to 36 <=> the weight of a distance of 6 needed to turn
# * mines: increase moving_cost of neighbors if a cannon ball is going to hit the mine
# * Improve the _follow_path algo
# * anticipate the speed at 0 when blocked
# * coeff 20 instead of 10 for the presence probability, making it impassable from 50% instead of 100%
# *(disactivated)  moving cost takes now in account the order of play of the ships
# * increase the max length of the path from 10 to 15 when seeking for next objectives
# * minor improvement to automove
# * Avoid shooting barrels unless ennemy is nearest
# * include distance to ennemy in the eval of the shooting spot
# * (disactivated because of below) avoid consecutives direction changes 
# * path: direction change moving cost changed from 10 to 20 because of the slowing effect

# 2019-04-18
# * take in account the inertial_area in path computing when direction change
# * improve the esquive algo by priorizing moves in direction of the target
# * remove cache on 'next_pos_proba'
# * improve the fire_at_will algo
# * takes all ennemies in account to find the best shot

# 2019-04-19
# * path(): fix the special speed-up-inertia when start whith speed 0
# * fix the grid.threat update
# * add a moving cost at the prow of enemy ships to avoid a possible mine