Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
v2: BFS to find gems, avoiding dead ends (detected by Kosaraju) solution in Clear category for Inertia by Phil15
# Tested on a 100x100 grid too! Too long on a 100x200 grid, I interrupted.
from typing import Tuple, Iterable
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)}
def inertia(grid: Tuple[str], start: Tuple[int]) -> Iterable[str]:
""" Path to find all gems on the icefield avoiding mines and dead ends. """
nb_rows, nb_cols = len(grid), len(grid[0])
def possible(i, j):
""" Be on the icefield and not on rocks. """
return 0 <= i < nb_rows and 0 <= j < nb_cols and grid[i][j] != ROCK
def movement(position, move):
""" What happens if I do this move from this position? """
(i, j), (di, dj), gems, dead = position, MOVES[move], set(), False
while possible(i + di, j + dj):
i, j = i + di, j + dj
if grid[i][j] == GEM:
gems.add((i, j))
elif grid[i][j] in (ROUGH, MINE):
dead = grid[i][j] == MINE
break
return dead, (i, j), gems
def neighbors(position):
""" Try all directions, keep good ones. """
for move in MOVES:
dead, new_position, gems = movement(position, move)
if not dead and new_position != position and \
new_position not in deadends: # avoid deadends.
yield move, new_position, gems
def find_gem(start):
""" Find the closest gem to start, thanks to BFS. """
queue = [([], start)] # (path from start, current position) queue
visited = set()
while queue:
path, position = queue.pop(0)
visited.add(position)
for move, new_position, gems in neighbors(position):
collect = gems & uncollected_gems
if collect:
return path + [move], new_position, collect
if new_position not in visited:
queue.append((path + [move], new_position))
deadends = set()
# 1) Compute the graph of possible moves thanks to DFS from start.
graph, stack = {}, [start]
while stack:
position = stack.pop()
graph[position] = [new_pos for _, new_pos, _ in neighbors(position)]
stack.extend(n for n in graph[position] if n not in graph)
# 2) Know all dead ends in this graph thanks to Kosaraju's algorithm.
# A bit too powerful for this task but we could (with improvements)
# solve this task without the first precondition.
for component in kosaraju(graph):
if start not in component:
deadends |= component
# 3) Now simply collect gems avoiding deadends.
uncollected_gems = {(i, j) for i, row in enumerate(grid)
for j, cell in enumerate(row) if cell == GEM}
while uncollected_gems:
path, start, gems = find_gem(start)
uncollected_gems -= gems
yield from path
def kosaraju(graph):
""" Kosaraju's algorithm to know strongly connected components.
Post-order DFS on the graph, and DFS on the transpose graph. """
order = list(iterative_postorder_dfs(graph))
# DFS on the transpose graph following the order.
transposed = transpose_graph(graph)
visited = {v: False for v in transposed}
while order:
start = order.pop()
if not visited[start]:
component = set()
stack = [start]
while stack:
v = stack.pop()
visited[v] = True
component.add(v)
for w in transposed[v]:
if not visited[w]:
stack.append(w)
yield component
def transpose_graph(graph):
""" Reverse all edges from the directed graph, into a new one. """
gT = {}
for v in graph:
for neighbor in graph[v]:
gT.setdefault(neighbor, []).append(v)
return gT
def iterative_postorder_dfs(graph):
""" An iterative implementation of DFS with post-order:
A node is yielded after exploration of its neighbors. """
# Iterative implementation complicates things but recursion have a limit.
visited = {node: False for node in graph}
while True:
try:
start = next(node for node, visit in visited.items() if not visit)
except StopIteration:
break
to_do = [(True, start)] # dfs stack
while to_do:
continue_exploration, node = to_do.pop()
if not continue_exploration:
yield node
else:
to_do.append((False, node)) # will be popped after its neighbors
visited[node] = True
neighbors = [n for n in graph[node] if not visited[n]]
for n in reversed(neighbors):
to_do.append((True, n))
Dec. 26, 2018