cig/last_crusade.py

'''

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


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

TOP = 0
LEFT = 1
RIGHT = 2
BOTTOM = 3
DIRS = {TOP: (0, -1), BOTTOM: (0, 1), RIGHT: (1, 0), LEFT: (-1, 0)}

PIVOT_UNCHANGED = 0
PIVOT_LEFT = 1
PIVOT_RIGHT = 2
PIVOT_BACK = 3
PIVOTS = {PIVOT_UNCHANGED: 0, PIVOT_LEFT: 1, PIVOT_RIGHT: 1, PIVOT_BACK: 2}
COMMAND = {PIVOT_LEFT: "LEFT", PIVOT_RIGHT: "RIGHT"}

SYM = {TOP: BOTTOM, BOTTOM: TOP, LEFT: RIGHT, RIGHT: LEFT}


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]
    
    def fget(self):
        return heapq.heappop(self.items)

class Position(tuple):
    def __new__(self, x, y, face):
        n = tuple.__new__(self, (x, y,face))
        return n
    
    @property
    def x(self):
        return self[0]
    
    @property
    def y(self):
        return self[1]
    
    @property
    def coords(self):
        return self[:2]
    
    @property
    def face(self):
        return self[2]
    
class Item():
    def __init__(self, x, y, side):
        self.pos = Position(x, y, side)
    
    @classmethod
    def from_input(cls, x, y, strface):
        return cls(int(x), int(y), ["TOP", "LEFT", "RIGHT", "BOTTOM"].index(strface))

class Indi(Item):
    graph = "I"

class Rock(Item):
    graph = "R"

class RockThreat(Item):
    graph = "T"

class Piece():
    type = 0
    pipes = {}
    pivoted = {PIVOT_LEFT: 0, PIVOT_RIGHT: 0, PIVOT_BACK: 0}
    graph = ["...",
             "...",
             "..."]
    
    def __init__(self, x, y, locked=False):
        self.x = int(x)
        self.y = int(y)
        self.locked = locked

    def __repr__(self):
        return "<{}{}:{}>".format(self.type, "X"*self.locked, (self.x, self.y))

    def result(self, from_):
        return self.pipes[from_]

    def open_on(self, face_in):
        return face_in in self.pipes
    
    def apply(self, face_in):
        return self.pipes.get(face_in, None)
        
    def connects(self, face_in, face_out):
        return self.apply(face_in) == face_out
        
class Piece0(Piece):
    pass
    
class Piece1(Piece0):
    type = 1
    pipes = {TOP: BOTTOM, RIGHT: BOTTOM, LEFT: BOTTOM}
    pivoted = {PIVOT_LEFT: 1, PIVOT_RIGHT: 1, PIVOT_BACK: 1}
    graph = ["x x",
             "   ",
             "x x"]

class Piece2(Piece0):
    type = 2
    pipes = {LEFT: RIGHT, RIGHT: LEFT}
    pivoted = {PIVOT_LEFT: 3, PIVOT_RIGHT: 3, PIVOT_BACK: 2}
    graph = ["xxx",
             "   ",
             "xxx"]

class Piece3(Piece0):
    type = 3
    pipes = {TOP: BOTTOM}
    pivoted = {PIVOT_LEFT: 2, PIVOT_RIGHT: 2, PIVOT_BACK: 3}
    graph = ["x x",
             "x x",
             "x x"]
        
class Piece4(Piece0):
    type = 4
    pipes = {TOP: LEFT, RIGHT: BOTTOM}
    pivoted = {PIVOT_LEFT: 5, PIVOT_RIGHT: 5, PIVOT_BACK: 4}
    graph = ["x x",
             " / ",
             "x x"]
    
class Piece5(Piece0):
    type = 5
    pipes = {LEFT: BOTTOM, TOP: RIGHT}
    pivoted = {PIVOT_LEFT: 4, PIVOT_RIGHT: 4, PIVOT_BACK: 5}
    graph = ["x x",
             " \ ",
             "x x"]

class Piece6(Piece0):
    type = 6
    pipes = {LEFT: RIGHT, RIGHT: LEFT}
    pivoted = {PIVOT_LEFT: 9, PIVOT_RIGHT: 7, PIVOT_BACK: 8}
    graph = ["x x",
             "   ",
             "xxx"]

class Piece7(Piece0):
    type = 7
    pipes = {TOP: BOTTOM, RIGHT: BOTTOM}
    pivoted = {PIVOT_LEFT: 6, PIVOT_RIGHT: 8, PIVOT_BACK: 9}
    graph = ["x x",
             "x  ",
             "x x"]

class Piece8(Piece0):
    type = 8
    pipes = {RIGHT: BOTTOM, LEFT: BOTTOM}
    pivoted = {PIVOT_LEFT: 7, PIVOT_RIGHT: 9, PIVOT_BACK: 6}
    graph = ["xxx",
             "   ",
             "x x"]

class Piece9(Piece0):
    type = 9
    pipes = {TOP: BOTTOM, LEFT: BOTTOM}
    pivoted = {PIVOT_LEFT: 8, PIVOT_RIGHT: 6, PIVOT_BACK: 7}
    graph = ["x x",
             "  x",
             "x x"]

class Piece10(Piece0):
    type = 10
    pipes = {TOP: LEFT}
    pivoted = {PIVOT_LEFT: 13, PIVOT_RIGHT: 11, PIVOT_BACK: 12}
    graph = ["x x",
             "  x",
             "xxx"]

class Piece11(Piece0):
    type = 11
    pipes = {TOP: RIGHT}
    pivoted = {PIVOT_LEFT: 10, PIVOT_RIGHT: 12, PIVOT_BACK: 13}
    graph = ["x x",
             "x  ",
             "xxx"]

class Piece12(Piece0):
    type = 12
    pipes = {RIGHT: BOTTOM}
    pivoted = {PIVOT_LEFT: 11, PIVOT_RIGHT: 13, PIVOT_BACK: 10}
    graph = ["xxx",
             "x  ",
             "x x"]

class Piece13(Piece0):
    type = 13
    pipes = {LEFT: BOTTOM}
    pivoted = {PIVOT_LEFT: 12, PIVOT_RIGHT: 10, PIVOT_BACK: 11}
    graph = ["xxx",
             "  x",
             "x x"]

classes = [Piece0, Piece1, Piece2, Piece3, Piece4, 
          Piece5, Piece6, Piece7, Piece8, Piece9, 
          Piece10, Piece11, Piece12, Piece13]


def new_piece(x, y, v):
    x, y, v = int(x), int(y), int(v)
    type_, locked = abs(v), v < 0
    piece = classes[type_](x, y, locked)
    return piece

def turn(piece, pivot):
    if pivot == PIVOT_UNCHANGED:
        return piece
    if piece.locked:
        raise Exception("can not pivot a locked piece")
    pivoted_type = piece.pivoted[pivot]
    if pivoted_type == piece.type:
        return piece
    return classes[pivoted_type](piece.x, piece.y)

class PathNode():
    def __init__(self, position, parent=None, pivot=PIVOT_UNCHANGED):
        self.pos = position
        self.pivot = pivot
        
        self.parent = parent
        self.cost = 0
        
        self.round = 0
        self.require = []
    
    def __lt__(self, other):
        return self.pos < other.pos
    
    def __repr__(self):
        return f"<{self.pos}, pivot:{self.pivot}, cost:{self.cost}>"


class Grid():
    
    def __init__(self, w, h, rows, x_exit):
        self.w = w
        self.h = h
        self.cells = {(x, y): new_piece(x, y, v) for y, row in enumerate(rows) for x, v in enumerate(row)}
        
        # add exit
        self.exit = (x_exit, h)
        self.cells[(x_exit, h)] = Piece1(x_exit, h, locked=True)
        
        self.indi = None
        self.rocks = []
    
    def get_cell(self, coords):
        return self.cells.get(coords, Piece0(*coords))
    
    def update(self, indi, rocks):
        self.indi = indi
        self.rocks = rocks

        self.include_threats()
        self.update_rocks_moves()
    
    @property
    def items(self):
        return [self.indi] + self.rocks
        
    def graph(self):
        res = "\n   "
        res += "".join([f"{x:02d} " for x in range(self.w)])
        res += "\n"
        
        items = []
        if self.indi:
            items.append(self.indi)
        items += self.rocks
        
        for y in range(self.h):
            for i in range(3):
                if i ==0:
                    res += "{:02d} ".format(y)
                else:
                    res += "   "
                for x in range(self.w):
                    piece = grid.cells[(x, y)]
                    line = list(piece.graph[i])
                    
                    for item in items:
                        if item.pos.coords == (x, y):
                            if item.pos.face == TOP and i == 0:
                                line[1] = item.graph
                            elif item.pos.face == RIGHT and i == 1:
                                line[2] = item.graph
                            elif item.pos.face == LEFT and i == 1:
                                line[0] = item.graph
                            elif item.pos.face == BOTTOM and i == 2:
                                line[1] = item.graph
                    if item.pos.x == x_exit and item.pos.y == h - 1 and i == 2:
                        line[1] = "E"
                    
                    line = "".join(line)
                    if piece.locked:
                        line = line.replace("x", "#")
                    res += line
#                     res += "|"
                res += "\n"
                
        return res
    
    def item_at(self, x, y, side=None):
        return next((i.pos.coords == (x, y) and (side is None or i.pos.face == side) for i in self.items), None)
    
    @staticmethod
    def dist(p1, p2):
        xa, ya = p1
        xb, yb = p2
        return abs(xa - xb) + abs(ya - yb) 
    
    def include_threats(self):
        
        threats = []
        for p, cell in self.cells.items():
            x, y = p
            
            if x == 0:
                if LEFT in cell.pipes and not self.item_at(x, y):
                    threats.append(RockThreat(x, y, LEFT))
            elif x == (self.w - 1) and not self.item_at(x, y):
                if RIGHT in cell.pipes:
                    threats.append(RockThreat(x, y, RIGHT))
            
            if y == 0:
                if TOP in cell.pipes and not self.item_at(x, y):
                    threats.append(RockThreat(x, y, TOP))

        self.rocks += threats
    
    def update_rocks_moves(self):
        self.trajectories = []
        
        for rock in self.rocks:
            trajectory = self.trajectory(rock)
            is_threat = isinstance(rock, RockThreat)
            if is_threat:
                # to simulate the 1 turn delay before arriving
                trajectory.insert(0, rock.pos)
            
            stops = []
            for i, pos in enumerate(trajectory):
                piece = self.cells[pos.coords]
                if piece.locked or i == 0:
                    continue
                for pivot in [PIVOT_LEFT, PIVOT_RIGHT, PIVOT_BACK]:
                    pivoted = turn(piece, pivot)
                    if not pivoted.open_on(pos.face):
                        stop = (i, pivot)
                        stops.append(stop)
                        break
            
            self.trajectories.append((trajectory, stops, is_threat))
        log(self.trajectories)
            
    def after(self, position, pivot=PIVOT_UNCHANGED):
        x, y, face = position
        piece = self.cells[(x, y)]
        piece = turn(piece, pivot)
        face_out = piece.apply(face)
        if face_out is None:
            return None
        dx, dy = DIRS[face_out]
        position = Position(x+dx, y+dy, SYM[face_out])
        return position
    
    def trajectory(self, item, with_start=True):
        path = []
        if with_start:
            path.append(item.pos)
        current = self.after(item.pos)
        while current is not None:
            path.append(current)
            next_pos = self.after(current)
            if not next_pos or next_pos.coords == self.exit or not self.get_cell(next_pos.coords).open_on(next_pos.face):
                break
            current = self.after(current)
        return path
    
    def path(self):
        subject = self.indi
        
        nodes = Queue()
        origin = PathNode(subject.pos)
        nodes.put(origin, 0)
        
        its, break_on = 0, 6000
        broken = False
        
        while nodes:
            current = nodes.get()
            
            its += 1
            if its > break_on:
                log("pathfinding broken")
                broken = True
            
            if broken or current.pos.coords == self.exit:
                path = []
                previous = current.parent
                while previous:
                    if previous != origin:
                        path.insert(0, previous)
                    previous = previous.parent
                return path

            next_pos = self.after(current.pos, current.pivot)
            if next_pos is None:
                log(f"! Next piece doesn't exist: ", current.pos, current.pivot)
                continue

            next_cell = self.get_cell(next_pos.coords)
            requirements = []
            
            deadend = False
            for trajectory, stops, is_threat in self.trajectories:
                if len(trajectory) > (current.round + 1) and trajectory[(current.round + 1)].coords == next_pos.coords:
                    
                    alternatives = [Action(trajectory[i], pivot) for i, pivot in stops if 0 < i <= (current.round + 1)]
                    
                    require = next(iter(alternatives), None)
                    if require is None: 
                        if not is_threat: #unstoppable rock
                            deadend = True
                            log("node is deadend: ", next_pos.coords)
                            break
                        else:
                            continue
                    
                    if len(alternatives) == 1:
                        require.last_chance = True
                    
                    requirements.append(require)
            if deadend:
                continue
            
            for pivot, rotations in PIVOTS.items():
                if rotations > 0:
                    if next_cell.locked:
                        continue
                    elif next_cell.pivoted[pivot] == next_cell.type:
                        # useless rotation
                        continue
                if current is origin and rotations > 1:
                    continue
                
                pivoted = turn(next_cell, pivot)
                
                if pivoted.open_on(next_pos.face):
                    node = PathNode(next_pos, current, pivot)
                    node.cost = current.cost + rotations
                    node.round = current.round + 1
                    node.require = requirements
                    
                    priority = node.cost
                    nodes.put(node, priority)

        return []

    def apply(self, action):
        self.cells[action.coords] = turn(self.cells[action.coords], action.pivot)

class Action():
    def __init__(self, coords, pivot, last_chance=False):
        self.coords = coords[:2]
        self.pivot = pivot
        self.last_chance = last_chance

    def command(self):
        return "{} {} {}".format(*self.coords, COMMAND[self.pivot])

    def __repr__(self):
        return f"<{self.command()}, last_chance: {self.last_chance}>"
    
    def __lt__(self, other):
        return self.last_chance and not other.last_chance or self.coords < other.coords

# Get input
w, h = [int(i) for i in input().split()]
rows = [input().split() for _ in range(h)]
x_exit = int(input())

# instanciate grid
grid = Grid(w, h, rows, x_exit)

while True:
    # get input
    indi = Indi.from_input(*input().split())
    rocks = [Rock.from_input(*input().split()) for _ in range(int(input()))]
    
    # update grid
    grid.update(indi, rocks)
    log(grid.graph())
    
    path = grid.path()
    log(path)
    
    if path:
        plan = []
        
        requirements = []
        for i, node in enumerate(path):
            if node.pivot == PIVOT_BACK:
                action = Action(node.pos, PIVOT_RIGHT, i <= 1)
                log("Node requirement: ", action)
                if i <= 1:
                    requirements.insert(0, action)
                else:
                    requirements.append(action)
                
            for action in node.require:
                log("Node requirement: ", action)
                if action.last_chance:
                    requirements.insert(0, action)
                else:
                    requirements.append(action)
                
                
        for i, node in enumerate(path):
            
            if node.pivot in [PIVOT_LEFT, PIVOT_RIGHT]:
                plan.append(Action(node.pos, node.pivot))
            elif node.pivot == PIVOT_BACK:
                plan.append(Action(node.pos, PIVOT_RIGHT))
            else:
                if requirements:
                    action = requirements.pop(0)
                    plan.append(action)
                
        log(plan)
    else:
        log("no path, use previous plan")

    try:
        action = plan.pop(0)
        grid.apply(action)
        print(action.command())
    except IndexError:
        print("WAIT")