codeingame/last_crusade/script.py

'''

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


# TODO: what about the PIVOT_BACK in requirements?
# TODO: do not use a rock for interception if it is behind indiana
# 

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"

    def __init__(self, *args):
        super().__init__(*args)
        self.trajectory = None
        self.crash_on = None

class RockThreat(Rock):
    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
        
    def useless_pivot(self, pivot):
        return self.pivoted[pivot] == self.type
        
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 Trajectory(list):
    def __init__(self, *args):
        super().__init__(args)
        self.stops = []
        self.interceptions = []

    def elide(self, at):
        new_t = Trajectory(*self[:at])
        new_t.stops = self.stops
        return new_t
    
    def __repr__(self):
        return "<{},stops={},intercept:{}>".format(list(self), self.stops, self.interceptions)
    
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 = []
        self.deadend = False
    
    def __lt__(self, other):
        return self.pos < other.pos
    
    def __repr__(self):
        return f"<{self.pos}, pivot:{self.pivot}, cost:{self.cost}, round:{self.round}, require:{self.require}, deadend:{self.deadend}>"

class DeadEnd(Exception): 
    pass
class Collision(Exception): 
    pass

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 += reversed(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 collide(self, pos1, pos2, pivot=PIVOT_UNCHANGED):
        if pos1.coords != pos2.coords:
            return False
        if pos1.coords == self.exit:
            return False
        if pos1 == pos2:
            return True
        piece = self.get_cell(pos1.coords)
        if pivot:
            piece = turn(piece, pivot)
        if type(piece) in [Piece4, Piece5]:
            return piece.apply(pos1.face) == pos2.face
        if not piece.open_on(pos1.face) or not piece.open_on(pos2.face):
            return False
        return True
    
    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 interception_path(self, rock, target):
        subject = rock
        nodes = Queue()
        origin = PathNode(subject.pos)
        nodes.put(origin, 0)
        
        its, break_on = 0, 2000
        
        while nodes:
            current = nodes.get()
            
            its += 1
            if its > break_on:
                log("interception pathfinding broken")
                return None
            
            for at_ in range(len(target.trajectory)):
                if self.collide(current.pos, target.trajectory[at_]):
                    path = []
                    previous = current.parent
                    while previous:
                        if previous != origin:
                            path.insert(0, previous)
                        previous = previous.parent
                    return path, at_

            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)
            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
                    
                    priority = node.cost
                    nodes.put(node, priority)

        return []
    
    
    def update_rocks_moves(self):
        
        for rock in self.rocks:
            trajectory = Trajectory(*self.trajectory(rock))
            if trajectory:
                rock.crash_on = self.after(trajectory[-1])
            
            for i, pos in enumerate(trajectory):
                piece = self.cells[pos.coords]
                if piece.locked or i == 0:
                    continue
                
                # stops
                for pivot in [PIVOT_LEFT, PIVOT_RIGHT, PIVOT_BACK]:
                    if piece.useless_pivot(pivot):
                        continue
                    pos_after = self.after(pos, pivot)
                    if not pos_after or not self.get_cell(pos_after.coords).open_on(pos_after.face):
                        stop = (i, pivot)
                        trajectory.stops.append(stop)
                        break
            
            rock.trajectory = trajectory
        
        self.apply_collisions()
        
        for rock in self.rocks:
            # find an interception possibility
            for other in self.rocks:
                if rock is other:
                    continue
                res = self.interception_path(other, rock)
                if res:
                    path, at_ = res
                    if any(self.collide(self.indi.pos, n.pos) for n in path):
                        continue
                    rock.trajectory.interceptions += [(n.pos, n.pivot, at_) for n in path if n.pivot]
        
#         log([rock.trajectory for rock in self.rocks])
        log([rock.crash_on for rock in self.rocks])
          
    def apply_collisions(self):
        
        real_rocks = [rock for rock in self.rocks if type(rock) is Rock]
        if not real_rocks:
            return
        
        for turn in range(max([len(rock.trajectory) for rock in real_rocks])):
            
            for i in range(len(real_rocks)):
                for j in range(i+1, len(real_rocks)):
                    try:
                        if self.collide(real_rocks[i].trajectory[turn], real_rocks[j].trajectory[turn]):
                            log("Two rocks collide at ", real_rocks[i].trajectory[turn])
                            self.rocks[i].trajectory = self.rocks[i].trajectory.elide(turn + 1)
                            self.rocks[j].trajectory = self.rocks[j].trajectory.elide(turn + 1)
                    except IndexError:
                        pass
        
    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 = []
        current = 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 if with_start else path[1:]
    
    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 = set()
            
            deadend = False
            try:
                for rock in self.rocks:
                    
                    for round_ in (current.round +1, current.round):
                        if len(rock.trajectory) > round_ and self.collide(rock.trajectory[round_], next_pos):
                            alternatives = [Requirement(rock.trajectory[i], pivot, i) for i, pivot in rock.trajectory.stops if 0 < i <= round_]
        
                            if alternatives: 
                                require = alternatives[-1]
                                requirements.add(require)
                                break
                            
                            else:
                                interceptions = [Requirement(pos, pivot, i) for pos, pivot, i in rock.trajectory.interceptions if 0 < i <= round_]
                                if interceptions:
                                    requirements |= set(interceptions)
                            
                                elif type(rock) == Rock: #unstoppable rock
                                    log("node is deadend: ", next_pos.coords)
                                    raise DeadEnd
                        
            except DeadEnd:
                deadend = True
        
            for pivot, rotations in PIVOTS.items():
                if rotations > 0:
                    if next_cell.locked:
                        continue
                    elif next_cell.useless_pivot(pivot):
                        # useless rotation
                        continue
                    
                if current is origin and rotations > 1:
                    continue
                
                collision = False
                for rock in self.rocks:
                    if not type(rock) is Rock:
                        continue
                    if rock.crash_on and current.round + 1 == len(rock.trajectory) and self.collide(rock.crash_on, next_pos, pivot):
                        log(f"pivoting from {pivot} would lead to a collision at {next_pos}")
                        collision = True
                        break
                
                pivoted = turn(next_cell, pivot)
                if pivoted.open_on(next_pos.face):
                    node = PathNode(next_pos, current, pivot)
                    node.cost = current.cost + rotations + len(requirements) + 3 * deadend + 5 * collision
                    node.round = current.round + 1
                    node.require = requirements
                    node.deadend = deadend
                    
                    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):
        self.coords = coords[:2]
        self.pivot = pivot

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

    def __repr__(self):
        return f"<{self.command()}>"

    def __eq__(self, other):
        return self.coords == other.coords and self.pivot == other.pivot
        
    def __hash__(self):
        return 0

class Requirement(Action):
    def __init__(self, coords, pivot, last_chance_at):
        super().__init__(coords, pivot)
        self.last_chance_at = last_chance_at

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

    def __repr__(self):
        return f"<REQ {self.command()} before {self.last_chance_at}>"

# 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 = [None for _ in range(len(path))]
        
        # basic plan
        for i, node in enumerate(path):
            if node.pivot in [PIVOT_LEFT, PIVOT_RIGHT]:
                plan[i] = Action(node.pos, node.pivot)
            elif node.pivot == PIVOT_BACK:
                plan[i] = Action(node.pos, PIVOT_RIGHT)

        log("first plan:", plan)

        # add requirements
        requirements = set()
        for i, node in enumerate(path):
            if node.pivot == PIVOT_BACK:
                action = Requirement(node.pos, PIVOT_RIGHT, i)
                requirements.add(action)
            for action in node.require:
                requirements.add(action)
        
        log(requirements)
        
        for action in sorted(requirements, key=lambda x: x.last_chance_at):
            for j in range(action.last_chance_at - 1, -1, -1):
                if j < len(plan) and plan[j] is None:
                    plan[j] = action
                    break
            else:
                log("! action required could not be inserted: ", action)
        
        log("completed:", plan)
    else:
        log("no path, use previous plan")

    try:
        action = plan.pop(0)
        if not next((type(a) is Requirement for a in plan if not a is None), False):
            while plan and not action:
                action = plan.pop(0)
            
        if action:
            grid.apply(action)
            print(action.command())
        else:
            print("WAIT")
    except IndexError:
        print("WAIT")