Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Dijkstra solution in Clear category for Express Delivery by Phil15
START, GOAL, EMPTY, BOX, WATER = 'SE.BW'
MOVES = {'L': (0, -1), 'R': (0, 1), 'U': (-1, 0), 'D': (1, 0)}
def checkio(field_map):
""" Dijkstra algorithm to find shortest path to end from start,
thanks to deposit boxes available on this weird island. """
start, end = (next((i, j, 1) for i, row in enumerate(field_map)
for j, cell in enumerate(row) if cell == item)
for item in (START, GOAL)) # 1 means we hold the package.
nb_rows, nb_cols = len(field_map), len(field_map[0])
possible = lambda i, j: (0 <= i < nb_rows and 0 <= j < nb_cols and
field_map[i][j] != WATER)
def neighbors(i, j, hold_package):
""" Generate possible (action, time for it, new state) from state. """
if field_map[i][j] == BOX:
yield BOX, 1, (i, j, not hold_package)
for action, (di, dj) in MOVES.items():
if possible(i + di, j + dj):
yield action, 1 + hold_package, (i + di, j + dj, hold_package)
dist = {(i, j, hold_pack): float('inf') for i, row in enumerate(field_map)
for j, cell in enumerate(row)
if field_map[i][j] != WATER
for hold_pack in (True, False)}
states, parents, dist[start] = set(dist), dict(), 0
def reversed_path():
""" Trace back the path from end to start, thanks to parents dict. """
state = end
while state != start:
action, state = parents[state]
yield action
while states:
old = min(states, key = dist.get)
if old == end:
return ''.join(reversed(list(reversed_path())))
states.remove(old)
for action, time, new in neighbors(*old):
if dist[new] > dist[old] + time:
dist[new] = dist[old] + time
parents[new] = action, old # action change old into new.
Jan. 5, 2019
Comments:
