Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Modified A* solution in Clear category for Supply Stations by bukebuer
# migrated from python 2.7
from copy import deepcopy
from itertools import permutations
def supply_routes(the_map):
llim, wlim = len(the_map), len(the_map[0])
locdict = {}
for i in range(llim):
for j in range(wlim):
if the_map[i][j] in ['1', '2', '3', '4']:
locdict[int(the_map[i][j]) - 1] = (i, j)
elif the_map[i][j]=='F':
F = (i, j)
def get_neighbor(p):
plist = [(p[0]-1, p[1]), (p[0]+1, p[1]), (p[0], p[1]-1), (p[0], p[1]+1)]
plist = [(i,j) for i,j in plist if 0<=i 0) and (end not in closeDict):
now = sorted(list(openDict.keys()), key=lambda x: sum(openDict[x][:2]))[0]
closeDict[now] = openDict[now]
del openDict[now]
plist = [(i,j) for i,j in get_neighbor(now) if recmap[i][j]=='.']
if check:
recmap[now[0]][now[1]] = 'X'
for p in plist:
if check:
newmap = deepcopy(recmap)
newmap[p[0]][p[1]] = 'X'
if not all([access(s, target, newmap) for s in check]):
continue
if p in closeDict:
continue
elif p not in openDict:
openDict[p] = (closeDict[now][0] + 1, h(p, end), now)
elif closeDict[now][0] + 1 + h(p, end) < sum(openDict[p][:2]):
openDict[p] = (closeDict[now][0] + 1, h(p, end), now)
if end not in closeDict:
return None
path = [end]
while start not in path:
path = [closeDict[path[0]][2]] + path
return path
def path2dir(path):
dirmap = [[0, 'E', 'W'], ['S'], ['N']]
d = ''
for i,p in enumerate(path):
if i>0:
q = path[i-1]
x = [p[0]-q[0], p[1]-q[1]]
d += dirmap[x[0]][x[1]]
return d
# naive search, fast but may find nothing
for ports in permutations(get_neighbor(F)):
for sources in permutations((0, 1, 2, 3)):
newmap = [list(r) for r in the_map]
pathmap = [0, 0, 0, 0]
for n,s in enumerate(sources):
path = find_path(locdict[s], ports[n], newmap)
if path is None:
break
pathmap[s] = path
for i,j in path:
newmap[i][j] = 'X'
if 0 not in pathmap:
return [path2dir(path+[F]) for path in pathmap]
# sophisticated search, slow but more careful
for ports in permutations(get_neighbor(F)):
for sources in permutations((0, 1, 2, 3)):
newmap = [list(r) for r in the_map]
pathmap = [0, 0, 0, 0]
for n,s in enumerate(sources):
check = [locdict[t] for t in sources[n+1:]]
path = find_path(locdict[s], ports[n], newmap, check, F)
if path is None:
break
pathmap[s] = path
for i,j in path:
newmap[i][j] = 'X'
if 0 not in pathmap:
return [path2dir(path+[F]) for path in pathmap]
Sept. 10, 2014
Comments:
