"""Fewest commands: clean the whole floor (Part 1 rules) with as few commands as possible. The true minimum is NP-hard to find, so this builds several good routes, keeps the shortest, and stops early when a route reaches the lower bound, which proves it is optimal. """ import random from collections import deque DIRS = [(-1, 0, '^'), (1, 0, 'v'), (0, -1, '<'), (0, 1, '>')] def parse(room): """Return (start, floor): the robot's start and the set of every field that isn't a wall.""" start, floor = None, set() for r, row in enumerate(room): for c, ch in enumerate(row): if ch != '#': floor.add((r, c)) if ch == '*': start = (r, c) return start, floor def steps(cell, allowed): """Yield (neighbour, command) for each neighbour of cell that is inside allowed.""" r, c = cell for dr, dc, go in DIRS: n = (r + dr, c + dc) if n in allowed: yield n, go def lower_bound(room): start, floor = parse(room) return route_lower_bound(start, floor, floor) def route_lower_bound(start, targets, walkable): """No route from start that visits every target (walking inside walkable) is shorter than this. - Each command reaches at most one new target: n - 1. - Steps alternate colours on a checkerboard, so the route needs enough steps of each colour. - Leaving a dead end means stepping back onto a visited field, except at the very end. """ targets = set(targets) | {start} n = len(targets) same = sum((r + c) % 2 == (start[0] + start[1]) % 2 for r, c in targets) other = n - same dead_ends = sum(1 for cell in targets if cell != start and sum(1 for _ in steps(cell, walkable)) == 1) return max(n - 1, 2 * same - 2, 2 * other - 1, n - 1 + max(0, dead_ends - 1)) def shortest_path(a, b, walkable): """[(command, field), ...] along a shortest path from a to b inside walkable.""" for n, go in steps(a, walkable): if n == b: return [(go, b)] parent = {a: None} queue = deque([a]) while b not in parent: cell = queue.popleft() for n, go in steps(cell, walkable): if n not in parent: parent[n] = (cell, go) queue.append(n) path = [] while b != a: prev, go = parent[b] path.append((go, b)) b = prev return path[::-1] def follow(start, order, walkable): """Visit fields in order along shortest paths; fields passed on the way count as cleaned.""" pos, cleaned, moves = start, {start}, [] for target in order: if target not in cleaned: for go, cell in shortest_path(pos, target, walkable): moves.append(go) cleaned.add(cell) pos = target return ''.join(moves) def first_option(options, seen, targets): return options[0] def fewest_exits(options, seen, targets): """Warnsdorff's rule: prefer the field with the fewest ways onward.""" return min(options, key=lambda n: sum(1 for m, _ in steps(n, targets) if m not in seen)) def tree_route(start, targets, walkable, choose): """Grow a depth-first tree over the targets, then visit it in preorder with the deepest branch last, so the route never walks back from its far end.""" parent, children, found = {start: None}, {start: []}, [start] stack = [start] while stack: options = [n for n, _ in steps(stack[-1], targets) if n not in parent] if not options: stack.pop() continue n = choose(options, parent, targets) parent[n], children[n] = stack[-1], [] children[stack[-1]].append(n) found.append(n) stack.append(n) height = dict.fromkeys(found, 0) for cell in reversed(found[1:]): height[parent[cell]] = max(height[parent[cell]], height[cell] + 1) order, stack = [], [start] while stack: cell = stack.pop() order.append(cell) stack.extend(sorted(children[cell], key=lambda k: -height[k])) # deepest is popped last order += [cell for cell in targets if cell not in parent] # targets the tree missed return follow(start, order, walkable) def greedy_route(start, targets, walkable, rng): """Step to the uncleaned neighbour with the fewest uncleaned neighbours (ties: keep going straight, then random); when stuck, walk to the nearest uncleaned field.""" cleaned, pos, heading, moves = {start}, start, None, [] left = len(targets) - 1 def exits(cell): return sum(1 for m, _ in steps(cell, targets) if m not in cleaned) while left: options = [(n, go) for n, go in steps(pos, targets) if n not in cleaned] if options: n, go = min(options, key=lambda o: (exits(o[0]), o[1] != heading, rng.random())) path = [(go, n)] else: path = path_to_nearest(pos, targets, walkable, cleaned, exits, rng) for go, cell in path: moves.append(go) if cell in targets and cell not in cleaned: cleaned.add(cell) left -= 1 heading, pos = path[-1] return ''.join(moves) def path_to_nearest(pos, targets, walkable, cleaned, exits, rng): """Shortest path to the closest uncleaned target, choosing among the closest by fewest exits. The search stops at the first layer holding an uncleaned target, so the path itself only crosses fields that are already clean (or aren't targets).""" parent, layer = {pos: None}, [pos] while True: nxt = [] for cell in layer: for n, go in steps(cell, walkable): if n not in parent: parent[n] = (cell, go) nxt.append(n) if not nxt: raise ValueError('some targets cannot be reached') found = [n for n in nxt if n in targets and n not in cleaned] if found: break layer = nxt cell = min(found, key=lambda n: (exits(n), rng.random())) path = [] while cell != pos: prev, go = parent[cell] path.append((go, cell)) cell = prev return path[::-1] def best_route(start, targets, walkable, runs=10, seed=0): """Shortest of several routes that visit every target; stops as soon as one is provably best.""" targets = set(targets) | {start} bound = route_lower_bound(start, targets, walkable) rng = random.Random(seed) makers = [lambda: tree_route(start, targets, walkable, first_option), lambda: tree_route(start, targets, walkable, fewest_exits)] makers += [lambda: greedy_route(start, targets, walkable, rng)] * runs best = None for make in makers: route = make() if best is None or len(route) < len(best): best = route if len(best) <= bound: break return best def solution(room, runs=10, seed=0): start, floor = parse(room) return best_route(start, floor, floor, runs, seed)