Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Third solution in Clear category for Express Delivery by pjwerneck
# migrated from python 2.7
import math
import itertools
import heapq
class Field(object):
def __init__(self, field):
self._w = len(field[0])
self._h = len(field)
self._field = ''.join(field)
def i2c(self, i):
y, x = divmod(i, self._w)
return x, y
def c2i(self, x, y):
return y * self._w + x
def neighbors(self, node):
i = node
w = self._w
for d, f in [('U', -w), ('D', w), ('L', -1), ('R', 1)]:
j = i + f
# ignore if out of bounds
if (d in 'LR' and j / self._w != i / self._w) or not 0 <= j < len(self._field):
continue
if self._field[j] == 'W':
continue
yield d, j
def edist(self, s, d):
w = self._w
return math.hypot(s % w - d % w, s / w - d / w)
def mdist(self, s, d):
w = self._w
return abs(s % w - d % w) + abs(s / w - d / w)
def dist(self, s, d):
return self.mdist(s, d)
def find_paths(self, src, dest):
# a node is a tuple (dist, index, path)
queue = [(self.dist(src, dest), src, '')]
visited = set()
paths = []
while queue:
dist, node, path = heapq.heappop(queue)
if node == dest:
# if we reached the destination, save this path
paths.append(path)
continue
visited.add(node)
for d, other in self.neighbors(node):
if other not in visited:
heapq.heappush(queue, (self.dist(other, dest), other, path + d))
return paths
def get_start(self):
return self._field.index('S')
def get_end(self):
return self._field.index('E')
def get_boxes(self):
return [i for (i, x) in enumerate(self._field) if x == 'B']
def cost(self, path):
# 2/cell if not using boxes
if 'B' not in path:
return len(path) * 2
else:
# 2/cell driving to/from box, 1/cell between boxes, 1/cell load/unload
a, b, c = path.split('B')
return len(a) * 2 + len(b) + len(c) * 2 + 2
def search(self):
start = self.get_start()
end = self.get_end()
# first, find straight paths from start to exit
paths = self.find_paths(start, end)
# I could probably use the A* itself to consider the cost of
# loading, unloading and moving without the load, but I
# couldn't figure a way to do it that could get the corner
# cases and still be simpler and perform better than this
# pragmatic approach.
# find all dropboxes
boxes = self.get_boxes()
# for every pair of boxes, compute the paths start -> drop -> load -> end
for drop, load in itertools.permutations(boxes, 2):
a = self.find_paths(start, drop)
b = self.find_paths(drop, load)
c = self.find_paths(load, end)
# get all combinations and join them with the drop/load command
paths.extend('B'.join(x) for x in itertools.product(a, b, c))
# and finally, get the cheapest
return min(paths, key=self.cost)
def checkio(field_map):
f = Field(field_map)
return f.search()
#These "asserts" using only for self-checking and not necessary for auto-testing
if __name__ == '__main__':
checkio(["S...","....","B..B","..WE"])
checkio(["S...", "....", "B.WB", "..WE"]) # RRRDDD
checkio(["S...", "....", "B..B", "..WE"]) # DDBRRRBD
checkio(["S.W...","..WB..","..WW..","....B.","....W.","..B.BE"])
checkio(['S...BB..E'])
Jan. 11, 2014
Comments: