import json import math import random import sys from enum import Enum from typing import List, Set, Iterable, Union, Tuple, Dict LOGGING = True ENEMY_SIGHT_DISTANCE = 3 DISTANCE_THRESHOLD_FOR_SPEED = 3 WALL = "#" PATH = " " UNKNOWN_PATH = "." class Type(Enum): ROCK = "ROCK" PAPER = "PAPER" SCISSORS = "SCISSORS" def __gt__(self, other): wins_over = { Type.ROCK: Type.SCISSORS, Type.SCISSORS: Type.PAPER, Type.PAPER: Type.ROCK, } loser = wins_over[self] return other is loser def get_winner(self): winner_for = { Type.SCISSORS: Type.ROCK, Type.PAPER: Type.SCISSORS, Type.ROCK: Type.PAPER, } return winner_for[self] def log(something, *args, **kwargs): if LOGGING: print(something, *args, file=sys.stderr, **kwargs) class Position: def __init__(self, x, y): self.x = x self.y = y def distance_to(self, other: "Position") -> int: return int(math.fabs(self.x - other.x) + math.fabs(self.y - other.y)) def __hash__(self): return hash((self.x, self.y)) def __eq__(self, other: "Position"): return self.x == other.x and self.y == other.y def __str__(self): return json.dumps(self.to_dict()) def __repr__(self): return str(self) def to_dict(self): return {"x": self.x, "y": self.y} class Pac(Position): def __init__(self, line: str): split = line.split() self.pac_id = int(split[0]) self.mine = split[1] != "0" self.type_id = Type[split[4].upper()] # type: Type self.speed_turns_left = int(split[5]) self.ability_cooldown = int(split[6]) x = int(split[2]) y = int(split[3]) super(Pac, self).__init__(x, y) def __hash__(self): return hash((self.pac_id, self.mine)) def __eq__(self, other: "Pac") -> bool: return ( isinstance(other, Pac) and self.pac_id == other.pac_id and self.mine == other.mine ) def to_dict(self) -> Dict: dct = super(Pac, self).to_dict() dct.update({"id": self.pac_id, "mine": self.mine}) return dct def move_to(self, unit: Position) -> str: return f"MOVE {self.pac_id} {unit.x} {unit.y}" def speed(self) -> str: return f"SPEED {self.pac_id}" def switch(self, type: Type, comment: str = "") -> str: return f"SWITCH {self.pac_id} {type.value} {comment}" def target_type(self, other: "Pac") -> Union[Type, None]: winner_type = other.type_id.get_winner() if winner_type is self.type_id: return None return winner_type @property def can_use_power(self) -> bool: return self.ability_cooldown <= 1 @property def is_speeding(self) -> bool: return self.speed_turns_left > 0 class Pellet(Position): def __init__(self, line: str): x, y, value = [int(i) for i in line.split()] self.value = value super(Pellet, self).__init__(x, y) def __hash__(self): return hash((self.x, self.y, self.value)) def __eq__(self, other: "Pellet"): return ( isinstance(other, Pellet) and super(Pellet, self).__eq__(other) and self.value == other.value ) def to_dict(self): dct = super().to_dict() dct.update({"value": self.value}) return dct @property def is_super(self) -> bool: return self.value > 1 class Grid: def __init__(self, line: str, process_rows: bool = True): # Invariants # width: size of the grid # height: top left corner is (x=0, y=0) width, height = [int(i) for i in line.split()] self.width = width # type: int self.height = height # type: int self.map = [] # type: List[List[str]] if process_rows: for i in range(self.height): self.map.append(list(input().replace(PATH, UNKNOWN_PATH))) # Variants self.pacs = set() # type: Set[Pac] self.pellets = set() # type: Set[Pellet] self.previous_pacs = set() @property def my_pacs(self) -> Iterable[Pac]: return filter(lambda pac: pac.mine, self.pacs) @property def enemy_pacs(self) -> Iterable[Pac]: return filter(lambda pac: not pac.mine, self.pacs) def pac_at_position(self, x, y, enemy_filter=None) -> Union[Pac, None]: if enemy_filter is True: pacs = self.enemy_pacs elif enemy_filter is False: pacs = self.my_pacs else: pacs = self.pacs x = x % self.width y = y % self.height for pac in pacs: if pac.x == x and pac.y == y: return pac def new_turn(self): self.previous_pacs = self.pacs self.pacs = set() self.pellets = set() def add_pellet(self, line: str) -> Pellet: pellet = Pellet(line) self.set_map_at_coordinates(pellet, str(pellet.value)) self.pellets.add(pellet) return pellet def add_pac(self, line: str) -> Pac: pac = Pac(line) self.pacs.add(pac) return pac def get_random_position(self) -> Position: return Position( random.randint(0, self.width - 1), random.randint(0, self.height - 1) ) def get_closest_unknown(self, me: Pac) -> Union[Position, None]: closest = None for y, row in enumerate(self.map): for x, cell in enumerate(row): if cell != UNKNOWN_PATH: continue pos = Position(x, y) if not closest or me.distance_to(pos) < me.distance_to(closest): closest = pos return closest def get_action( self, me: Pac, already_targeted: Set[Position] ) -> Tuple[str, Union[Position, None]]: enemy = self.closest_enemy_in_sight(me) if me.can_use_power and enemy: new_type = me.target_type(enemy) if new_type: return ( me.switch(new_type, f"switching to {new_type.value} for {enemy}"), None, ) if enemy and me.type_id > enemy.type_id: return me.move_to(enemy), enemy target = self.find_target(me, already_targeted) if me.can_use_power: return me.speed(), None return me.move_to(target), target def find_target(self, me: Pac, already_targeted: Set[Position]) -> Position: rnd = self.get_random_position() default = self.get_closest_unknown(me) same_position = False min_dist = 2 if me.is_speeding else 1 for pac in self.previous_pacs: if pac == me and pac.x == me.x and pac.y == me.y: same_position = True break if same_position: return default or rnd closest_pellet_distance = math.inf closest_pellet = None closest_super_pellet_distance = math.inf closest_super_pellet = None fallback_pellet = None for pellet in self.pellets: if pellet in already_targeted: continue distance = me.distance_to(pellet) if pellet.is_super: if distance < closest_super_pellet_distance: closest_super_pellet_distance = distance closest_super_pellet = pellet else: if min_dist <= distance < closest_pellet_distance: closest_pellet_distance = distance closest_pellet = pellet elif distance < closest_pellet_distance: fallback_pellet = pellet if ( fallback_pellet and closest_pellet and math.fabs( me.distance_to(fallback_pellet) - me.distance_to(closest_pellet) ) > 3 ): closest_pellet = fallback_pellet log(me.pac_id, closest_super_pellet, closest_pellet, default) return ( closest_super_pellet or closest_pellet or fallback_pellet or default or rnd ) def get_map_at_coordinates(self, x: int, y: int) -> str: x = x % self.width y = y % self.height return self.map[y][x] def set_map_at_coordinates(self, position: Position, value: str): x = position.x % self.width y = position.y % self.height self.map[y][x] = value def closest_enemy_in_sight(self, me: Pac) -> Union[Pac, None]: try_right, try_left, try_up, try_down = True, True, True, True closest_enemy = None self.set_map_at_coordinates(me, PATH) for i in range(1, max(self.height, self.width)): if try_right: x = me.x + i y = me.y cell = self.get_map_at_coordinates(x, y) if cell == WALL: try_right = False elif cell == UNKNOWN_PATH: self.set_map_at_coordinates(Position(x, y), PATH) pac_at_position = self.pac_at_position(x, y, enemy_filter=True) if ( pac_at_position and me.distance_to(pac_at_position) <= ENEMY_SIGHT_DISTANCE and not closest_enemy ): closest_enemy = pac_at_position if try_left: x = me.x - i y = me.y cell = self.get_map_at_coordinates(x, y) if cell == WALL: try_left = False elif cell == UNKNOWN_PATH: self.set_map_at_coordinates(Position(x, y), PATH) pac_at_position = self.pac_at_position(x, y, enemy_filter=True) if ( pac_at_position and me.distance_to(pac_at_position) <= ENEMY_SIGHT_DISTANCE and not closest_enemy ): closest_enemy = pac_at_position if try_up: x = me.x y = me.y - i cell = self.get_map_at_coordinates(x, y) if cell == WALL: try_up = False elif cell == UNKNOWN_PATH: self.set_map_at_coordinates(Position(x, y), PATH) pac_at_position = self.pac_at_position(x, y, enemy_filter=True) if ( pac_at_position and me.distance_to(pac_at_position) <= ENEMY_SIGHT_DISTANCE and not closest_enemy ): closest_enemy = pac_at_position if try_down: x = me.x y = me.y + i cell = self.get_map_at_coordinates(x, y) if cell == WALL: try_down = False elif cell == UNKNOWN_PATH: self.set_map_at_coordinates(Position(x, y), PATH) pac_at_position = self.pac_at_position(x, y, enemy_filter=True) if ( pac_at_position and me.distance_to(pac_at_position) <= ENEMY_SIGHT_DISTANCE and not closest_enemy ): closest_enemy = pac_at_position return closest_enemy def main(): grid = Grid(input()) # game loop while True: grid.new_turn() my_score, opponent_score = [int(i) for i in input().split()] # type: int, int visible_pac_count = int(input()) # type: int for i in range(visible_pac_count): grid.add_pac(input()) visible_pellet_count = int(input()) # type: int for _ in range(visible_pellet_count): grid.add_pellet(input()) output = [] targets = set() for pac in grid.my_pacs: action, target = grid.get_action(pac, targets) output.append(action) targets.add(target) print(" | ".join(output)) if __name__ == "__main__": main()