Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
analyze then combine segments solution in Clear category for Express Delivery by Leonix
import itertools, heapq, contextlib
def checkio(field_map):
# Prepare data structures and find all points of interest
grid = { x + y*1j: val for y, row in enumerate(field_map) for x, val in enumerate(row)}
poi = [c for c, v in grid.items() if v in 'SBE']
start = next(c for c in poi if grid[c] == 'S')
end = next(c for c in poi if grid[c] == 'E')
boxes = [c for c in poi if c != start and c != end]
# Calculate best route to travel from each point of interest to each
segments = { c: analyze(grid, c) for c in poi if c != end }
# Figure out best route overall using segments calculated above.
best_path = segments[start][end]
best_cost = len(best_path)*2
for box1, box2 in itertools.permutations(boxes, 2):
with contextlib.suppress(KeyError):
cost = 2*len(segments[start][box1]) + 1 + len(segments[box1][box2]) + 1 + 2*len(segments[box2][end])
if cost < best_cost:
best_path = segments[start][box1] + 'B' + segments[box1][box2] + 'B' + segments[box2][end]
best_cost = cost
return best_path
def analyze(grid, start):
""" For each cell in grid, find best path from start to the cell in question (if reachable). """
counter = 1
result = { start: '' }
frontier = [ (0, 0, start) ]
while frontier:
_, _, start = heapq.heappop(frontier)
for next_direction, next_coord in neighbours(start):
if next_coord in result or next_coord not in grid or grid[next_coord] == 'W':
continue
heapq.heappush(frontier, (dist(next_coord, start), counter, next_coord))
result[next_coord] = result[start] + next_direction
counter += 1 # counter is here for heapq to never attempt to compare complex numbers
return result
def neighbours(c):
""" All places connected to given point. """
return [('D',c+1j), ('R',c+1), ('U',c-1j), ('L',c-1)]
def dist(start, goal):
""" Manhattan distance between given points. """
return abs((start-goal).real) + abs((start-goal).imag)
Sept. 27, 2021
Comments:
