''' @author: olivier.massot, 2019 ''' import heapq import sys DEBUG = False def log(x): if DEBUG: print(x, file=sys.stderr) # Cells START_0 = '0' START_1 = '1' BLUEBERRIES_CRATE = "B" ICE_CREAM_CRATE = "I" WINDOW = "W" EMPTY_TABLE = "#" DISHWASHER = "D" FLOOR_CELL = "." # Items NONE = "NONE" DISH = "DISH" ICE_CREAM = "ICE_CREAM" BLUEBERRIES = "BLUEBERRIES" location = {DISH: DISHWASHER, ICE_CREAM: ICE_CREAM_CRATE, BLUEBERRIES: BLUEBERRIES_CRATE, WINDOW: WINDOW} special = (BLUEBERRIES_CRATE, ICE_CREAM_CRATE, WINDOW, DISHWASHER) class Base(): def __repr__(self): return f"<{self.__class__.__name__}: {self.__dict__}>" class Customer(Base): def __init__(self, item, award): self.item = item self.award = int(award) class Cook(Base): def __init__(self, x, y, item): self.x = int(x) self.y = int(y) self.item = item self.order = "" @property def pos(self): return (self.x, self.y) def use(self, x, y, msg=""): print("USE", x, y, msg) def move(self, x, y): print("MOVE", x, y) def wait(self): print("WAIT") class Table(Base): def __init__(self, x, y, item): self.x = int(x) self.y = int(y) self.item = item class Oven(Base): def __init__(self, contents, timer): self.contents = contents self.timer = int(timer) class PathNode(tuple): def __new__(self, x, y, parent=None): n = tuple.__new__(self, (x, y)) n.parent = parent n.cost = 0 return n class Grid(Base): def __init__(self, cells): self.cells = cells self.w, self.h = len(cells[0]), len(cells) self.add_costs = {} def at(self, x, y): return self.cells[y][x] def flatten(self): return [(x, y, c) for y, row in enumerate(self.cells) for x, c in enumerate(row)] @property def coords(self): return [(x, y) for y in range(self.h) for x in range(self.w)] def where_are(self, content): return [(x, y) for x, y, c in self.flatten() if c == content] @staticmethod def distance(from_, to_): return abs(from_[0] - to_[0]) + abs(from_[1] - to_[1]) def closest(self, from_, content): return sorted([(c, Grid.distance(from_, c)) for c in self.where_are(content)], key=lambda k: k[1])[0] def neighbors(self, x, y, diags=False): neighs = [(x, y - 1), (x - 1, y), (x + 1, y), (x, y + 1)] if diags: neighs += [(x - 1, y - 1), (x + 1, y - 1), (x - 1, y + 1), (x + 1, y + 1)] return [(x, y) for x, y in neighs if 0 <= x < self.w and 0 <= y < self.h] def passable(self, x, y): return self.at(x, y) in (FLOOR_CELL, START_0, START_1) def cost(self, x, y): return 10 + self.add_costs.get((x, y), 0) def path(self, origin, target, incl_start=False): nodes = [] origin = PathNode(*origin) targets = grid.neighbors(*target, diags=True) heapq.heappush(nodes, (0, origin)) while nodes: current = heapq.heappop(nodes)[1] if current in targets: path = [] next_ = current while next_: if next_ != origin or incl_start: path.insert(0, next_) next_ = next_.parent return path neighbors = self.neighbors(*current, False) for x, y in neighbors: if not self.passable(x, y): continue cost = current.cost + self.cost(x, y) priority = cost + 10 * (abs(x - target[0]) + abs(y - target[1])) node = PathNode(x, y, current) node.cost = cost heapq.heappush(nodes, (priority, node)) else: return None # input vars num_all_customers = int(input()) all_customers = [Customer(*input().split()) for _ in range(num_all_customers)] grid = Grid([list(input()) for i in range(7)]) log(f"{num_all_customers} customers: {all_customers}") log(f"grid: {grid}") class Task(Base): def __init__(self, name, from_): self.name = name self.loc = location[name] self.pos, self.dist = grid.closest(from_, self.loc) while True: turns_remaining = int(input()) player = Cook(*input().split()) log(f"*** player: {player}") partner = Cook(*input().split()) log(f"*** partner: {partner}") num_tables_with_items = int(input()) # the number of tables in the kitchen that currently hold an item tables = [Table(*input().split()) for _ in range(num_tables_with_items)] log(f"*** tables: {tables}") oven = Oven(*input().split()) log(f"*** oven: {oven}") num_customers = int(input()) # the number of customers currently waiting for food customers = [Customer(*input().split()) for _ in range(num_customers)] log(f"*** customers: {customers}") ### SCRIPT # if no current order, take the most beneficial if not player.order: queue = sorted(customers, reverse=True, key=lambda x: x.award) player.order = queue[0].item.split('-') log(f'>>> new order taken: {player.order}') todo = [Task(t, player.pos) for t in player.order if t not in player.item] log(f"todo: {todo}") if not todo: # no task left, target is the window next_task = Task(WINDOW, player.pos) player.order, todo = [], [] elif player.item != NONE and not DISH in player.item: # cook has something in its hands and no dish, he have to take one next_task = next((t for t in todo if t.name == "DISH")) else: # else, go for the closest task tasks = sorted(todo, key= lambda x: x.dist) next_task = next(iter(tasks), None) log(f"next_task: {next_task}") # update grid movement costs following the probability of finding the partner here partner_could_be_there = [(x, y) for x, y in grid.coords if grid.passable(x, y) and grid.distance(partner.pos, (x, y)) <= 4] grid.add_costs = {} for x, y in partner_could_be_there: k1 = 2 if (x, y) == partner.pos else 1 # cell is next to a special cell, partner has more chance to stop there k2 = 2 if any((c for c in grid.neighbors(x, y) if grid.at(*c) in special )) else 1 grid.add_costs[(x, y)] = k1 * k2 * 3 log(grid.add_costs) path = grid.path(player.pos, next_task.pos) log(path) if path is not None: if len(path) > 0: if len(path) > 4: player.move(*path[3]) else: player.move(*path[-1]) else: player.use(*next_task.pos) else: player.use(*next_task.pos)