Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Newtonian movement solution in Clear category for Inertia by Rcp8jzd
from collections import deque
from typing import Iterable
from itertools import product
GEM, ROUGH, ICE, ROCK, MINE = "$. X*"
MOVES = {
"NW": (-1, -1),
"N": (-1, 0),
"NE": (-1, 1),
"W": (0, -1),
"E": (0, 1),
"SW": (1, -1),
"S": (1, 0),
"SE": (1, 1),
}
DIRECTIONS = {v: k for k, v in MOVES.items()}
def inertia(grid: tuple[str], start: tuple) -> Iterable[str]:
grid = list(map(list, grid))
height, width = len(grid), len(grid[0])
# Given a grid, and a start position (init_row, init_col), for all possible
# cardinal directions, give the travelled along tiles.
# This precomputation saves a lot of time, cutting the search tree.
paths = {}
deadends = []
gems = set()
for init_row, init_col in product(range(height), range(width)):
if grid[init_row][init_col] not in (GEM, ROUGH, ICE):
continue
elif grid[init_row][init_col] == GEM:
gems.add((init_row, init_col))
path_from = {}
for move, (drow, dcol) in MOVES.items():
path = []
row, col = init_row, init_col
while (
0 <= row + drow < height
and 0 <= col + dcol < width
and grid[row + drow][col + dcol] != ROCK
):
row, col = row + drow, col + dcol
path.append((row, col))
if grid[row][col] == ROUGH:
break
elif grid[row][col] == MINE:
break
if grid[row][col] != MINE and path:
path_from[move] = path
# Is there any way out from this position?
if path_from:
paths[init_row, init_col] = path_from
else:
deadends.append((init_row, init_col))
# Go the next gem and build the directions to catch them all!
directions = []
while gems:
# BFS to the next gem's position
visited = set()
came_from = {}
queue = deque([start])
end_pos = None
while queue and not end_pos:
current = queue.popleft()
for move, path in paths[current].items():
stop = path[-1]
if stop in deadends:
continue
# Exit the BFS: at least one gem found
if any(step in gems for step in path):
for step in path:
if step in gems:
gems.remove(step)
end_pos = stop
came_from[end_pos] = current, move
break
if stop not in visited:
queue.append(stop)
came_from[stop] = current, move
visited.add(stop)
# Build the reversed list of cardinal directions that lead to the gem(s)
current, move = came_from[end_pos]
gem_path = [move]
while current != start:
current, move = came_from[current]
gem_path.append(move)
gem_path.reverse()
# Move on to the next gem.
start = end_pos
directions.extend(gem_path)
return directions
Feb. 22, 2023
