cig/carribean/script.py

'''

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

# TODO:
# * add an esquive manoeuvre / try to avoid cannonballs
# * separate the main loop in two: planning, then acting
# * consider targeting rum barrels if an ennemy is nearer
# * compute first and second target instead of only one to anticipate the next move
# * if an enemy is near a mine, shoot the mine instead of the ship

debug = True

def log(*msg):
    if debug:
        print(*msg, file=sys.stderr)

current_turn = 0

class DidNotAct(Exception):
    pass

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


class Position(Base):
    def __init__(self, x, y):
        self.pos = (x, y)

class ShootingSpot(Position):
    def __init__(self, *args):
        super().__init__(*args)
        self.interest = 0

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):
    def __init__(self):
        self.w = 23
        self.h = 21
        
        self._neighbors = {}
        for x in range(-1, self.w + 1):
            for y in range(-1, self.h + 1):
                self.cache_neighbors(x, y)
 
        self.load_entities({})
        
    def __contains__(self, key):
        return 0 <= key[0] < self.w and 0 <= key[1] < self.h

    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.pos in [e.pos for e in entities.values() if type(e) is Mine]:
                    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 = []
        
        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)
                
        
    def at(self, x, y):
        try:
            return self.index[(x, y)]
        except KeyError:
            return None
        
    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 pre_evaluate_barrels_interest(self):
        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))
            
    def evaluate_barrels_interest(self, ship):
        for b in self.barrels:
            b.distance = Grid.manhattan(ship.next_pos, b.pos)
            b.alignement = abs(Grid.diff_directions(Grid.direction_to(*ship.prow, *b.pos), ship.orientation))
            b.about_to_be_picked = any(b.pos in s.next_area for s in self.ennemy_ships)
                    
    def evaluate_ennemies_interest(self, ship):
        for s in self.ennemy_ships:
            s.distance = Grid.manhattan(ship.next_pos, s.next_pos)
            s.alignement = abs(self.diff_directions(self.direction_to(*ship.prow, *s.next_pos), ship.orientation))
    
    def pre_update_moving_costs(self):
        self.moving_costs = {}
        
        for x in range(-1, self.w + 1):
            for y in range(-1, self.h + 1):
                if x in (0, self.w) or y in (0, self.h):
                    self.moving_costs[(x, y)] = 15 # borders are a little more expensive
                elif x in (-1, self.w + 1) or y in (-1, self.h + 1):
                    self.moving_costs[(x, y)] = 1000 # out of the map
                else:
                    self.moving_costs[(x, y)] = 10 # base moving cost
        
        for m in self.mines:
            for n in self.neighbors(*m.pos):
                self.moving_costs[n] += 30
        for m in self.mines:
            self.moving_costs[m.pos] += 1000
        for c in self.cannonballs:
            self.moving_costs[c.pos] += (100 + (5 - c.countdown) * 200)
        
    def update_moving_costs(self, ship):
        for s in self.ships:
            if s is ship:
                continue
            dist = self.manhattan(ship.pos, s.pos)
            if dist > 8:
                continue
            for c in self.neighbors(*s.pos):
                self.moving_costs[c] += 100 * abs(3 - s.speed)
            for c in self.zone(s.next_pos, 4):
                self.moving_costs[c] += 20
    
    def shooting_spot(self, ship, targetted_ship):
        self.shooting_spots = []
        for x, y in self.zone(targetted_ship.next_pos, 10):
            if self.moving_costs[(x, y)] > 10:
                continue
            if self.manhattan((x, y), targetted_ship.next_pos) < 2:
                continue
            
            spot = ShootingSpot(x, y)
            
            spot.interest -= self.moving_costs[(x, y)]
            
            # avoid cells too close from borders
            if not (3 <= x <= (self.w - 3) and 3 <= y < (self.h - 3)):
                spot.interest -= 10
            
            # priorize spots at distance 5 from active ship
            spot.interest += 10 * abs(5 - self.manhattan((x, y), ship.pos))
            
            self.shooting_spots.append(spot)

        return max(self.shooting_spots, key= lambda x: x.interest)

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

    def zone(self, center, radius):
        buffer = frozenset([center])
        for _ in range(0, radius):
            current = buffer
            for x, y in current:
                buffer |= frozenset(self.neighbors(x, y))
        return [c for c in buffer if 0 <= c[0] < self.w and 0 <= c[1] < self.h]       

    @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 diff_directions(d1, d2):
        d = d2 - d1
        if d <= -3:
            d += 6
        elif d > 3:
            d -= 6
        return d
    
    @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))
    
    def cache_neighbors(self, xc, yc):
        self._neighbors[(xc, yc)] = [(x, y) for x, y in Grid.abs_neighbors(xc, yc) if 0 <= x < self.w and 0 <= y < self.h]

    def neighbors(self, x, y):
        try:
            return self._neighbors[(x, y)]
        except KeyError:
            self.cache_neighbors(x, y)
            return self._neighbors[(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, origin, orient0, target, incl_start=False, limit=10000):
        nodes = []
        break_on, iteration = limit, 0
        
        origin = PathNode(*origin)
        origin.orientation = orient0
        heapq.heappush(nodes, (0, origin))
        neighbors = []

        while nodes:
            current = heapq.heappop(nodes)[1]

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

            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:
                    return None
                
                moving_cost = self.moving_costs[x, y]
                if moving_cost >= 1000:
                    continue
                
                d = Grid.direction_to(*current, x, y)
                diff = abs(Grid.diff_directions(current.orientation, d))
                if diff > 1:
                    # change direction one degree at a time
                    continue
                    
                cost = current.cost + moving_cost + diff * 10
                if diff != 0 and any(self.moving_costs[c] >= 1000 for c in neighbors):
                    # a direction change here is dangerous
                    cost += 50
                
                priority = cost + 10 * Grid.manhattan((x, y), target)

                node = PathNode(x, y, current)
                node.cost = cost
                node.orientation = d
                heapq.heappush(nodes, (priority, node))
        else:
            return None

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)
    
class Ship(Entity):
    MAX_SPEED = 2
    SCOPE = 10
    
    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.target = None
        
        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}>"

    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.target = None
        
        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_area = Ship.get_area(*self.next_pos, self.orientation)
        
        self.mobility_zone = list(set(self.area + self.next_area))
            
        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_area(cls, x, y, orientation):
        dx, dy = Grid.directions(y)[((orientation + 3) % 6)]
        stern = (x + dx, y + dy)
        
        dx, dy = Grid.directions(y)[orientation]
        prow = (x + dx, y + dy)
        
        return [prow, (x, y), stern]

    def get_next_pos(self, in_=1):
        x, y = self.x, self.y
        for _ in range(in_):
            for _ in range(self.speed):
                dx, dy = Grid.directions(y)[self.orientation]
                x, y = x + dx, y + dy
        return x, y
    
    def get_next_cell(self, in_=1):
        x, y = self.x, self.y
        for _ in range(in_):
            dx, dy = Grid.directions(y)[self.orientation]
            x, y = x + dx, y + dy
        return x, y

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

    @property
    def interest(self):
        return 7 * self.distance + 3 * self.alignment - 20 * self.blocked_since - 10 * self.same_traject_since
    
    def acquire(self, target):
        self.target = target
        if type(target) is Barrel:
            target.aimed = True

    def move(self, *args, **kwargs):
        try:
            self._move(*args, **kwargs)
            return True
        except DidNotAct:
            return False

    def _move(self, path, avoid=[]):
        
        if path is None:
            log(f"(!) broken: automove to {goto}")
            ship.auto_move(*goto)
            return
        elif not path:
            raise DidNotAct()
        
        # <--- special: avoid blocking situations
        if current_turn > 1 and self.blocked_since >= 1:
            dx, dy = Grid.directions(self.y)[((self.orientation + 1) % 6)]
            if grid.moving_costs[self.x + dx, self.y + dy] <= 50:
                self.turn_left()
            else:
                self.turn_right()
            return
        # --->
        
        # speed shall be at 1 when arriving on the "flag"
        next_flag = next((i for i, n in enumerate(path) if n.orientation != self.orientation), None)
        if next_flag is None:
            next_flag = len(path)
        
        if next_flag < (2 * self.speed):
            # the end of the path or a direction change is coming
            diff = Grid.diff_directions(self.orientation, path[0].orientation)
            
            # <--- special: avoid the left/right hesitation when stopped
            if diff and not self.speed and self.last_action in ["STARBOARD",  "PORT"]:
                self.speed_up()
                return
            # --->
            
            if diff > 0:
                self.turn_left()
                return
                
            elif diff < 0:
                self.turn_right()
                return
        
            elif self.speed > 1:
                self.slow_down()
                return
        
        else:
            if not self.speed or (next_flag > (2 * self.speed + 1) and self.speed < self.MAX_SPEED):
                # long path and no direction change coming: speed up
                self.speed_up()
                return
        
        raise DidNotAct()
           
    def fire_at_will(self, *args, **kwargs):
        try:
            self._fire_at_will(*args, **kwargs)
            return True
        except DidNotAct:
            return False
           
    def _fire_at_will(self, target, allies = []):
        if not self.can_fire():
            raise DidNotAct()
        
        log("** fire at will")
        
        next_positions = [target.get_next_pos(i) for i in range(1, 3)]
        log(f"ennemy next pos: {next_positions}")
        
        avoid = []
        if not self in allies:
            allies.append(self)
        for ally in allies:
            avoid += ally.mobility_zone

        log(f"avoid: {avoid}")

        for i, p in enumerate(next_positions):
            turn = i + 1
            
            if p in avoid:
                continue
            
            dist_p = Grid.manhattan(self.prow, p)
            
            if dist_p > self.SCOPE:
                continue
            
            if (1 + round(dist_p / 3)) == turn:
                log(f"Precision: {p}, {dist_p}, {turn}")
                ship.fire(*p)
                return
        
        next_pos = next_positions[0]
        dist_p = Grid.manhattan(self.prow, next_pos)
        if dist_p <= self.SCOPE:
            ship.fire(*p)
            return
        
        raise DidNotAct()
            
    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
            
    # --- Basic commands
    def auto_move(self, x, y):
        self.last_action = "MOVE"
        print(f"MOVE {x} {y}")
        
    def speed_up(self):
        self.last_action = "FASTER"
        print("FASTER")
        
    def slow_down(self):
        self.last_action = "SLOWER"
        print("SLOWER")    
    
    def turn_right(self):
        self.last_action = "STARBOARD"
        print("STARBOARD")
    
    def turn_left(self):
        self.last_action = "PORT"
        print("PORT")
        
    def wait(self):
        self.last_action = "WAIT"
        print("WAIT")
        
    def mine(self):
        self.last_mining = current_turn
        self.last_action = "MINE"
        print("MINE")
        
    def fire(self, x, y):
        self.last_fire = current_turn
        self.last_action = "FIRE"
        print(f"FIRE {x} {y}")

class Barrel(Entity):
    def __init__(self, *args, **kwargs):
        super().__init__(*args, **kwargs)
        self.amount = 0
        self.distance = 0
        self.dispersal = 0
        self.alignement = False
        self.mine_threat = 0
        self.about_to_be_picked = False
        self.aimed = 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])
#         self.aimed = False
        
    @property
    def interest(self):
        # the lower the better
        return 7 * self.distance \
               + 3 * self.dispersal \
               + self.mine_threat ** 2 \
               + 7 * self.alignement \
               - 100 * self.about_to_be_picked

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



class Action(Base):
    def __init__(self, *args):
        self.args = args
        
    def resolve(self):
        raise NotImplementedError

class Move(Action):
    pass

class Fire(Action):
    pass

class TurnLeft(Action):
    pass

class TurnRight(Action):
    pass

class SpeedUp(Action):
    pass

class SlowDown(Action):
    pass


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

grid = Grid()


while True:
    seen = []
    current_turn += 1
    
    # <--- get input
    if 1:
        my_ship_count, entity_count = int(input()), int(input())
        for _ in range(entity_count):
            ent_id, ent_type, *data = input().split()
            ent_id = int(ent_id)
            seen.append(ent_id)
               
            if not ent_id in entities:
                entities[ent_id] = map_entity[ent_type](ent_id)
                   
            ent = entities[ent_id]
            ent.update(*data)
         
        entities = {k: v for k, v in entities.items() if k in seen}
    # --->
    # <--- test input
    else:
        ship = Ship(0)
        ship.update(3,3,0,1,0,1)
        ennemy = Ship(1)
        ennemy.update(1,1,0,1,0,0)
        barrel1 = Barrel(10)
        barrel1.update(8,2,40,0,0,0)
        barrel2 = Barrel(11)
        barrel2.update(4,2,50,0,0,0)
        mine = Mine(20)
        mine.update(10, 2)
        entities = {0: ship, 1: ennemy, 20: mine}
#         entities = {0: ship, 1: ennemy, 10: barrel1, 11: barrel2, 20: mine}
        seen = [0, 1]
    # --->
    
    # log(entities)
    grid.load_entities(entities)
    
    log(f"### turn {current_turn}")
#     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}")

    grid.pre_update_moving_costs()
    grid.pre_evaluate_barrels_interest()

    for ship in grid.owned_ships:
        log(f"---- ship {ship.id} ---")
        log(f"ship: {ship}")
        grid.update_moving_costs(ship)
        allies = [s for s in grid.owned_ships if s is not ship]
        
        target = None
        
        if grid.barrels:
            grid.evaluate_barrels_interest(ship)
            log("barrels interest: {}".format({b.pos: f"{b.interest} ({b.distance}/{b.dispersal}/{b.mine_threat}/{b.alignement})" for b in grid.barrels}))
        if grid.ennemy_ships:
            grid.evaluate_ennemies_interest(ship)
            log("ennemies interest: {}".format({s.pos: f"{s.interest} ({s.distance}/{s.alignement}/{s.blocked_since}/{s.same_traject_since})" for s in grid.ennemy_ships}))

        allies_targets = [a.target for a in allies]
        
        targetted_barrel = next((b for b in sorted(grid.barrels, key=lambda x: x.interest) if not b in allies_targets and not b.pos in ship.next_area), None)
        targetted_ennemy = next((s for s in sorted(grid.ennemy_ships, key=lambda x: x.interest)), None)
    
        if not targetted_barrel and not targetted_ennemy:
            log("(!) No target, wait")
            ship.wait()
            continue
    
        target = targetted_barrel or targetted_ennemy
    
        log(f"target ({target.__class__.__name__}): {target}")
        ship.acquire(target)
        
        if type(target) is Ship:
            goto = grid.shooting_spot(ship, target).pos
        else:
            goto = target.pos
        log(f"goto: {goto}")
        
        path = grid.path(ship.next_pos, ship.orientation, goto, limit=6000 // len(grid.owned_ships))
        log(f"path: {path}")
        
        if ship.move(path):
            continue
            
        if ship.fire_at_will(targetted_ennemy, allies=grid.owned_ships):
            continue
        
        log("ERROR: Did not act, wait")
        ship.wait()