Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
43-liner: base x4 solution in Speedy category for Inertia by przemyslaw.daniel
def init(grid):
from itertools import product
height, width, result = len(grid), len(grid[0]), {}
valid = {(x, y) for x, y in product(range(height), range(width))
if grid[x][y] != 'X'}
for x, y in valid:
neighbors = [(-1, 0, 'N'), (-1, 1, 'NE'), (0, 1, 'E'), (1, 1, 'SE')]
neighbors += [(1, 0, 'S'), (1, -1, 'SW'), (0, -1, 'W'), (-1, -1, 'NW')]
for dx, dy, direct in neighbors:
sx, sy, found = x, y, set()
while True:
if grid[sx][sy] == '$':
found |= {(sx, sy)}
if grid[sx][sy] == '*':
break
if (sx+dx, sy+dy) not in valid:
break
sx, sy = sx+dx, sy+dy
if grid[sx][sy] == '.':
break
if grid[sx][sy] in ' .$' and (sx, sy) != (x, y):
move = [direct, sx, sy, found]
result[(x, y)] = result.get((x, y), []) + [move]
for pos in result: # remove dead ends
result[pos] = [[direct, x, y, found] for direct, x, y, found in result[pos]
if (x, y) in result]
return result
def inertia(grid, start):
from heapq import heappop, heappush
moves, gems = init(grid), ''.join(grid).count('$')
queue, visited = [(0, set(), start, [])], set()
while queue:
_, gems_found, (x, y), path = heappop(queue)
if len(gems_found) == gems:
return path
for direct, sx, sy, found in moves[(x, y)]:
_found = found | gems_found
if (sx, sy, len(_found)) in visited:
continue
visited |= {(sx, sy, len(gems_found))}
heappush(queue, (-len(_found), _found, (sx, sy), path+[direct]))
Jan. 9, 2019
