399 lines
12 KiB
Python
399 lines
12 KiB
Python
|
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()
|