codeingame/code_mode/solution_wood.py

'''

@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)