''' @author: olivier.massot, 2019 ''' import heapq import itertools import sys def log(x): print(x, file=sys.stderr) # TODO: can I take ingredients not in order? If I can, find the shortest path trought all elements >> yes, but only one ingredient without a dish. # TODO: if partner on the way, wait if another path is 4+ cells longer # TODO: Should I tell wich I am doing to my partner? # TODO: When should I drop th plate on a table? # TODO: Check if a plate matching an order is already ready # TODO: don't take an order that is already taken by partner (how?) # Cells 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" crate = {DISH: DISHWASHER, ICE_CREAM: ICE_CREAM_CRATE, BLUEBERRIES: BLUEBERRIES_CRATE, WINDOW: WINDOW} 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 = "" self.plan = [] # self.todo = [] # self.current_target = "" @property def pos(self): return (self.x, self.y) def take_order(self, grid, order): self.grid = grid self.order = order # self.todo = order.split('-') self.update_plan() # self.current_target = where[self.plan[0]] def update_plan(self): todo = self.order.split('-') steps = [crate[t] for t in todo] # test different paths. DISH should be either first or second in the list, and window should be last. cases = [c for c in itertools.permutations(steps)] # special: dish can not be after second position: cases = [c for i, c in enumerate(cases) if not (i > 1 and c == DISH)] # window is always at the end: cases += [WINDOW] # multply cases by all combinations of coordinates exploded = [[self.grid.where_are(e) for e in case] for case in cases] routes = sum([list(itertools.product(*r)) for r in exploded], []) # take the shortest path shortest = min([r for r in routes], key=lambda r: len(self.grid.path_trough(self.pos, *r))) self.plan = shortest def act(self): # take the first action in the plan target = self.plan[0] # path = self.grid.path_to(self.pos, target) # if can act this turn, consider the action as completed if target in self.grid.neighbors(*self.pos): target.pop(0) self.use(target) if not self.plan: self.done() def done(self): self.order = "" self.plan = [] # self._objective = "" # self.todo = [] # self.current_target = "" # @property # def current_need(self): # for t in self.todo: # if not t in self.item: # return t # return NONE def use(self, x, y, msg=""): print("USE", x, y, msg) def move(self, x, y): print("MOVE", x, y) 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 NoPathFound(Exception): pass 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 def at(self, x, y): return self.cells[y][x] def is_in(self, x, y): try: self.at(x, y) return True except IndexError: return False def flatten(self): return [(x, y, c) for y, row in enumerate(self.cells) for x, c in enumerate(row)] def where_are(self, content): return [(x, y) for x, y, c in self.flatten() if c == content] def is_passable(self, x, y): return self.at(x, y) in (FLOOR_CELL, "0", "1") def closest(self, from_, content): return min(self.where_are(content), key=lambda k: (abs(from_[0] - k[0]) + abs(from_[1] - k[1]))) def neighbors(self, x, y): return [(xn, yn) for xn, yn in [(x - 1, y - 1), (x, y - 1), (x + 1, y - 1), \ (x - 1, y), (x + 1, y) , \ (x - 1, y + 1), (x, y + 1), (x + 1, y + 1)] if self.is_in(xn, yn)] def path_to(self, origin, target): nodes = [] origin = PathNode(*origin) heapq.heappush(nodes, (0, origin)) while nodes: current = heapq.heappop(nodes)[1] if current == target: break for x, y in self.neighbors(*current): node = PathNode(x, y, current) if not self.is_passable(*node): continue node.cost = current.cost + 1 priority = node.cost + (abs(node[0] - target[0]) + abs(node[1] - target[1])) heapq.heappush(nodes, (priority, node)) else: raise NoPathFound("no path were found to the targetted location {}".format(target)) result = [target] while current != origin: result.append(tuple(current)) current = current.parent result.append(origin) result.reverse() return result def path_trough(self, origin, *steps): return sum([self.path_to(origin, s) for s in steps], []) # 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}") 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}") # if no current order, take the most beneficial if not player.order: queue = sorted(customers, reverse=True, key=lambda x: x.award) # what is my partner doing? player.take_order(grid, queue[0].item) log(f'>>> new order taken: {player.order}') player.act() #print("WAIT") # log(f'todo: {player.todo}') # log(f'currently seeking: {player.current_need}') # if player.current_need == NONE: # target = WINDOW # log(f'current target: {target}') # player.done() # else: # target = where[player.current_need] # log(f'current target: {target}') # # closest = grid.closest(player.pos, target) # log(f"closest: {closest}") # player.use(*closest)