''' @author: olivier.massot, 2019 ''' import heapq import sys DEBUG = True def log(x): if DEBUG: print(x, file=sys.stderr) # -- Base class class Base(): def __repr__(self): return f"<{self.__class__.__name__}: {self.__dict__}>" # --- locations class Location(Base): name = "" passable = False class SpecialLocation(Location): pass class DishWasher(SpecialLocation): pass class IcecreamCrate(SpecialLocation): pass class BlueberriesCrate(SpecialLocation): pass class StrawberriesCrate(SpecialLocation): pass class DoughCrate(SpecialLocation): pass class ChoppingBoard(SpecialLocation): pass class Oven(SpecialLocation): def __init__(self): self._content = None self._timer = 0 @property def content(self): return self._content @content.setter def content(self, content): self._content = match[content] @property def timer(self): return self._timer @timer.setter def timer(self, timer): self._timer = int(timer) def update(self, content, timer): self.content = content self.timer = timer class Window(SpecialLocation): pass class Start(Location): passable = True class Start0(Start): pass class Start1(Start): pass class FloorCell(Location): passable = True class EmptyTable(Location): pass locations = [DishWasher, IcecreamCrate, BlueberriesCrate, StrawberriesCrate, DoughCrate, ChoppingBoard, Oven, Window, Start0, Start1, FloorCell, EmptyTable] special_locations = [l for l in locations if l is SpecialLocation] tables = [] # -- Grid 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 is content] @staticmethod def distance(from_, to_): return abs(from_[0] - to_[0]) + abs(from_[1] - to_[1]) def items(self): return [c for row in self.cells for c in row] def closest_in(self, from_, coords): return sorted([(c, Grid.distance(from_, c)) for c in coords], key=lambda k: k[1])[0] def closest(self, from_, content): return self.closest_in(from_, self.where_are(content)) def neighbors(self, x, y, diags=True): 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).passable 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) 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 class Order(Base): def __init__(self, order): self.order = order class Dish(Base): location = DishWasher class BaseDessert(Base): name = "" class SimpleDessert(BaseDessert): location = None class PreparedDessert(BaseDessert): ingredients = [] class CookedDessert(BaseDessert): ingredients = [] class Ingredient(Base): location = None transformer = None class CookIngredient(): location = None cooking_time = 0 # --- desserts class IceCream(SimpleDessert): location = IcecreamCrate class Blueberries(SimpleDessert): location = BlueberriesCrate class Strawberries(Ingredient): location = StrawberriesCrate transformer = ChoppingBoard class ChoppedStrawberries(PreparedDessert): ingredients = [Strawberries] class Dough(CookIngredient): location = DoughCrate cooking_time = 10 class Croissant(CookedDessert): location = Oven ingredients = [Dough] class Customer(Base): def __init__(self, item, award): self.order = [match[i] for i in item.split('-')] self.award = int(award) class Table(Base): def __init__(self, x, y, item): self.x = int(x) self.y = int(y) self.item = [match[i] for i in item.split('-')] @property def pos(self): return (self.x, self.y) # --- Actions class Action(Base): needs_dish = False needs_hands = False def __init__(self, location): self.location = location def locate(self, player): self.pos, self.dist = grid.closest(player.pos, self.location) class GetAction(Action): def __init__(self, subject): self.subject = subject self.location = self.subject.location def locate(self, player): available = grid.where_are(self.location) available += [t.pos for t in tables if self.subject == [t.item]] self.pos, self.dist = grid.closest_in(player.pos, available) class GetDessert(GetAction): needs_dish = True class GetIngredient(GetAction): needs_hands = True class GetDish(GetAction): def __init__(self): super().__init__(Dish) class Transform(Action): def __init__(self, subject): self.location = subject.transformer class Cook(Action): def __init__(self): self.location = Oven class GetCookedDessert(GetDessert): def __init__(self, subject): super().__init__(subject) self.location = Oven class Deliver(Action): def __init__(self): self.location = Window class DropHanded(Action): def __init__(self): self.subject = None self.location = EmptyTable class GetOnTable(GetAction): def __init__(self, pos): self._pos = pos def locate(self, player): self.pos = self._pos self.dist = Grid.distance(player.pos, self._pos) class GetDishOnTable(GetOnTable): pass class Cooker(Base): def __init__(self): self._x = -1 self._y = -1 self._in_hand = [] self.order = [] @property def x(self): return self._x @x.setter def x(self, x): self._x = int(x) @property def y(self): return self._y @y.setter def y(self, y): self._y = int(y) @property def pos(self): return (self.x, self.y) @property def in_hand(self): return self._in_hand @in_hand.setter def in_hand(self, item): self._in_hand = [x for x in [match[i] for i in item.split('-')] if x is not None] def take_order(self, order): self.order = order def order_fullfilled(self): self.order = [] def update(self, x, y, item): self.x = x self.y = y self.in_hand = item @property def hands_free(self): return len(self._in_hand) == 0 @property def hands_full(self): return any(issubclass(i, Ingredient) for i in self._in_hand) @property def dish_handed(self): return Dish in self.in_hand def eval_orders(self, customers): waiting = sorted(customers, reverse=True, key=lambda x: x.award) self.take_order(waiting[0].order) def todo(self): todo = [] store = None for table in tables: if Dish in table.item and all((i in self.order and not i in self.in_hand) for i in table.item): store = table for item in self.order: if item in self.in_hand or (store and item in store.item): # already done continue if issubclass(item, SimpleDessert): todo.append(GetDessert(item)) elif issubclass(item, PreparedDessert): on_table = next((t for t in tables if [item] == t.item), None) if on_table: todo.append(GetOnTable(on_table.pos)) else: for ingredient in item.ingredients: if ingredient in self.in_hand: todo.append(Transform(ingredient)) else: todo.append(GetIngredient(ingredient)) elif issubclass(item, CookedDessert): on_table = next((t for t in tables if [item] in t.item), None) if on_table: todo.append(GetOnTable(on_table.pos)) else: for ingredient in item.ingredients: if ingredient in self.in_hand: todo.append(Cook()) elif type(item) == type(oven.content): todo.append(GetCookedDessert(item)) elif type(ingredient) == type(oven.content): if oven.timer < 3: todo.append(GetCookedDessert(item)) else: todo.append(GetIngredient(ingredient)) elif issubclass(item, Dish): todo.append(GetDish()) else: log(f" Unknown order: {item}") if store: todo.append(GetOnTable(store.pos)) # nothing left to do: deliver if not todo: todo = [Deliver()] # if the current order is not anymore in the queue, drop the dish if not self.order in [c.order for c in customers]: player.order = [] todo = [DropHanded()] for action in todo: action.locate(self) return todo def act(self, action): log("{}, {}, {}, {}".format(action.needs_hands, self.hands_free, isinstance(action, GetAction), self.hands_full)) if isinstance(action, Deliver) and action.pos in grid.neighbors(*self.pos): self.order = [] elif (action.needs_hands and not self.hands_free) or (isinstance(action, GetAction) and self.hands_full): # cannot act, needs to drop the dish log("need to drop") action = DropHanded() action.locate(self) self.use(*action.pos) 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") # --- constants match = { '0': Start0, '1': Start1, 'B': BlueberriesCrate, 'I': IcecreamCrate, 'S': StrawberriesCrate, 'C': ChoppingBoard, 'H': DoughCrate, 'W': Window, '#': EmptyTable, 'D': DishWasher, '.': FloorCell, 'O': Oven, 'NONE': None, 'DISH': Dish, 'ICE_CREAM': IceCream, 'BLUEBERRIES': Blueberries, 'STRAWBERRIES': Strawberries, 'CHOPPED_STRAWBERRIES': ChoppedStrawberries, 'DOUGH': Dough, 'CROISSANT': Croissant } # --- input vars num_all_customers = int(input()) all_customers = [Customer(*input().split()) for _ in range(num_all_customers)] grid = Grid([[match[c] for c in input()] for i in range(7)]) log(f"{num_all_customers} customers: {all_customers}") log(f"grid: {grid}") player = Cooker() partner = Cooker() oven = next((i for i in grid.items() if type(i) is Oven), Oven()) while True: # <--- turn input turns_remaining = int(input()) player.update(*input().split()) log(f"*** player: {player}") partner.update(*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.update(*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 awarded if not player.order: player.eval_orders(customers) log('>>> new order taken') log(f"order: {player.order}") todo = player.todo() log(f"todo: {todo}") priorities = [p for p in [ # order fulfilled: deliver next((a for a in todo if type(a) is Deliver), None), # something to take out from the oven! next((a for a in todo if type(a) is GetCookedDessert), None), # If cook has an ingredient in hands, he needs to prepare it next((a for a in todo if type(a) is Transform), None), # If cook has an cook_ingredient in hands, he needs to cook it next((a for a in todo if type(a) is Cook), None), # If hands are free and an ingredient is needed, we go for it first next((a for a in todo if a.needs_hands and player.hands_free), None), # there is a dish waiting on a table next((a for a in todo if type(a) is GetDishOnTable), None), # cook has a dessert in its hands and no dish, he have to take one next((a for a in todo if isinstance(a, GetDish) and any(h for h in player.in_hand if issubclass(h, BaseDessert))), None), ] if p is not None] if priorities: next_task = priorities[0] log(f"next task (priority): {next_task}") else: # else, go for the closest task tasks = sorted(todo, key=lambda x: x.dist) next_task = next(iter(tasks)) log(f"next task (closest): {next_task}") # <--- Update moving costs # 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 isinstance(grid.at(*c), SpecialLocation))) else 1 grid.add_costs[(x, y)] = k1 * k2 * 3 log(grid.add_costs) # ---> # <--- compute shortest path 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.act(next_task) else: player.act(next_task)