Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in 3rd party category for Express Delivery by Somebody12345678910
"""
Find the express delivery route using the A* algorithm
"""
import heapq
from collections import namedtuple
import numpy as np
# The possible directions
DIRECTIONS = {
"L": (0, -1),
"R": (0, 1),
"U": (-1, 0),
"D": (1, 0)
}
def distance(point, goal):
"""
Return an admissible heuristic for the distance from point to goal.
For the case of a grid with orthogonal movement, use the Manhattan distance.
"""
return abs(point[0] - goal[0]) + abs(point[1] - goal[1])
def find(map, char):
"""
Return a tuple containing the index of the desired char inside map.
There must be only one instance of char in map.
"""
row, col = np.where(map == char)
if len(row) != 1 or len(col) != 1:
raise RuntimeError('{0} not found or multiple instances of {0} found'.format(char))
return row[0], col[0]
# Every cell of the map has the following properties:
# - hist: heuristic (cost + distance from goal)
# - cost: total time for delivery
# - box: whether the box is being carried or not
# - coord: the coordinates of the cell
# - action: last action
# - prev: the previous cell in the path
Cell = namedtuple('Cell', ['hist', 'cost', 'box', 'coord', 'action', 'prev'])
def checkio(field_map):
# convert to numpy matrix
map = np.matrix([list(row) for row in field_map])
# get the shape
height, width = map.shape
# find the start and the goal coordinates on map
start = find(map, 'S')
goal = find(map, 'E')
# create the frontier, initialized with start cell
frontier = [Cell(distance(start, goal), 0, True, start, None, None)]
# the set of visited cells
visited = set()
# iterate until the frontier is empty
while frontier:
# get the item with the lowest heuristic
current = heapq.heappop(frontier)
# unpack the tuple
_, cost, box, coord, action, prev = current
# if the cell has been already visited (to be checked
# both with and without box), skip
if (coord, box) in visited:
continue
# goal reached while holding the box
if coord == goal and box:
break
# flag the current cell as visited
visited.add((coord, box))
# initialize possible actions: copy from DIRECTIONS
possible_actions = DIRECTIONS.copy()
# if the cell has a box, add action B
# second check (action != 'B') to avoid infinite loop
if map[coord] == 'B' and action != 'B':
possible_actions['B'] = (0, 0)
# get all possible actions and corresponding movements
for next_action, (dx, dy) in possible_actions.items():
# new candidate cell
candidate = coord[0] + dx, coord[1] + dy
# check that the candidate is within bounds and that it is not
# a water cell
if candidate[0] in range(height) and candidate[1] in range(width) and map[candidate] in '.SBE':
if next_action == 'B' and map[candidate] == 'B':
# if the action is 'B', flip the box variable ...
new_box = not box
# ... and set the cost to 1
move_cost = 1
else:
# otherwise maintain the same state ...
new_box = bool(box)
# ... and set the cost depending on the box
if new_box:
move_cost = 2
else:
move_cost = 1
# compute new heuristic
h = cost + move_cost + distance(candidate, goal)
# create and push the new cell
new_cell = Cell(h, cost + move_cost, new_box, candidate, next_action, current)
heapq.heappush(frontier, new_cell)
# reconstruct the moves by recursing cell.prev
result = ''
while current.prev is not None:
result = current.action + result
current = current.prev
return result
July 17, 2021