Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Backtracking to avoid dead ends, BFS to find gems solution in Clear category for Inertia by Phil15
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) -> 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) = position, MOVES[move]
gems, dead = 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: # don't repeat past mistakes.
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, pos = queue.pop(0)
visited.add(pos)
for move, position, gems in neighbors(pos):
collect = gems & uncollected_gems
if collect:
yield path + [move], position, collect
if position not in visited:
queue.append((path + [move], position))
def backtracking(position): # RecursionError with more than 1000 gems.
""" Recursively find all gems, avoiding dead ends. """
nonlocal uncollected_gems
if not uncollected_gems:
return True
for path, new_position, gems in find_gem(position):
paths.append(path)
uncollected_gems -= gems
if backtracking(new_position):
return True
deadends.add(new_position)
uncollected_gems |= gems
paths.pop()
# Oops... I'm at a dead end.
uncollected_gems = {(i, j) for i, row in enumerate(grid)
for j, cell in enumerate(row) if cell == GEM}
paths, deadends = [], set()
if backtracking(start):
for path in paths:
yield from path
Dec. 22, 2018
