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