cig/labyrinth/script.py

import heapq
import sys
import time


t0 = time.time()
def log(*msg):
    print("{} - ".format(str(time.time() - t0)[1:5]), *msg, file=sys.stderr)

class Queue():
    def __init__(self):
        self.items = []
    
    def __bool__(self):
        return bool(self.items)

    def __repr__(self):
        return str(self.items)

    def values(self):
        return (v for _, v in self.items)

    def put(self, item, priority):
        heapq.heappush(self.items, (priority, item))

    def fput(self, item, priority):
        while priority in [p for p, _ in self.items]:
            priority += 1
        self.put(item, priority)

    def get(self):
        return heapq.heappop(self.items)[1]


class PathNode(tuple):
    def __new__(self, x, y, parent=None):
        n = tuple.__new__(self, (x, y))
        n.parent = parent
        n.cost = 0
        return n
    
    def __repr__(self):
        return f"<{self[0]}, {self[1]}, c:{self.cost}>"

class Waypoint(tuple):
    def __new__(self, x, y, neighbors=None):
        n = tuple.__new__(self, (x, y))
        n.neighbors = neighbors or []
        return n

    def __repr__(self):
        return f"<({self[0]},{self[1]}), n:{self.neighbors}>"

MOVES = {(0, -1) : "UP", (0, 1): "DOWN", (-1, 0): "LEFT", (1, 0) : "RIGHT"}

h, w, countdown = [int(i) for i in input().split()]

UP = "UP"
RIGHT = "RIGHT"
DOWN = "DOWN"
LEFT = "LEFT"
MOVES = [UP, RIGHT, DOWN, LEFT]

