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