codeingame/code_mode/script.py

'''

@author: olivier.massot, 2019
'''
import heapq
import sys

DEBUG = True
def log(x):
    if DEBUG:
        print(x, file=sys.stderr)

# Cells
START_0 = '0'
START_1 = '1'
BLUEBERRIES_CRATE = "B"
ICE_CREAM_CRATE = "I"
STRAWBERRIES_CRATE = "S"
CHOPPING_BOARD = "C"
DOUGH_CRATE = "H"
WINDOW = "W"
EMPTY_TABLE = "#"
DISHWASHER = "D"
FLOOR_CELL = "."
OVEN = "O"

# Items
NONE = "NONE"
DISH = "DISH"
ICE_CREAM = "ICE_CREAM"
BLUEBERRIES = "BLUEBERRIES"
STRAWBERRIES = "STRAWBERRIES"
CHOPPED_STRAWBERRIES = "CHOPPED_STRAWBERRIES"
DOUGH = "DOUGH"
CROISSANT = "CROISSANT"


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 update(self, x, y, item):
        self.x = int(x)
        self.y = int(y)
        self.item = item
        
    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, content, timer):
        self.content = content
        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=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) 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)
        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}")

player = Cook(-1, -1, "")
partner = Cook(-1, -1, "")
oven = Oven(NONE, 0)


location = {DISH: DISHWASHER,
            ICE_CREAM: ICE_CREAM_CRATE,
            BLUEBERRIES: BLUEBERRIES_CRATE,
            STRAWBERRIES: STRAWBERRIES_CRATE,
            CHOPPED_STRAWBERRIES: CHOPPING_BOARD,
            CROISSANT: OVEN,
            DOUGH: DOUGH_CRATE,
            OVEN: OVEN,
            WINDOW: WINDOW}
special = list(location.values())

class Task(Base):
    def __init__(self, name, from_):
        self.name = name
        self.loc = location[name]
        self.pos, self.dist = grid.closest(from_, self.loc)


ingredients_for = {CHOPPED_STRAWBERRIES: STRAWBERRIES,
               CROISSANT: DOUGH}
needs_ingredients = list(ingredients_for.keys())


preparation_for = {STRAWBERRIES: CHOPPED_STRAWBERRIES,
                   DOUGH: CROISSANT}
needs_preparation = list(preparation_for.keys())

oven_time = {CROISSANT: 10}
needs_oven = list(oven_time.keys())


def whats_next(todo):
    if not todo:
        # no task left, target is the window
        return Task(WINDOW, player.pos)
    
    # special case: one or more ingredients needs preparation
    if any((t for t in todo if t.name in needs_ingredients)):
        
        # If cook has an ingredient in hands, he needs to prepare it
        if player.item in needs_preparation:
            return Task(preparation_for[player.item], player.pos)
    
        # If hands are free and an ingredient is needed, we go for it first except if it is already in the oven
        if player.item == NONE and any((t for t in todo if t.name in needs_ingredients and not t.name in oven.content)):
            return Task(next((ingredients_for[t.name] for t in todo if t.name in needs_ingredients)), player.pos)
        
        
        
#         
#         
#         # special case, one or more plates needs to be cooked
#         if any((t for t in todo if t.name in needs_oven)):
#             
#             # if oven has ended, go grab the oven's content
#             if oven.timer <=1 and any((t for t in todo if t.name in oven.content)):
#                 return Task(OVEN, player.pos)
#             
#             # if oven is empty, go fill it
#             if oven.content == NONE:
#                 return Task(next((ingredients_for[t.name] for t in todo if t.name in needs_oven)), player.pos)


        
    if player.item != NONE and not DISH in player.item:
        # cook has something in its hands and no dish, he have to take one
        return next((t for t in todo if t.name == DISH))

    # else, go for the closest task
    tasks = sorted(todo, key= lambda x: x.dist)
    return next(iter(tasks))


while True:
    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 = 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}")

    next_task = whats_next(todo)
    log(f"next_task: {next_task}")

    if next_task.name == WINDOW:
        player.order = []
    
    # 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)