class Grid():
    UNKNOWN = 0
    WALL = 1
    EMPTY = 2
    
    VECT = {UP: (0,-1), RIGHT: (1,0), DOWN: (0,1), LEFT: (-1,0)}
    INV = {UP: DOWN, RIGHT: LEFT, LEFT: RIGHT, DOWN: UP}
    
    def __init__(self, w, h):
        self.w = w
        self.h = h
        self.cells = {(x, y): Grid.UNKNOWN for x in range(self.w) for y in range(self.h)}
        self.start = None
        self.control_room = None
        self.kirk = None
        
        self.neighbors = {p: self.get_neighbors(*p) for p in self.cells}
        self.waypoints = []
        self.to_explore = None
        
    def update(self, kirk, scan):
        self.previous_pos = self.kirk
        self.kirk = kirk
        if not self.start:
            self.start = kirk
            
        for y, row in enumerate(scan):
            for x, c in enumerate(row):
                if c == "C":
                    self.control_room = (x, y)
                self.cells[(x, y)] = {"#": Grid.WALL, "?": Grid.UNKNOWN}.get(c, Grid.EMPTY)
        
        if self.to_explore is not None:
            if self.cells[self.to_explore] != Grid.UNKNOWN:
                self.to_explore = None
        
        self.update_corners()
        
    def _repr_cell(self, p, show=[]):
        if p == self.kirk:
            return "T"
        elif p == self.start:
            return "S"
        elif p == self.control_room:
            return "C"
        elif self.cells[p] == Grid.WALL:
            return "#"
        elif p in show:
            return "x"
        elif self.cells[p] == Grid.EMPTY:
            return "."
        else:
            return "?"
        
    def graph(self, show=[]):
        return "\n".join(["".join([self._repr_cell((x, y), show) for x in range(self.w)]) for y in range(self.h)])

    def set_visited(self, p):
        self.cells[p] = Grid.EMPTY
        
    def set_wall(self, p):
        self.cells[p] = Grid.WALL

    def unknown_gravity_center(self):
        wx, wy, wtotal = 0,0,0
        for x, y in self.cells:
            if self.cells[(x, y)] == Grid.UNKNOWN:
                wx += x
                wy += y
                wtotal += 1
        return (wx // wtotal, wy // wtotal) if wtotal else None

    @staticmethod
    def pos_after(current, move):
        x, y = current
        dx, dy = Grid.VECT[move]
        return x + dx, y + dy

    def get_move_to(self, p):
        return next(m for m in MOVES if grid.pos_after(grid.kirk, m) == p)
    
    @staticmethod
    def dist(p1, p2):
        xa, ya = p1
        xb, yb = p2
        return abs(xa - xb) + abs(ya - yb) 

    def get_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 line(self, x1, y1, x2, y2):
        # special case
        if (x1, y1) == (x2, y2):
            return [(x1, y1)]

        # diagonal symmetry
        vertically_oriented = (abs(y2 - y1) > abs(x2 - x1))
        if vertically_oriented:
            y1, x1, y2, x2 = x1, y1, x2, y2

        # horizontal symmetry
        reversed_sym = (x1 > x2)
        if reversed_sym:
            x2, y2, x1, y1 = x1, y1, x2, y2

        # angle
        dx, dy = x2 - x1, y2 - y1
        alpha = (abs(dy) / dx)

        offset = 0.0
        step = 1 if dy > 0 else -1

        result = []
        y = y1
        for x in range(x1, x2 + 1):
            if vertically_oriented:
                result.append((y, x))
            else:
                result.append((x, y))

            offset += alpha
            if offset > 0.5:
                y += step
                offset -= 1.0

        if reversed_sym:
            result.reverse()
        return result

    def _get_quarters(self, x, y):
        return {(x - 1, y - 1): [(x - 1, y), (x - 1, y - 1), (x, y - 1)], 
                (x + 1, y - 1): [(x, y - 1), (x + 1, y - 1), (x + 1, y)], 
                (x + 1, y + 1): [(x + 1, y), (x + 1, y + 1), (x, y + 1)], 
                (x - 1, y + 1): [(x, y + 1), (x - 1, y + 1), (x - 1, y)]}
        
    def update_corners(self):
        corners = set()
        for p, c in self.cells.items():
            if c == Grid.WALL:
                for corner, quarter in self._get_quarters(*p).items():
                    if all(self.cells.get(n, Grid.WALL) != Grid.WALL for n in quarter):
                        corners.add(corner)
        self.corners = list(corners)
        
    def way(self, start, target, known_only=False):
        nodes = Queue()
        origin = PathNode(*start)
        nodes.put(origin, 0)
        
        waypoints = set(self.corners) | {start, target}
        neighbors = {}
        
        passable = [Grid.EMPTY] if known_only else [Grid.EMPTY, Grid.UNKNOWN]
        
        for waypoint in waypoints:
            neighbors[waypoint] = []
            for other in waypoints:
                if other is waypoint:
                    continue
                sight = self.line(*other, *waypoint)[1:-1]
                if all(self.cells.get(p, Grid.WALL) in passable for p in sight) and not any(c in sight for c in self.corners):
                    neighbors[waypoint].append(other)
        
        while nodes:
            current = nodes.get()
            
            if current == target:
                path = []
                previous = current
                while previous:
                    if previous != start:
                        path.insert(0, previous)
                    previous = previous.parent
                return path

            for x, y in neighbors[current]:
                if (x, y) == current.parent or (x, y) == start:
                    continue

                cost = current.cost + Grid.dist((x, y), current)
                priority = cost + Grid.dist((x, y), target)
                
                node = PathNode(x, y, current)
                node.cost = cost
                nodes.put(node, priority)
                
        return None

    def path(self, start, target, known_only=False):
        nodes = Queue()
        origin = PathNode(*start)
        nodes.put(origin, 0)
        neighbors = []

        its, break_on, broken = 0, 10000, False

        self.costs = {}
        for p, c in self.cells.items():
            cost = 0
            if c == Grid.WALL:
                cost = -1
            elif known_only and c == Grid.UNKNOWN:
                cost = -1
            else:
                cost = 2 if c == Grid.UNKNOWN else 1
            self.costs[p] = cost
        
        while nodes:
            current = nodes.get()
            
            if current == target or broken:
                path = []
                previous = current
                while previous:
                    if previous != start:
                        path.insert(0, previous)
                    previous = previous.parent
                return path

            neighbors = self.neighbors[current]

            for x, y in neighbors:
                if (x, y) == current.parent:
                    continue

                its += 1
                if its > break_on:
                    broken = True
                    break

                if self.costs[(x, y)] < 0:
                    continue
                
                cost = current.cost + self.costs[(x, y)]
                priority = cost + Grid.dist((x, y), target)
                
                node = PathNode(x, y, current)
                node.cost = cost
                nodes.put(node, priority)
                
        return None

    def optim_path(self, origin, target, known_only=False, first_steps=False):
        way = self.way(origin, target, known_only)
        if way:
            if first_steps:
                path = self.path(origin, way[0], known_only)
            else:
                way.insert(0, origin)
                path = sum([self.path(start, target, known_only) for start, target in zip(way, way[1:])], [])
        else:
            path = self.path(origin, target, known_only)
        return path
    
    def propagation(self):
        # identify dead ends and visited
        propagation = {}
        for m in MOVES:
            visited= set()
            start = self.pos_after(self.kirk, m)
            if self.cells[start] == Grid.WALL:
                continue
             
            propagation[m] = 0
            buffer = [start]
            visited |= set(buffer)
             
            while buffer:
                new_buffer = []
                for p in buffer:
                    for n in self.neighbors[p]:
                        if not n in visited and \
                           not n in new_buffer and \
                           not n == self.kirk and \
                           not self.cells[n] == Grid.WALL:
                            new_buffer.append(n)
                            visited.add(n)
                            propagation[m] += 2 if self.cells[n] == Grid.UNKNOWN else 1
                buffer = new_buffer
        return propagation
    
    def discovery(self):
        # how many cells would be discovered thanks to each move
        discovery = {}
        for m in MOVES:
            pos= self.pos_after(self.kirk, m)
            if self.cells[pos] == Grid.WALL:
                continue
            discovery[m] = len([p for p in self.cells if self.dist(p, pos) <= 4 and self.cells[p] == Grid.UNKNOWN])
        return discovery
            
    def explore(self):
        if not self.to_explore is None:
            return self.to_explore
        
        buffer = [self.kirk]
        tested = set()
        
        while buffer:
            new_buffer = []
            for p in buffer:
                for n in self.neighbors[p]:
                    if n in tested:
                        continue
                    c = self.cells[n]
                    if c == Grid.UNKNOWN:
                        return n
                    if c != Grid.WALL:
                        new_buffer.append(n)
                    tested.add(n)
            buffer = new_buffer
            
        return None
            
    def explore2(self):
        q = Queue()
        propagation = self.propagation()
        discovery = self.discovery()
        
        unknown_center = self.unknown_gravity_center()
        
        log(f"* grav center: {unknown_center}")
        for m in propagation:
            new_pos = self.pos_after(self.kirk, m)
            if new_pos == self.control_room:
                continue
            iprop = 100 * propagation[m] // len(self.cells)
            idisc = 100 * discovery[m] // 16
            
            gofar = self.dist(grid.start, new_pos) > self.dist(self.start, self.kirk)
            unknown_gravity = self.dist(unknown_center, new_pos) < self.dist(unknown_center, self.kirk)
                
            goback = (new_pos == self.previous_pos)
            
            interest = -2 * iprop - idisc - 10 * gofar - 30 * unknown_gravity + 50 * goback
            
            log(m, iprop, idisc, gofar, unknown_gravity, goback, interest)
            q.fput(m, interest)
        
        return q.get()    
        
            
grid = Grid(w, h)
fuel = 1201
coming_back = False
turn = 0
comeback_found = None

while True:
    turn += 1
    fuel -= 1
    
    y, x = [int(i) for i in input().split()]
    grid.update((x, y), [list(input()) for j in range(grid.h)])
    
    if grid.kirk == grid.control_room:
        coming_back = True
    log("Position:", grid.kirk, "CR:", grid.control_room)
    log("Fuel:", fuel, "Countdown:", countdown)
    path = []
    
    if grid.control_room is None:
        log("> Looking for the control room")
        target = grid.explore()
        path = grid.optim_path(grid.kirk, target)
        next_move = grid.get_move_to(path[0])
    
    elif not coming_back:
        log("> Have found the control room")
        
        if not comeback_found:
            comeback = grid.optim_path(grid.control_room, grid.start, True)
        else:
            comeback = comeback_found
        log("comeback's length: ", len(comeback) if comeback else None)
        log("comeback: ", comeback)
        
        if not comeback:
            log("<!> Path to start can not be computed")
            if fuel > 300:
                log("<!> Path to start can not be computed: explore")
                target = grid.explore()
                path = grid.optim_path(grid.kirk, target)
                next_move = grid.get_move_to(path[0])
            else:
                log("<!> Path to start can not be computed: go to control room")
                path = grid.optim_path(grid.kirk, grid.control_room)
                next_move = grid.get_move_to(path[0])
                
        elif len(comeback) > countdown:
            log("<!> Path to start is to long, keep exploring")
            target = grid.explore()
            path = grid.optim_path(grid.kirk, target)
            next_move = grid.get_move_to(path[0])
            
        else:
            log("> Go to the control room")
            comeback_found = comeback
            path = grid.optim_path(grid.kirk, grid.control_room)
            next_move = grid.get_move_to(path[0])
    else:
        log("> Come back to the ship")
        path = grid.optim_path(grid.kirk, grid.start, True, True)
        next_move = grid.get_move_to(path[0])
        
    log("\n"+grid.graph(path))
        
    print(next_move)